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

我最近开始使用LINQ相当多,而且我还没有看到任何LINQ方法的运行时复杂性。 很明显,这里有很多因素,所以让我们把讨论限制在纯IEnumerable LINQ-to-Objects提供程序中。 此外,假设任何作为select器/增变器等传入的Func都是便宜的O(1)操作。

似乎很明显,所有的单程操作( SelectWhereCountTake/SkipAny/All等)都是O(n),因为他们只需要走一次序列; 虽然这是懒惰。

对于更复杂的操作,情况会更加恶劣。 集合类运算符( UnionDistinctExcept等)默认使用GetHashCode (afaik),所以假设他们在内部使用哈希表似乎是合理的,也使得这些操作O(n)一般来说。 那么使用IEqualityComparer的版本呢?

OrderBy需要sorting,所以很可能我们看O(n log n)。 如果它已经分类? 如果我说OrderBy().ThenBy()并提供相同的密钥?

我可以看到GroupBy (和Join )使用sorting或哈希。 这是哪个?

ContainsList O(n),但O(1)在HashSet – 是否LINQ检查底层容器,看看它是否可以加快速度?

而真正的问题 – 到目前为止,我一直坚信这个操作是高性能的。 但是,我可以在这个银行? 例如,STL容器清楚地说明了每个操作的复杂性。 .NET库规范中的LINQ性能有没有类似的保证?

更多的问题(回复评论):
没有真正考虑开销,但我没想到对于简单的Linq-to-Objects来说还有很多。 CodingHorror文章谈论Linq到SQL,在那里我可以理解parsing查询,并使SQL会增加成本 – 对象提供者也有类似的成本? 如果是这样,如果你使用声明性或function性语法,它是不同的?

有很less的保证,但有几个优化:

  • 使用索引访问的扩展方法(如ElementAtSkipLastLastOrDefault )将检查基础types是否实现IList<T> ,以便获得O(1)访问而不是O(N)。

  • Count方法检查ICollection实现,所以这个操作是O(1)而不是O(N)。

  • DistinctGroupBy Join ,我也相信集合聚合方法( UnionIntersectExcept )使用散列,所以它们应该接近O(N)而不是O(N²)。

  • ContainsICollection实现的检查,因此如果底层集合也是O(1)(如HashSet<T> ),则它可能是O(1),但这取决于实际的数据结构并且不能保证。 哈希集重写Contains方法,这就是为什么他们是O(1)。

  • OrderBy方法使用稳定的快速sorting,因此它们是O(N log N)平均情况。

我认为这涵盖了大部分(如果不是全部)内置的扩展方法。 确实有很less的性能保证。 Linq本身将尝试利用高效的数据结构,但是写入潜在的低效代码并不是一个自由通行证。

所有你可以真正存储的是Enumerable方法是写得很好的一般情况下,不会使用天真的algorithm。 有可能是第三方的东西(博客等),描述了实际使用的algorithm,但这些都不是官方的或STLalgorithm的保证。

为了说明,这里是来自System.Core的Enumerable.Count的reflection源代码(由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; } } 

正如你所看到的,为了避免简单列举每一个元素的简单解决scheme,需要做一些努力。

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

但是我总是对Set操作的运行时复杂.Intersect()到厌倦: .Intersect() .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() ,下面是.Union().Union()的实现。

扰stream警报:它们也具有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; } } 

我刚爆发了reflection器,当Contains被调用时,他们检查底层types。

 public static bool Contains<TSource>(this IEnumerable<TSource> source, TSource value) { ICollection<TSource> is2 = source as ICollection<TSource>; if (is2 != null) { return is2.Contains(value); } return source.Contains<TSource>(value, null); } 

正确的答案是“这取决于”。 它取决于底层的IEnumerable是什么types。 我知道对于一些集合(如实现ICollection或IList的集合),有特殊的代码path被使用,但是实际的实现不保证做任何特殊的事情。 例如我知道ElementAt()有一个可索引集合的特殊情况,类似于Count()。 但总的来说,你可能应该承担最糟糕的O(n)performance。

一般来说,我不认为你会find你想要的性能保证types,但如果你遇到一个linq运算符的特定性能问题,你总是可以为你的特定集合重新实现它。 还有很多博客和扩展项目,将Linq扩展到对象以添加这些性能保证。 检查索引LINQ ,它扩展并添加到操作集中以获得更多性能优势。