内存中 LINQ 性能

Question

这个问题不仅仅是关于 LINQ to [在此处插入您最喜欢的提供程序]，而是关于搜索或过滤内存中集合。

我知道 LINQ（或搜索/过滤扩展方法）适用于实现 IEnumerable 或者 IEnumerable<T>. 。问题是： 由于枚举的性质，每个查询的复杂度至少是 在）?

例如：

var result = list.FirstOrDefault(o => o.something > n);

在这种情况下，每个算法至少需要 在） 除非 list 是关于 'something', ，在这种情况下，搜索应该采取 O(log(n)): ：应该是二分查找。但是，如果我理解正确的话，这个查询将通过枚举来解决，所以应该采取 在）, ， 即使在 list 之前已订购。

• 我可以做些什么来解决查询 O(log(n))?
• 如果我想要性能，我应该使用 Array.Sort 和 Array.BinarySearch 吗？

Answer 1

即使采用并行化，它仍然是 O(n)。常数因子会有所不同（取决于核心数量），但随着 n 的变化，总时间仍会线性变化。

当然，您可以根据自己的数据类型编写各种 LINQ 运算符的自己的实现，但它们只适用于非常特定的情况 - 您必须确定谓词仅在优化方面进行操作数据。例如，如果您有一个按年龄排序的人员列表，那么它不会帮助您尝试查找具有特定名称的人:)

要检查谓词，您必须使用表达式树而不是委托，并且生活会变得更加困难。

我怀疑我通常会添加新方法，使您明显地知道您正在使用索引/有序/任何性质的数据类型，并且这些方法始终可以正常工作。当然，您无法轻松地从查询表达式调用这些额外的方法，但您仍然可以使用带有点表示法的 LINQ。

Answer 2

是的，正如 Sklivvz 所说，一般情况总是 O(n)。

然而，许多 LINQ 方法的特殊情况是当实现 IEnumerable 的对象实际实现时，例如I集合。（我已经在 IEnumerable.Contains 中看到过这个。）

实际上，这意味着 LINQ IEnumerable.Contains 会调用快速 HashSet.Contains，例如，如果 IEnumerable 实际上是 HashSet。

IEnumerable<int> mySet = new HashSet<int>();

// calls the fast HashSet.Contains because HashSet implements ICollection.
if (mySet.Contains(10)) { /* code */ }

您可以使用 Reflector 来准确检查 LINQ 方法的定义方式，这就是我的解决方法。

哦，LINQ 还包含方法 IEnumerable.ToDictionary（将键映射到单个值）和 IEnumerable.ToLookup（将键映射到多个值）。该字典/查找表可以创建一次并使用多次，这可以将某些 LINQ 密集型代码的速度提高几个数量级。

Answer 3

是的，必须如此，因为访问任何成员的唯一方法 IEnumerable 是通过使用它的方法，这意味着 O(n)。

这似乎是一个经典案例，语言设计者决定用性能来换取通用性。