内存中的LINQ性能

Question

除了与您最喜爱的提供程序相关的LINQ外，这个问题是关于在内存集合中搜索或过滤的。

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

例如：

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

在这种情况下，除非list按照某个标准排序，否则每个算法都至少需要 O(n) 的时间来执行搜索。如果按照'something'排序，则搜索应该采用二分查找，其时间复杂度为O(log(n))。然而，如果我理解正确，这个查询将通过枚举来解决，因此即使list之前已经排序，它也应该需要 O(n) 的时间。

• 有什么方法可以在O(log(n))的时间内解决查询吗？
• 如果我想要更好的性能，应该使用Array.Sort和Array.BinarySearch吗？

- Pablo Marambio

Answer 1

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

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

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

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

- Jon Skeet

Answer 2

是的，通用情况下时间复杂度总是O(n)，正如Sklivvz所说。

然而，很多LINQ方法都会对实现IEnumerable接口的对象进行特殊处理，例如当其实现ICollection时。（至少我在IEnumerable.Contains中看到过这种情况。）

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

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

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

您可以使用反射器来查看LINQ方法的定义，这就是我找到答案的方式。

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

- Tobi

---

按照问题所述的属性进行过滤，这该怎么实现？ - Sklivvz

然后，您可以使用ToDictionary或ToLookup，将该属性映射到字典的键，将对象本身映射到字典的值。 （Both ToDircetionary and ToLookup take delegates to specify what should be key and what should be value.） - Tobi

当然，这只会在您对不变的结果集上进行足够多的特定属性搜索时加快速度。我认为，过滤/搜索属性只是一个例子，快速搜索对象本身也包括在问题中 :) - Tobi

Answer 3

是的，必须这样做，因为访问 IEnumerable 的任何成员的唯一方法是使用其方法，这意味着 O(n)。

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

- Sklivvz

---

谢谢你的回答。这正是我所想的。但是...难道没有绕过这个问题的方法吗？也许可以通过并行化来解决。 - Pablo Marambio

@Marambio：看看PLINQ吧，它试图并行化大部分LINQ。 - user7116