草庐IT

C# 二叉树和字典

coder 2024-05-20 原文

我在纠结何时使用二叉搜索树以及何时使用字典的概念。

在我的应用程序中，我做了一个使用 C5 库的小实验 TreeDictionary (我认为这是一个红黑二叉搜索树)和 C# 字典。字典在添加/查找操作时总是更快，而且总是使用更少的内存空间。例如，在 16809 <int, float>条目，字典使用了 342 KiB，而树使用了 723 KiB。

我认为 BST 应该具有更高的内存效率，但似乎树的一个节点比字典中的一个条目需要更多的字节。是什么赋予了？ BST 是否比字典更好？

此外，作为附带问题，有谁知道是否有更快+内存效率更高的数据结构来存储 <int, float>用于字典类型访问的对而不是上述任何一种结构？

最佳答案

I thought that BST's were supposed to be more memory efficient, but it seems that one node of the tree requires more bytes than one entry in a dictionary. What gives? Is there a point at where BST's are better than dictionaries?

我个人从未听说过这样的原则。即便如此，这只是一个普遍原则，而不是刻在宇宙结构中的绝对事实。

一般来说，字典实际上只是一组链表的奇特包装器。您在字典中插入如下内容:

LinkedList<Tuple<TKey, TValue>> list =
    internalArray[internalArray % key.GetHashCode()];
if (list.Exists(x => x.Key == key))
    throw new Exception("Key already exists");
list.AddLast(Tuple.Create(key, value));

所以它的几乎 O(1) 操作。字典使用 O(internalArray.Length + n) 内存，其中 n 是集合中的项目数。

一般来说，BST 可以实现为:

  • 链表，使用 O(n) 空间，其中 n 是集合中的项目数。
  • arrays ，它使用 O(2h - n) 空间，其中 h 是树的高度，n 是集合中的项目数。
    • 由于红黑树的有界高度为 O(1.44 * n)，因此数组实现的有界内存使用量应约为 O(21.44n - n)

奇怪的是，C5 TreeDictionary 是使用数组实现的，这可能是浪费空间的原因。

What gives? Is there a point at where BST's are better than dictionaries?

字典有一些不受欢迎的特性:

  • 可能没有足够的连续内存块来容纳您的字典，即使它的内存需求远小于总可用 RAM。

  • 计算哈希函数可能需要任意长的时间。例如，字符串使用 Reflector 检查 System.String.GetHashCode 方法——您会注意到对字符串进行哈希处理总是需要 O(n) 时间，这意味着它可能需要相当长的时间字符串。另一方面，比较字符串的不平等几乎总是比散列更快，因为它可能只需要查看前几个字符。如果哈希码计算时间过长，树插入完全有可能比字典插入更快。

    • Int32 的 GetHashCode 方法实际上只是return this，因此您很难找到具有 int 键的哈希表比树字典慢的情况。

RB 树有一些理想的特性:

  • 与使用字典的 O(n) 时间相比，您可以在 O(log n) 时间内找到/删除 Min 和 Max 元素。

  • 如果将树实现为链表而不是数组，则树通常比字典更节省空间。

  • 同样，在 O(log n) 时间内编写支持插入/查找/删除的树的不可变版本非常容易。字典不能很好地适应不变性，因为您需要为每个操作复制整个内部数组(实际上，我已经看到了一些基于数组的不可变手指树实现，一种通用字典数据结构，但实现起来非常复杂)。

  • 您可以在恒定空间和 O(n) 时间内按排序顺序遍历树中的所有元素，而您需要将哈希表转储到数组中并对其进行排序才能获得相同的效果。

因此，数据结构的选择实际上取决于您需要的属性。如果您只想要一个无序包并且可以保证您的散列函数快速评估，请使用 .Net 字典。如果您需要有序包或运行缓慢的哈希函数，请使用 TreeDictionary。

关于C# 二叉树和字典，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2151747/

C#二叉树code的sectiondictionarybinary-search-treec5

