Linq ToList/ToArray/ToDictionary 性能

Question

我经常遇到一些情况，仅有IEnumerable是不够的。但是我对上述方法调用的性能不确定。

我真正想问的是:

ToList/ToArray的性能：

1. 是否为O(n)操作，将IEnumerable复制到一个新的数组/List中？

2. 如果我在列表上调用linq扩展方法，如果调用ToList，则其性能为O(1)，但如果调用ToArray，则为O(n)(反之亦然，如果我的原始列表是一个数组)？

3. 是否发生了某些魔法，使性能为O(1)？

可能转换为Dictionary是O(n)，对吗？

- Jonny

Answer 1

ToList/ToArray 的性能是 O(n)，会将 IEnumerable 复制到一个新的数组/List 中吗？

是的。 ToList 稍微更有效率，因为它不需要先修剪内部缓冲区到正确的长度。

如果我在列表上调用 linq 扩展方法，如果我调用 ToList，则其性能为 O(1)，但如果我调用 ToArray，则其性能为 O(n)（如果我的原始列表是数组，则相反）？

不是这样的。对于两个调用，总是创建一个新的集合；那是原始集合的浅拷贝。调用任何 ICollection<T> 上的 ToList 或 ToArray 比在简单的没有实现 ICollection<T> 的 IEnumerable<T> 上调用更有效率，因为集合的长度一开始就是已知的。（尽管这在执行时被检测到；您不需要担心编译时类型。）

可能转换为 Dictionary 是 O(n)，对吗？

假设哈希是合理的，那么时间复杂度为O(N)。基本上，它会按照你预期的方式创建一个新的字典。

你可能想阅读我在Edulinq博客系列中对应的文章:

- ToList - ToArray - ToDictionary

- Jon Skeet

---

我想补充说，将此链接添加到您的答案中：http://msmvps.com/blogs/jon_skeet/archive/2011/01/01/reimplementing-linq-to-objects-part-20-tolist.aspx - MarcinJuraszek

@JonSkeet：哇，我没注意那是你的博客文章 :) 不得不说，真的很棒！ - MarcinJuraszek

@MarcinJuraszek 是的，请查看完整的 Edulinq 系列 和电子书。非常棒，真正帮助理解 Linq、集合迭代以及它的一般优雅之处；扩展了我的思路。说到电子书，Jon 有计划重新更新/编辑已出版的 PDF 版本吗？我一定会购买一个完全打磨和印刷版的。 :) - Chris Sinclair

@ChrisSinclair：有一家出版商实际上拥有它的权利，但我仍然不知道他们是否打算使用它们... - Jon Skeet

@JonSkeet，博客链接现在已经失效了。看起来路径的第一个部分从“jon_skeet”变成了“jonskeet”。以下是新链接，以防有人需要：ToList，ToArray，ToDictionary。 - rdumont

@rdumont：那仍然是我的旧博客 - 我已经更新了链接，指向我的新博客。 - Jon Skeet