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

我最近开始大量使用 LINQ，并且我还没有真正看到任何 LINQ 方法的运行时复杂性。显然，这里有许多因素在起作用，因此让我们将讨论限制在简单的 IEnumerable LINQ-to-Objects 提供程序上。此外，让我们假设作为选择器/变异器等传入的任何 Func都是廉价的 O (1)操作。

显而易见，所有的单遍操作(Select、 Where、 Count、 Take/Skip、 Any/All等)都将是 O (n) ，因为它们只需要遍历序列一次; 尽管这也会受到惰性的影响。

对于更复杂的操作来说，情况更加模糊; 类似集合的操作符(Union、 Distinct、 Except等)默认使用 GetHashCode工作(afaik) ，因此假设它们在内部使用哈希表似乎是合理的，通常这些操作也是 O (n)。使用 IEqualityComparer的版本怎么样？

OrderBy需要排序，所以很可能是 O (n log n)。如果已经解决了呢？如果我说 OrderBy().ThenBy()并为两者提供相同的密钥怎么样？

我可以看到使用排序或散列的 GroupBy(和 Join)。是哪个？

Contains在 List上是 O (n) ，但在 HashSet上是 O (1)—— LINQ 是否检查底层容器，看看它是否能加快速度？

真正的问题是，到目前为止，我一直相信这些操作是可行的。不过，我能指望这一点吗？例如，STL 容器清楚地指定了每个操作的复杂性。中的 LINQ 性能是否有类似的保证。NET 库规范? ？

更多问题(回应评论) :
没有真正考虑过开销，但是我并不期望有很多简单的 Linq-to-Objects。CodingHorror 这篇文章讨论的是 Linq-to-SQL，在这里我可以理解解析查询和使用 SQL 会增加成本——对象提供程序也有类似的成本吗？如果是这样，那么使用声明式语法或函数式语法是否有所不同？

37008 次浏览
小开

您真正可以依赖的是，Enumable 方法是针对一般情况编写的，不会使用幼稚的算法。可能有第三方的东西(博客等)来描述实际使用的算法，但是这些并不是官方的或者在 STL 算法的意义上是保证的。

为了说明这一点，下面是 System.Core 中 Enumerable.Count的反射源代码(由 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;
}
}

正如您所看到的，为了避免简单地枚举每个元素这种幼稚的解决方案，我们做了一些努力。

小开

我刚打开了反射器，当调用 Contains时，他们确实检查了底层类型。

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);
}
小开
最佳答案

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

  • 使用索引访问的扩展方法(如 ElementAt、 Skip、 Last或 LastOrDefault)将检查底层类型是否实现了 IList<T>，以便您获得 O (1)访问而不是 O (N)访问。

  • Count方法检查 ICollection实现，因此此操作为 O (1)而不是 O (N)。

  • Distinct、 GroupBy、 Join和我认为集合聚合方法(Union、 Intersect和 Except)也使用散列，所以它们应该接近 O (N)而不是 O (N2)。

  • Contains检查 ICollection实现，所以如果底层集合也是 O (1) ，比如 HashSet<T>，那么 梅就是 O (1) ，但这取决于实际的数据结构，并不能保证。散列集覆盖 Contains方法，这就是它们为 O (1)的原因。

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

我认为它涵盖了大部分(如果不是全部的话)内置的扩展方法。确实很少有性能保证; Linq 本身会尝试利用有效的数据结构，但它并不是编写潜在低效代码的免费通行证。

小开

正确答案是“视情况而定”。它取决于基础 IEnumable 的类型。我知道对于一些集合(比如实现 ICollection 或 IList 的集合)有一些特殊的代码路径，但是实际的实现并不能保证做任何特殊的事情。例如，我知道 ElementAt ()对于可索引的集合有一个特殊的用例，类似于 Count ()。但是一般来说，你可能应该假设最坏的情况 O (n)性能。

一般来说，我不认为你会找到你想要的性能保证，但是如果你遇到了一个特定的性能问题，你总是可以为你的特定集合重新实现它。此外，还有许多博客和扩展性项目将 Linq 扩展到 Object，以添加这类性能保证。检查 索引 LINQ，它扩展和增加了操作员集更多的性能好处。

小开

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

但是我总是对 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;
}
}

提交答案