c# - 为什么 IOrderedEnumerable 不重新实现 .Contains() 以获得性能

Question

如果你去这里:The IOrderedEnumerableDocs然后单击 .Contains() 方法，然后它会将您带到此处:the generalised Enumerable.Contains() docs

我认为这意味着它只是使用底层的 IEnumerable 实现？

这看起来很奇怪，因为你知道你有一个可以与你的元素进行比较的排序列表(例如，进行二进制搜索以确认元素是否存在，而不是枚举整个设置？

我错过了什么吗？

Answer 1

从一开始就值得注意的是，给定方法仅记录为在 IEnumerable<T> 上运行这一事实并不意味着它没有针对给定的实现或派生接口(interface)进行优化。事实上 Enumerable 中的很多方法为不同的派生接口(interface)和/或具体实现采取不同的路径。这里的经典例子是 Count()如果 IEnumerable<T> 采取不同的路径它被称为工具ICollection<T>或 ICollection .在完整的框架中还有几个这样的例子，在 .NET Core 中甚至更多，包括一些采用优化路径来实现 IOrderedEnumerable<T> 的例子。你可以调用OrderBy() .

其中一些是我做的，因为这些天我的爱好是为 .NET Core 做出贡献，尤其是 Linq，尤其是性能改进(尽管很明显，如果我正在破解某些东西，我需要增加对位的测试我'我很感人，当这样做时会出现小错误，它们会优先于性能改进)。

说到IOrderedEnumerable ，我做过类似改变的事情.OrderBy(someLambda).Skip(j).Take(k) (常见的分页习语)从 O(n log n) 时间计算和 O(j + k) 时间枚举到 O(n + k log k) 时间计算和 O(k) 时间枚举，以及 .OrderBy(someLambda).First()对于 O(n) 空间和 O(n log n) 时间到 O(1) 空间和 O(n) 时间，等等。

我可能会考虑改进其他方法，当然，如果我不这样做，其他人也很可能会这样做。

如果我这样做，我将不会按照您的建议去做。

首先，为 IOrderedEnumerable<T> 单独重载将需要向公共(public) API 添加一个方法，但仅涵盖某些情况(也许我们作为 IEnumerable<T> 给出的实际上是 IOrderedEnumerable<T> )。为 IEnumerable<T> 设置一个过载要好得多并检测 IOrderedEnumerable<T>案例。

其次，要使用二进制搜索，我们必须知道 IOrderedEnumerable 的方式。被排序。这可以通过 OrderedEnumerable<TElement, TKey> 实现通过调用 OrderBy 创建但不是更普遍。

第三，这不会是最大可能的收获。

当前成本source.OrderBy(someLambda).Contains(someItem)如下:

1. 缓冲区 source : O(n) 空间，O(n) 时间。
2. 对缓冲区进行排序:O(n log n) 时间(平均，O(n²) 更差)。
3. 找到与 someItem 匹配的一项，或确认不存在。:O(n) 时间。

如果Contains()被优化为使用二进制搜索它将变成:

1. 缓冲区 source : O(n) 空间，O(n) 时间。
2. 对缓冲区进行排序:O(n log n) 时间(平均，O(n²) 更差)。
3. 找到与 someItem 匹配的一项，或确认不存在。:O(log n) 时间(平均，O(n) 更糟，因为精确匹配可能与所有元素在同一级别排序，并且必须与所有元素进行比较)。

然而，这完全是一种浪费。如果我们想优化Contains() (以及与此相关的许多其他聚合方法)最佳策略是:

1. 调用source.Contains(someItem)并返回结果。这将更糟糕的是 O(n) 时间和 O(1) 空间，尽管它可能是 O(log n) 或 O(1) 时间如果 source例如 HashSet<T> (Contains() 已经针对这种情况进行了优化)。在理论和实践中，它最终都会比上面的缓冲步骤更快。

实现该更改将大大减少工作量，并获得更大的 yield 。

我已经考虑过了，可能确实会提交这样的 PR，但我还不确定总的来说它是否值得(因此如果其他人提交这样的 PR，我的意见会是什么)因为它几乎总是来电者更容易转….OrderBy(foo).Contains(bar)进入.Contains(bar)他们自己，并且针对这种情况进行优化所需的检查会很便宜，但并非完全免费。