LINQ方法的运行时复杂性（Big-O）有什么保证？

Question

LINQ方法的运行时复杂性（Big-O）有什么保证？我最近开始使用LINQ了，我还没有真正看到任何LINQ方法的运行时复杂性。显然，这里有很多因素在起作用，所以让我们将讨论局限于普通的IEnumerableLINQ-to-Objects提供者。此外，假设任何Func作为选择器/ mutator /等传入的是廉价的O（1）操作。它似乎很明显，所有的单次操作（Select，Where，Count，Take/Skip，Any/All，等）将是O（n）的，因为他们只需要步行的顺序一次; 虽然这甚至会受到懒惰的影响。对于更复杂的运营来说，事情变得更加模糊; 集合类运算符（Union，Distinct，Except等）使用工作GetHashCode在默认情况下（据我所知），所以它似乎是合理的假设他们使用一个哈希表内，使这些操作为O（n）为好，一般。使用的版本怎么样IEqualityComparer？OrderBy需要排序，所以很可能我们正在看O（n log n）。如果它已经排序了怎么办？如果我说OrderBy().ThenBy()并为两者提供相同的密钥怎么样？我可以看到GroupBy（和Join）使用排序或散列。这是什么？Contains将是O（n）on a List，但是O（1）on a HashSet- LINQ检查基础容器以查看它是否可以加快速度？真正的问题 - 到目前为止，我一直坚信运营是高效的。但是，我可以依靠吗？例如，STL容器清楚地指定了每个操作的复杂性。.NET库规范中的LINQ性能是否有类似的保证？更多问题（回应评论）：没有真正想过开销，但我没想到对于简单的Linq-to-Objects有很多。CodingHorror帖子讨论的是Linq-to-SQL，在那里我可以理解解析查询并使SQL增加成本 - 对象提供者也有类似的成本吗？如果是这样，如果您使用声明性或功能性语法，它会有所不同吗？

Answer 1

保证非常非常少，但有一些优化：

• 使用索引访问扩展方法，比如ElementAt，Skip，Last或者LastOrDefault，将检查底层式工具与否IList<T>，让你得到O（1）访问，而不是O（N）。

• 该Count方法检查ICollection实现，以便该操作是O（1）而不是O（N）。

• Distinct，GroupBy Join我相信set-aggregation方法（Union，Intersect和Except）也使用散列，所以它们应该接近O（N）而不是O（N²）。

• Contains检查ICollection实现，因此如果底层集合也是O（1），它可能是O（1），例如a HashSet<T>，但这取决于实际的数据结构，并且不能保证。散列集覆盖了该Contains方法，这就是它们为O（1）的原因。

• OrderBy 方法使用稳定的快速排序，因此它们是O（N log N）平均情况。

我认为这涵盖了大多数（如果不是全部）内置扩展方法。实际保证很少; Linq本身将尝试利用高效的数据结构，但编写可能效率低下的代码并不是免费的。

Answer 2

我早就知道如果枚举是一个.Count()返回。.CountIList

但是我总是有点疲惫有关Set操作的运行时间复杂度：.Intersect()，.Except()，.Union()。

这是针对.Intersect()（评论我的）反编译的BCL（.NET 4.0 / 4.5）实现：

private static IEnumerable<TSource> IntersectIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer){
  Set<TSource> set = new Set<TSource>(comparer);
  foreach (TSource source in second)                    // O(M)
    set.Add(source);                                    // O(1)

  foreach (TSource source in first)                     // O(N)
  {
    if (set.Remove(source))                             // O(1)
      yield return source;
  }}

结论：

• 性能是O（M + N）

• 当集合已经设置时，实现不会占用优势。（它可能不一定是直截了当的，因为使用过的也需要匹配。）IEqualityComparer<T>

为了完整起见，这里都为实现.Union()和.Except()。

扰流板警报：它们也具有O（N + M） 复杂度。

private static IEnumerable<TSource> UnionIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer){
  Set<TSource> set = new Set<TSource>(comparer);
  foreach (TSource source in first)
  {
    if (set.Add(source))
      yield return source;
  }
  foreach (TSource source in second)
  {
    if (set.Add(source))
      yield return source;
  }}private static IEnumerable<TSource> ExceptIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer){
  Set<TSource> set = new Set<TSource>(comparer);
  foreach (TSource source in second)
    set.Add(source);
  foreach (TSource source in first)
  {
    if (set.Add(source))
      yield return source;
  }}

Answer 3

所有你能真正依赖的是，Enumerable方法是针对一般情况编写的，不会使用朴素算法。可能有第三方的东西（博客等）描述了实际使用的算法，但这些并不是官方的，也不是STL算法所保证的。

为了说明，这里是Enumerable.Count来自System.Core 的反映源代码（由ILSpy提供）：

// System.Linq.Enumerablepublic static int Count<TSource>(this IEnumerable<TSource> source){
    checked
    {
        if (source == null)
        {
            throw Error.ArgumentNull("source");
        }
        ICollection<TSource> collection = source as ICollection<TSource>;
        if (collection != null)
        {
            return collection.Count;
        }
        ICollection collection2 = source as ICollection;
        if (collection2 != null)
        {
            return collection2.Count;
        }
        int num = 0;
        using (IEnumerator<TSource> enumerator = source.GetEnumerator())
        {
            while (enumerator.MoveNext())
            {
                num++;
            }
        }
        return num;
    }}

正如您所看到的，它需要付出一些努力来避免简单地枚举每个元素的天真解决方案。