4

如果你去这里：IOrderedEnumerableDocs并单击 .Contains() 方法，那么它会带你到这里：通用 Enumerable.Contains() 文档

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

鉴于您知道您有一个可以与您的元素进行比较的排序列表（例如，进行二分搜索以确认该元素是否存在，而不是枚举整个集合？

我错过了什么吗？

4

3 回答 3

6

从一开始就值得注意的是，给定方法仅记录为操作上的IEnumerable<T>事实并不意味着它没有针对给定实现或派生接口进行优化。事实上，Enumerable对于不同的派生接口和/或具体实现，许多方法采用不同的路径。这里的经典示例是，Count()如果IEnumerable<T>在 implementsICollection<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) 时间，等等。

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

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

首先，要单独重载 forIOrderedEnumerable<T>需要向公共 API 添加一个方法，但只涵盖某些情况（也许我们给出的 anIEnumerable<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(n) 时间和 O(1) 空间，尽管它可能是 O(log n) 或 O(1) 时间，如果source是例如 a HashSet<T>（Contains()已经优化的情况）。在理论和实践中，它最终都会比上面的缓冲步骤更快。

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

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

于 2016-01-25T17:58:33.490 回答
3

为了能够使用二分搜索，您需要某种排序的数据结构。也许是排序数组或排序列表。但是你刚刚得到了一个IOrderedEnumerable实现；查询尚未实现。

您IOrderedEnumerable可以使用 Iterator 块或一些惰性查询（通常是这样生成的）来简单地创建。那里没有真正的数据结构。您无法从枚举IOrderedEnumerable或IEnumerable不枚举它们中获取所有元素，即 O(n)。

因此，您无法实现二进制搜索或类似的东西。

于 2016-01-25T17:26:02.213 回答
0

因此，基于@Sriram 的回答，但充实了具体问题：

这里的基本问题是，因为你只有一个生成规则，而不是一个实例化的数据集，所以为了进行二进制搜索的任何变体，你首先必须生成所有元素直到你的上限，所以你已经已经超过了您的目标元素。所以最好抓住它。

如果您的对象很难比较但很容易生成，那么您可能会获得更好的性能（即有效地实例化整个集合然后进行二分搜索，因此比依次比较每个元素进行的比较更少）。但是你会以更常见的情况为代价这样做。无论如何，您可以通过调用 .ToArray() 并将 THAT 的结果传递给您的二进制搜索算法来实现。

于 2016-01-25T18:01:05.327 回答