性能字典<string,int>与List <string>

Question

我有一个大约500个字符串的列表"joe""john""jack"..."jan"

我只需要找到序数.

在我的示例中,列表永远不会更改.

可以将它们放在列表和IndexOf中

ll.Add("joe")
ll.Add("john")
...
ll.Add("jan")
ll.IndexOf("jib") is 315

或者你可以使用序数整数作为值将它们放在字典中,

dd.Add("joe", 1)
dd.Add("john", 2)
dd.Add("jack", 3)
...
dd.Add("jan", 571)
dd["jib"] is 315

FTR字符串长度为3到8个字符.FTR这是一个Unity,因此Mono,环境.

1)纯粹为了性能,一种方法通常更可取吗？

1b)实际上,我发现了许多这种性质的分析:http://www.dotnetperls.com/dictionary-time(google进行了大量类似的分析).这适用于我描述的情况还是我在这里？

2)关于哪个在一般的开发工程意义上更好.(完全抛开表现.)在我看来,两者都有明显的优点和缺点; 既不优雅.

3)遗憾的是没有"HashSetLikeThingWithOrdinality"类型的设施 - 如果我错过了明显的请告诉我们.实际上,这似乎是一个相当普遍的,基本的集合用例 - "得到一些字符串的序数" - 也许我完全错过了一些明显的东西.

Answer 1

以下是使用a Dictionary<string,int>和a(已排序)之间差异的小概述List<string>:

观察:1)在我的微基准测试中,一旦创建了字典,字典就会快得多.(关于为什么会很快跟进的解释)2)在我看来,以某种方式(例如a Dictionary或HashTable)的映射将显着减少尴尬.

性能:

对于List<string>,进行二分搜索,系统将从"中间"开始,然后走向每个方向(步入现在减半的搜索空间中的"中间",采用典型的分治模式),具体取决于值是否为大于或小于它正在查看的索引处的值.这是O(log n)增长.这假设数据已经以某种方式排序(也适用于类似的东西SortedDictionary,它使用允许二进制搜索的数据结构)

或者,你会这样做IndexOf,这很O(n)复杂,因为你必须走遍每一个元素.

对于Dictionary<string,int>,它使用哈希查找(通过调用生成对象的哈希.GetHashCode()在TKey这种情况下(串),然后使用该查找在哈希表(然后做了比较,以确保它是精确匹配),并且获得了价值.这大致是O(1)增长(即,复杂性并没有随着元素的数量而有意义地增长)[不包括涉及哈希冲突的最坏情况场景]

因此,Dictionary<string,int>需要(相对)恒定的时间来进行查找,同时List<string>根据元素的数量(尽管以对数(慢)速率增长).

测试:我做了一些微基准测试,在那里我获得了前500名的女性名字并对他们进行了查找.查找看起来像这样:

var searchItems = new[] { "Maci", "Daria", "Michelle", "Amber", "Henrietta"};

foreach (var item in searchItems)
{
    sortedList.BinarySearch(item); //You'd store the output here. Just looking at performance
}

并将其与字典查找进行比较:

 foreach (var item in searchItems)
 {
     var output = dictionary.ContainsKey(item) ? dictionary[item] : -1; //Presumably, output would be declared outside of this, just getting rid of a compiler error
 }

所以,这就是事情:即使对于少量的元素,使用短字符串作为查找键,排序List<string>也不是更快(在我的机器上,在我公认的简单测试中)而不是Dictionary<string,int>.再一次,这是一个微基准测试,但对于500个元素,使用字典,5次查找大约快3倍.

但请记住,列表是6.3 微秒,字典是1.8 微秒.

语法:使用列表作为查找来查找索引有点尴尬.映射类型(如Dictionary)意味着意图比查找列表更好,这应该最终使代码更易于维护.

也就是说,根据我的语法和性能考虑,我会说与词典一起使用.但是,如果你因为某种原因不喜欢字典,那么性能考虑因素就会很小,无论如何都要担心它是毫无意义的.

编辑:奖励积分,您可能希望对任一方法使用不区分大小写的比较器.您可以将比较器作为参数传递,Dictionary并且也BinarySearch()应该支持比较器.