8

不仅仅是关于 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 吗？
4

3 回答 3

5

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

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

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

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

于 2008-09-27T17:28:03.603 回答
3

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

然而，当实现 IEnumerable 的对象实际实现 ICollection 时，许多 LINQ 方法是特殊情况。（我已经为 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 */ }

您可以使用反射器来准确检查 LINQ 方法的定义方式，这就是我想出的方法。

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

于 2008-09-27T17:29:24.380 回答
2

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

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

于 2008-09-27T16:59:53.453 回答