c# - 内存中的 LINQ 性能

Question

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

我知道 LINQ(或搜索/过滤扩展方法)适用于实现 IEnumerable 的对象或 IEnumerable<T> .问题是:由于枚举的性质，每个查询的复杂度是否至少为 O(n)？

例如:

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

在这种情况下，每个算法至少需要 O(n) 除非 list是根据 'something' 订购的，在这种情况下，搜索应该采用 O(log(n)):它应该是二分搜索。但是，如果我理解正确的话，这个查询将通过枚举来解决，所以它应该花费 O(n)，即使在 list 中也是如此。之前订购过。

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

Answer 1

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

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

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

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