有关C# 二叉树和字典的更多相关文章

  1. c# - 如何在 ruby​​ 中调用 C# dll？ - 2

    如何在ruby​​中调用C#dll？ 最佳答案 我能想到几种可能性:为您的DLL编写(或找人编写)一个COM包装器，如果它还没有，则使用Ruby的WIN32OLE库来调用它；看看RubyCLR,其中一位作者是JohnLam，他继续在Microsoft从事IronRuby方面的工作。(估计不会再维护了，可能不支持.Net2.0以上的版本)；正如其他地方已经提到的，看看使用IronRuby，如果这是您的技术选择。有一个主题是here.请注意，最后一篇文章实际上来自JohnLam(看起来像是2009年3月)，他似乎很自在地断言RubyCL

  2. C# 到 Ruby sha1 base64 编码 - 2

    我正在尝试在Ruby中复制Convert.ToBase64String()行为。这是我的C#代码:varsha1=newSHA1CryptoServiceProvider();varpasswordBytes=Encoding.UTF8.GetBytes("password");varpasswordHash=sha1.ComputeHash(passwordBytes);returnConvert.ToBase64String(passwordHash);//returns"W6ph5Mm5Pz8GgiULbPgzG37mj9g="当我在Ruby中尝试同样的事情时，我得到了相同sha

  3. 基于C#实现简易绘图工具【100010177】 - 2

    C#实现简易绘图工具一.引言实验目的:通过制作窗体应用程序(C#画图软件),熟悉基本的窗体设计过程以及控件设计,事件处理等,熟悉使用C#的winform窗体进行绘图的基本步骤,对于面向对象编程有更加深刻的体会.Tutorial任务设计一个具有基本功能的画图软件**·包括简单的新建文件,保存,重新绘图等功能**·实现一些基本图形的绘制,包括铅笔和基本形状等,学习橡皮工具的创建**·设计一个合理舒适的UI界面**注明:你可能需要先了解一些关于winform窗体应用程序绘图的基本知识,以及关于GDI+类和结构的知识二.实验环境Windows系统下的visualstudio2017C#窗体应用程序三.

  4. 微信小程序通过字典表匹配对应数据 - 2

    前言一般来说，前端根据后台返回code码展示对应内容只需要在前台判断code值展示对应的内容即可，但要是匹配的code码比较多或者多个页面用到时，为了便于后期维护，后台就会使用字典表让前端匹配，下面我将在微信小程序中通过wxs的方法实现这个操作。为什么要使用wxs？{{method(a,b)}}可以看到，上述代码是一个调用方法传值的操作，在vue中很常见，多用于数据之间的转换，但由于微信小程序诸多限制的原因，你并不能优雅的这样操作，可能有人会说，为什么不用if判断实现呢？但是if判断的局限性在于如果存在数据量过大时，大量重复性操作和if判断会让你的代码显得异常冗余。wxswxs相当于是一个独立

  5. ruby - 在 Ruby 中实现二叉树 - 2

    我一直在尝试在Ruby中实现BinaryTree类，但我得到了stackleveltoodeep错误，尽管我似乎没有在该特定代码段中使用任何递归:1.classBinaryTree2.includeEnumerable3.4.attr_accessor:value5.6.definitialize(value=nil)7.@value=value8.@left=BinaryTree.new#stackleveltoodeephere9.@right=BinaryTree.new#andhere10.end11.12.defempty?13.(self.value==nil)?true:

  6. python - 将 Ruby 哈希字符串转换为 Python 字典 - 2

    我正在处理一些作为Ruby哈希字符串返回的命令输出。(来自名为mcollective的东西)。这是我收到的示例字符串:{:changes=>{"total"=>0},:events=>{"failure"=>0,"success"=>0,"total"=>0},:version=>{"puppet"=>"2.7.21(PuppetEnterprise2.8.1)","config"=>1381497648},:time=>{"filebucket"=>0.000287,"cron"=>0.00212,"package"=>0.398982,"exec"=>0.001314,"confi

  7. c# - C# 中的 Flatten Ruby 方法 - 2

    我如何做Ruby方法"Flatten"RubyMethod在C#中。此方法将锯齿状数组展平为一维数组。例如:s=[1,2,3]#=>[1,2,3]t=[4,5,6,[7,8]]#=>[4,5,6,[7,8]]a=[s,t,9,10]#=>[[1,2,3],[4,5,6,[7,8]],9,10]a.flatten#=>[1,2,3,4,5,6,7,8,9,10 最佳答案 递归解决方案:IEnumerableFlatten(IEnumerablearray){foreach(variteminarray){if(itemisIEnume

  8. ruby - 可以像在 C# 中使用#region 一样在 Ruby 中使用 begin/end 吗？ - 2

    我最近从C#转向了Ruby，我发现自己无法制作可折叠的标记代码区域。我只是想到做这种事情应该没问题:classExamplebegin#agroupofmethodsdefmethod1..enddefmethod2..endenddefmethod3..endend...但是这样做真的可以吗？method1和method2最终与method3是同一种东西吗？还是有一些我还没有见过的用于执行此操作的Ruby惯用语？ 最佳答案 正如其他人所说，这不会改变方法定义。但是，如果要标记方法组，为什么不使用Ruby语义来标记它们呢？您可以使用

  9. c# - Ruby 等效于 C# Linq 聚合方法 - 2

    什么是Linq聚合方法的ruby​​等价物。它的工作原理是这样的varfactorial=new[]{1,2,3,4,5}.Aggregate((acc,i)=>acc*i);每次将数组序列中的值传递给lambda时，变量acc都会累积。 最佳答案 这在数学以及几乎所有编程语言中通常称为折叠。它是更普遍的变形概念的一个实例。Ruby从Smalltalk中继承了这个特性的名称，它被称为inject:into:(像aCollectioninject:aStartValueinto:aBlock一样使用。)所以，在Ruby中，它称为inj

  10. c# - 先学什么？ - 2

    关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭8年前。Improvethisquestion几年前我去学校学习编程，毕业后我找到了一份系统管理方面的工作，这就是我职业生涯的方向。我想重新开始某种开发，并且一直在“玩”C#和ASP.NET，但我已经听到很多关于其他"new"语言的讨论(新的意思是它们是新的)我)喜欢Ruby和F#。我想我想知道我是否在浪费时间学习主要的MS语言，而不是成为一名通才。很长一段时间没有离开开发社区(如果我曾经离开过的话)让我在潮流中挣扎，我不想落在时代的

随机推荐