为什么IOrderedEnumerable无法重新实现.Contains（）以获取性能

Question

如果您去这里：IOrderedEnumerableDocs并单击.Contains（）方法，那么它将带您到这里：广义Enumerable.Contains（）docs

我的意思是说它只是在使用底层的IEnumerable实现？

考虑到您知道可以将排序后的列表与元素进行比较，考虑到可能进行更高性能的搜索，这似乎很奇怪（例如，执行二进制搜索以确认元素是否存在，而不是枚举整个集合？

我有什么想念的吗？

Answer 1

从一开始就值得注意的是，给定方法仅记录为可操作的IEnumerable<T>事实并不意味着未针对给定的实现或派生的接口对其进行优化。实际上，许多方法Enumerable针对不同的派生接口和/或具体实现采用不同的路径。这里的经典示例是，Count()如果IEnumerable<T>在实现ICollection<T>或上调用，则采用不同的路径ICollection。完整框架中还有其他一些示例，.NET Core中还有更多示例，其中一些示例采用了优化的路径来实现IOrderedEnumerable<T>从call获得的实现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>需要向公共API添加一个方法，但仅涵盖某些情况（也许我们给出的IEnumerable<T>实际上是an 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（log n）或O（1）时间，但如果source是a HashSet<T>（Contains()已经针对其优化的情况），这将是O（n）时间和O（1）空间，但更糟。在理论和实践上，它最终都将比上述缓冲步骤更快。

实施该更改将大大减少工作量，并获得更大的收益。

我已经考虑过这一点，可能确实会提交这样的PR，但我不确定总的来说是否值得（因此，如果其他人提交这样的PR，我的看法是什么），因为这样做几乎总是很容易呼叫者….OrderBy(foo).Contains(bar)变成.Contains(bar)自己，通过针对这种情况进行优化所需的检查会很便宜，但并非完全免费。