这个问题不仅仅涉及LINQ [在此处插入我们喜欢的提供程序]，还涉及搜索或者过滤内存中的集合。

我知道LINQ(或者搜索/过滤扩展方法)可以在实现IEnumerable或者IEnumerable <T>的对象中工作。问题是：由于枚举的性质，每个查询的复杂度是否至少为O(n)？

例如：

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

在这种情况下，除非相对于"某物"对" list"进行排序，否则每种算法都将至少占用O(n)，在这种情况下，搜索应采用O(log(n))：它应该是二进制搜索。但是，如果我理解正确，则此查询将通过枚举解决，因此即使在先前订购的"列表"中也应采用O(n)。

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

解决方案

是的，必须如此，因为访问" IEnumerable"的任何成员的唯一方法是使用其方法，即O(n)。

这似乎是一个经典案例，其中语言设计师决定为了通用而牺牲性能。

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

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

要检查谓词，我们必须使用表达式树而不是委托，生活会变得更加艰辛。

我怀疑我通常会添加新的方法，这些方法使我们明显使用的是数据类型的索引/有序/任何性质，并且始终可以正常工作。当然，我们不能轻易地从查询表达式中调用那些额外的方法，但是我们仍然可以将LINQ与点符号一起使用。

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

但是，当实现IEnumerable的对象实际实现例如ICollection。 (我已经为IEnumerable看到了这一点。至少包含。)

在实践中，这意味着LINQ IEnumerable.Contains会调用快速HashSet。例如，如果IEnumerable实际上是HashSet，则包含。

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密集型代码加速几个数量级。