LINQ方法的运行时间复杂度（Big-O）有哪些保证？

Question

我最近开始大量使用LINQ，但没有看到任何有关任何LINQ方法的运行时复杂度的提及。显然，这里有许多因素，因此让我们将讨论限制在普通的IEnumerable LINQ-to-Objects提供程序上。另外，让我们假设作为选择器/变异器/等的任何Func都是廉价的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在List上是O(n)，但在HashSet上是O(1)——LINQ会检查底层容器以查看是否可以加快速度吗？

真正的问题是——到目前为止，我一直信任操作的高性能。例如STL容器明确指定了每个操作的复杂度。在.NET库规范中是否有类似的LINQ性能保证？

更多问题（回复评论）：
我没有考虑过开销，但我认为简单的Linq-to-Objects不会有太多开销。CodingHorror的帖子谈到了Linq-to-SQL，我可以理解解析查询并生成SQL会增加成本 - 对于对象提供程序是否存在类似的成本？如果存在，使用声明式语法和函数式语法是否不同？

- tzaman

---

虽然我无法真正回答你的问题，但我想评论一下，通常性能的大部分将与核心功能相比是“开销”。当然，在您拥有非常大的数据集（> 10k项）时，情况并非如此，因此我很好奇您想知道哪种情况。 - Henri

回复：“如果您使用声明式或函数式语法，是否有所不同？” - 编译器将声明式语法转换为函数式语法，因此它们是相同的。 - John Rasch

STL容器清晰地指定了每个操作的复杂度。.NET容器也清晰地指定了每个操作的复杂度。Linq扩展类似于STL算法，而不是STL容器。就像在STL容器上应用STL算法时一样，您需要将Linq扩展的复杂性与.NET容器操作的复杂性结合起来，以正确分析结果的复杂性。这包括考虑模板特化，正如Aaronaught的答案所提到的那样。 - Tim Sparkles

一个潜在的问题是，为什么微软不更关心 IList<T> 优化的效用有限，因为开发人员如果依赖它来提高性能，就必须依赖于未记录的行为。 - Edward Brey

在结果集List上使用AsParallel()应该会给你 ~O(1) < O(n)。 - Latency

Answer 1

虽然几乎没有什么保证，但有一些优化：

• 使用索引访问的扩展方法，如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(N²)。

• Contains 检查是否实现了ICollection，因此如果底层集合也是O(1)，如HashSet<T>，则它可能是O(1)，但这取决于实际数据结构，不能保证。哈希集覆盖了Contains方法，所以它们是O(1)。

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

我认为这覆盖了大多数内置扩展方法。虽然Linq本身会尝试利用有效的数据结构，但它并不是编写潜在低效代码的免费通行证。

- Aaronaught

---

哦，对了。我没有意识到EqualityComparer实现了GetHashCode和Equals；但当然这是很有道理的。 - tzaman

我认为Join的时间复杂度是O(MN)。 - imgen

@imgen: 循环连接的时间复杂度为O(N*M)，对于不相关的数据集，这将推广到O(N²)。LINQ使用哈希连接，其时间复杂度为O(N+M)，可以推广到O(N)。这假设使用了一个合理的哈希函数，在.NET中很难出错。 - Aaronaught

谢谢，太棒了，我不知道Join可以这么高效。感谢你的提示。 - imgen

Orderby().ThenBy()仍然是N logN吗？还是(N logN) ^2或类似的东西？ - M.kazem Akhgary

Answer 2

我一直知道如果枚举是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;
  }
}

- Cristian Diaconescu

Answer 3

你能依赖的只有Enumerable方法在一般情况下是写得很好的，不会使用简单的算法。可能有第三方的东西（博客等）描述了实际使用的算法，但这些并不是官方的或者像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;
    }
}

正如您所看到的，它会尽力避免简单枚举每个元素的幼稚解决方案。

- Marcelo Cantos

---

对于一个IEnnumerable对象，遍历整个对象以获取Count()似乎对我来说太幼稚了... - Zonko

@Zonko：我不明白你的观点。我已经修改了我的答案，以显示Enumerable.Count只有在没有明显的替代方案时才会迭代。你会如何使它更不幼稚？ 我已修改我的答案以表明“Enumerable.Count”只有在没有明显替代方案时才进行迭代。请问您有什么更好的建议，让我的回答更加专业？ - Marcelo Cantos

是的，根据源代码实现的方法是最有效的。然而，最有效的方法有时是一个天真的算法，使用linq时应该小心，因为它隐藏了调用的真正复杂性。如果您不熟悉您正在操作的对象的基本结构，您可能会轻易地使用错误的方法来满足您的需求。 - Zonko

@MarceloCantos 为什么不处理数组呢？对于ElementAtOrDefault方法也是一样的。 http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,0bd04e5c179c3c7d - Freshblood

@Freshblood 他们是的。（数组实现ICollection。）不过我不确定ElementAtOrDefault，我猜数组也实现了ICollection<T>，但是我的.Net知识有些生疏了。 - Marcelo Cantos

Answer 4

我刚刚使用了反射器，当调用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);
}

- ChaosPandion

Answer 5

正确答案是“这取决于”。这取决于基础的IEnumerable类型。我知道，对于一些集合（如实现ICollection或IList的集合），会使用特殊的代码路径，但实际实现不能保证执行任何特殊的操作。例如，我知道ElementAt()针对可索引集合有一个特殊情况，Count()也是一样。但总的来说，您应该假定最坏的情况是O(n)的性能。

总的来说，我认为您不太可能找到您想要的性能保证，尽管如果您遇到特定的Linq运算符的性能问题，您可以为自己的特定集合重新实现它。此外，还有许多博客和可扩展性项目将Linq to Objects扩展到添加这些性能保证。请查看Indexed LINQ，它扩展并添加了运算符集以获得更多的性能优势。

- luke