为什么 IOrderedEnumerable 不重新实现 .Contains() 以获得性能
Why doesn't IOrderedEnumerable re-implement .Contains() to gain performance
如果你去这里：The IOrderedEnumerableDocs and click on the .Contains() method then it takes you to here: the generalised Enumerable.Contains() docs
我认为这意味着它只是使用底层 IEnumerable 实现？
鉴于您知道您有一个可以与您的元素进行比较的排序列表（例如，进行二进制搜索以确认该元素是否存在，而不是枚举），因此有可能进行更高效的搜索，这似乎很奇怪全套？
我错过了什么吗？
为了能够使用二进制搜索，您需要某种排序的数据结构。也许是排序数组或 SortedList。但是你只有一个 IOrderedEnumerable 实现；查询尚未具体化。
您的 IOrderedEnumerable 可以使用 Iterator 块或一些惰性查询（通常是这样生成的）简单地创建。那里没有真正的数据结构。如果不枚举它们，就无法从 IOrderedEnumerable 或 IEnumerable 中获取所有元素，即 O(n)。
因此您无法实施二进制搜索或类似的东西。
从一开始就值得注意的是，给定方法仅记录为在 IEnumerable<T> 上运行的事实并不意味着它未针对给定实现或派生接口进行优化。事实上，Enumerable 中的许多方法针对不同的派生接口 and/or 具体实现采用不同的路径。这里的经典示例是 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) space 和 O(n log n) 时间到 O( 1) space 和 O(n) 时间，依此类推。
我可能会考虑改进其他方法，当然如果我不这样做，其他人也很有可能会这样做。
如果我这样做，我会不会按照你的建议去做。
首先，要为 IOrderedEnumerable<T> 单独重载需要向 public API 添加一个方法，但仅涵盖某些情况（也许我们给出的 IEnumerable<T> 实际上是一个 IOrderedEnumerable<T>)。为 IEnumerable<T> 重载并检测 IOrderedEnumerable<T> 情况要好得多。
其次，要使用二进制搜索，我们必须知道 IOrderedEnumerable 的排序方式。这可以通过 OrderBy 的调用创建的 OrderedEnumerable<TElement, TKey> 实现，但不是更普遍。
第三，这不是最大的收获。
source.OrderBy(someLambda).Contains(someItem)目前的费用如下：
- 缓冲区
source：O(n) space，O(n) 时间。
- 对缓冲区进行排序：O(n log n) 时间（平均，O(n²) 更差）。
- 找到匹配
someItem 的项目，或确认 none 存在。: O(n) 时间。
如果 Contains() 被优化为使用二进制搜索，它将变为：
- 缓冲区
source：O(n) space，O(n) 时间。
- 对缓冲区进行排序：O(n log n) 时间（平均，O(n²) 更差）。
- 找到匹配
someItem 的项目，或确认 none 存在。：O(log n) 时间（平均，O(n) 更糟，因为精确匹配可能会同时排序与所有元素一样，必须与所有元素进行比较。
然而，这完全是一种浪费。如果我们想优化 Contains()（以及许多其他与此相关的聚合方法），最佳策略将是：
- 调用
source.Contains(someItem)并return结果。更糟的是 O(n) 时间和 O(1) space，尽管它可能是 O(log n) 或 O(1) 时间，如果 source 例如 HashSet<T>（Contains() 已经针对这种情况进行了优化）。在理论和实践中，它最终都会比上面的缓冲步骤更快。
实施该更改将大大减少工作量，并获得更大的收益。
我已经考虑过了，可能确实会提交这样的 PR，但我还不确定总的来说它是否值得（因此如果其他人提交这样的 PR 我的意见会是什么）因为它是调用者几乎总是更容易将 ….OrderBy(foo).Contains(bar) 变成 .Contains(bar) 自己，并且针对这种情况进行优化所需的检查会很便宜，但并非完全免费。
所以基于@Sriram 的回答，但充实了具体问题：
这里的根本问题是因为你只有一个生成规则，而不是一个实例化的数据集，所以为了进行二进制搜索的任何变化，你首先必须生成所有元素直到你的上限，所以你已经超过了你的目标元素。所以最好抓住它。
如果你的对象真的很难比较但很容易生成，那么你可能会获得更好的性能（即有效地实例化整个集合然后进行二进制搜索，因此比依次比较每个元素进行更少的比较).但是您这样做会以更常见的情况为代价。无论如何，您可以通过调用 .ToArray() 并将 THAT 的结果传递给二进制搜索算法来实现。
如果你去这里：The IOrderedEnumerableDocs and click on the .Contains() method then it takes you to here: the generalised Enumerable.Contains() docs
我认为这意味着它只是使用底层 IEnumerable 实现？
鉴于您知道您有一个可以与您的元素进行比较的排序列表（例如，进行二进制搜索以确认该元素是否存在，而不是枚举），因此有可能进行更高效的搜索，这似乎很奇怪全套？
我错过了什么吗？
为了能够使用二进制搜索，您需要某种排序的数据结构。也许是排序数组或 SortedList。但是你只有一个 IOrderedEnumerable 实现；查询尚未具体化。
您的 IOrderedEnumerable 可以使用 Iterator 块或一些惰性查询（通常是这样生成的）简单地创建。那里没有真正的数据结构。如果不枚举它们，就无法从 IOrderedEnumerable 或 IEnumerable 中获取所有元素，即 O(n)。
因此您无法实施二进制搜索或类似的东西。
从一开始就值得注意的是，给定方法仅记录为在 IEnumerable<T> 上运行的事实并不意味着它未针对给定实现或派生接口进行优化。事实上，Enumerable 中的许多方法针对不同的派生接口 and/or 具体实现采用不同的路径。这里的经典示例是 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) space 和 O(n log n) 时间到 O( 1) space 和 O(n) 时间，依此类推。
我可能会考虑改进其他方法，当然如果我不这样做，其他人也很有可能会这样做。
如果我这样做，我会不会按照你的建议去做。
首先，要为 IOrderedEnumerable<T> 单独重载需要向 public API 添加一个方法，但仅涵盖某些情况（也许我们给出的 IEnumerable<T> 实际上是一个 IOrderedEnumerable<T>)。为 IEnumerable<T> 重载并检测 IOrderedEnumerable<T> 情况要好得多。
其次，要使用二进制搜索，我们必须知道 IOrderedEnumerable 的排序方式。这可以通过 OrderBy 的调用创建的 OrderedEnumerable<TElement, TKey> 实现，但不是更普遍。
第三，这不是最大的收获。
source.OrderBy(someLambda).Contains(someItem)目前的费用如下：
- 缓冲区
source：O(n) space，O(n) 时间。 - 对缓冲区进行排序：O(n log n) 时间（平均，O(n²) 更差）。
- 找到匹配
someItem的项目，或确认 none 存在。: O(n) 时间。
如果 Contains() 被优化为使用二进制搜索，它将变为：
- 缓冲区
source：O(n) space，O(n) 时间。 - 对缓冲区进行排序：O(n log n) 时间（平均，O(n²) 更差）。
- 找到匹配
someItem的项目，或确认 none 存在。：O(log n) 时间（平均，O(n) 更糟，因为精确匹配可能会同时排序与所有元素一样，必须与所有元素进行比较。
然而，这完全是一种浪费。如果我们想优化 Contains()（以及许多其他与此相关的聚合方法），最佳策略将是：
- 调用
source.Contains(someItem)并return结果。更糟的是 O(n) 时间和 O(1) space，尽管它可能是 O(log n) 或 O(1) 时间，如果source例如HashSet<T>（Contains()已经针对这种情况进行了优化）。在理论和实践中，它最终都会比上面的缓冲步骤更快。
实施该更改将大大减少工作量，并获得更大的收益。
我已经考虑过了，可能确实会提交这样的 PR，但我还不确定总的来说它是否值得（因此如果其他人提交这样的 PR 我的意见会是什么）因为它是调用者几乎总是更容易将 ….OrderBy(foo).Contains(bar) 变成 .Contains(bar) 自己，并且针对这种情况进行优化所需的检查会很便宜，但并非完全免费。
所以基于@Sriram 的回答，但充实了具体问题：
这里的根本问题是因为你只有一个生成规则，而不是一个实例化的数据集，所以为了进行二进制搜索的任何变化，你首先必须生成所有元素直到你的上限，所以你已经超过了你的目标元素。所以最好抓住它。
如果你的对象真的很难比较但很容易生成，那么你可能会获得更好的性能（即有效地实例化整个集合然后进行二进制搜索，因此比依次比较每个元素进行更少的比较).但是您这样做会以更常见的情况为代价。无论如何，您可以通过调用 .ToArray() 并将 THAT 的结果传递给二进制搜索算法来实现。