将IEnumerable转换为字典以获得性能？

Question

我最近在我的公司看到了一个新趋势,我们通过简单的LINQ转换将IEnumerable更改为字典,如下所示:

enumerable.ToDictionary(x=>x);

当集合上的操作是包含/访问时,我们大多数情况下最终会这样做,显然字典在这种情况下具有更好的性能.

但我意识到将Enumerable转换为字典有其自身的成本,我想知道它在什么时候开始收支平衡(如果确实如此),即Contains/Access 的性能IEnumerable等于ToDictionary+ access/contains.

好的我可能会添加没有数据库访问,可以从数据库查询创建枚举,这就是它,并且可以在之后编辑枚举...

知道密钥的数据类型如何影响性能也很有趣？

查询可能一般是2-5次,但有时也可能是一次.但是我已经看到了类似于可枚举的东西:

 var element=Enumerable.SingleorDefault(x=>x.Id);
 //do something if element is null or return

对于字典:

 if(dictionary.ContainsKey(x))
 //do something if false else  return

这已经困扰了我很长一段时间了.

Answer 1

字典的性能与IEnumerable相比

A Dictionary,正确使用时,读取总是更快(除非数据集非常小,例如10个项目).创建它时可能会有开销.

给定m针对同一对象执行的查找量(这些是近似值):

• 性能IEnumerable(从干净的清单创建):O(mn)
  • 这是因为您需要每次(基本上m * O(n))查看所有项目.
• 表现Dictionary:O(n) + O(1m)或,或O(m + n)
  • 这是因为您需要先插入项目(O(n)).

一般来说,可以看出Dictionary胜利时m > 1,IEnumerable胜利时m = 1或m = 0.

一般来说,你应该:

• Dictionary在针对同一数据集多次执行查找时使用a .
• IEnumerable在执行查找时使用.
• 使用IEnumerable时,该数据集可能太大,无法到内存中.
  • 请记住,SQL表可以像a一样使用Dictionary,因此您可以使用它来抵消内存压力.

进一步的考虑

Dictionary■使用GetHashCode()来组织其内部状态.a的性能Dictionary以两种方式与哈希码密切相关.

• 性能不佳GetHashCode()- 每次添加,查找或删除项目时都会产生开销.
• 低质量哈希码 - 导致字典没有O(1)查找性能.

大多数内置的.Net类型(尤其是值类型)都有非常好的散列算法.但是,类似列表的类型(例如字符串)GetHashCode()具有O(n)性能 - 因为它需要迭代整个字符串.因此,你的字典的表现真的可以被看作(这里M是大哦,有效率的GetHashCode())O(1) + M.