我有一个记录文件,按字母顺序排序:
- 安德鲁·d432
- 本x127
- ...
- ...
- 扎克 b332
第一个字段是人名,第二个字段是一些id。读取文件后,我不需要对数据进行任何更改。
我想将每条记录视为键值对,其中人名是键。我不知道使用哪个类来访问记录(尽可能快)。 Dictionary
没有二进制搜索。另一方面,据我所知,SortedList
和 SortedDictionary
应该只在我需要插入/删除数据时使用。
编辑:澄清一下,我说的只是访问记录,例如:
x = MyDic[Zac]
最佳答案
没有人说明为什么字典是 O(1) 以及为什么它比二进制搜索更快。一方面是字典不按键排序。字典的全部要点是转到键值引用的项的确切*(出于所有实际目的)位置。它不会“搜索”该项目 - 它知道您想要的项目的确切位置。
因此,二分搜索在基于散列的字典上将毫无意义,因为当集合已经确切知道项目的位置时,无需“搜索”该项目。
*在哈希冲突的情况下,这并不完全正确,但字典的原则是直接获取项目,任何额外的查找都是一个实现细节,应该很少见。
On the other hand, as I understand,
SortedList
andSortedDictionary
should be used only when I need to insert/remove data.
当您希望在添加或删除数据时自动对数据进行排序时,应使用它们。请注意,SortedDictionary
失去了“普通”字典的性能增益,因为它现在必须使用键值搜索位置。它的主要用途是允许您按顺序迭代键。
如果您的每个项目都有一个唯一的键值,不需要以任何特定顺序迭代项目,并且想要最快的“获取”性能,那么 Dictionary
是最佳选择。
关于C# - 二进制搜索(排序)字典,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41019464/