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

Question

我最近开始使用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

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

为了说明,这里是Enumerable.Count来自System.Core 的反映源代码(由ILSpy提供):

// System.Linq.Enumerable
public 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;
    }
}

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

Answer 3

我早就知道如果枚举是一个.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;
  }
}