首頁猿問 LINQ方法的運(yùn)行時(shí)復(fù)雜性（Big...

LINQ方法的運(yùn)行時(shí)復(fù)雜性（Big-O）有什么保證？

C# .NET

Cats萌萌 2019-08-06 16:43:12

LINQ方法的運(yùn)行時(shí)復(fù)雜性（Big-O）有什么保證？我最近開始使用LINQ了，我還沒有真正看到任何LINQ方法的運(yùn)行時(shí)復(fù)雜性。顯然，這里有很多因素在起作用，所以讓我們將討論局限于普通的IEnumerableLINQ-to-Objects提供者。此外，假設(shè)任何Func作為選擇器/ mutator /等傳入的是廉價(jià)的O（1）操作。它似乎很明顯，所有的單次操作（Select，Where，Count，Take/Skip，Any/All，等）將是O（n）的，因?yàn)樗麄冎恍枰叫械捻樞蛞淮? 雖然這甚至?xí)艿綉卸璧挠绊憽?duì)于更復(fù)雜的運(yùn)營(yíng)來說，事情變得更加模糊; 集合類運(yùn)算符（Union，Distinct，Except等）使用工作GetHashCode在默認(rèn)情況下（據(jù)我所知），所以它似乎是合理的假設(shè)他們使用一個(gè)哈希表內(nèi)，使這些操作為O（n）為好，一般。使用的版本怎么樣IEqualityComparer？OrderBy需要排序，所以很可能我們正在看O（n log n）。如果它已經(jīng)排序了怎么辦？如果我說OrderBy().ThenBy()并為兩者提供相同的密鑰怎么樣？我可以看到GroupBy（和Join）使用排序或散列。這是什么？Contains將是O（n）on a List，但是O（1）on a HashSet- LINQ檢查基礎(chǔ)容器以查看它是否可以加快速度？真正的問題 - 到目前為止，我一直堅(jiān)信運(yùn)營(yíng)是高效的。但是，我可以依靠嗎？例如，STL容器清楚地指定了每個(gè)操作的復(fù)雜性。.NET庫(kù)規(guī)范中的LINQ性能是否有類似的保證？更多問題（回應(yīng)評(píng)論）：沒有真正想過開銷，但我沒想到對(duì)于簡(jiǎn)單的Linq-to-Objects有很多。CodingHorror帖子討論的是Linq-to-SQL，在那里我可以理解解析查詢并使SQL增加成本 - 對(duì)象提供者也有類似的成本嗎？如果是這樣，如果您使用聲明性或功能性語法，它會(huì)有所不同嗎？

查看完整描述

3 回答

當(dāng)年話下

TA貢獻(xiàn)1890條經(jīng)驗(yàn) 獲得超9個(gè)贊

保證非常非常少，但有一些優(yōu)化：

使用索引訪問擴(kuò)展方法，比如ElementAt，Skip，Last或者LastOrDefault，將檢查底層式工具與否IList<T>，讓你得到O（1）訪問，而不是O（N）。
該Count方法檢查ICollection實(shí)現(xiàn)，以便該操作是O（1）而不是O（N）。
Distinct，GroupBy Join我相信set-aggregation方法（Union，Intersect和Except）也使用散列，所以它們應(yīng)該接近O（N）而不是O（N2）。
Contains檢查ICollection實(shí)現(xiàn)，因此如果底層集合也是O（1），它可能是O（1），例如a HashSet<T>，但這取決于實(shí)際的數(shù)據(jù)結(jié)構(gòu)，并且不能保證。散列集覆蓋了該Contains方法，這就是它們?yōu)镺（1）的原因。
OrderBy 方法使用穩(wěn)定的快速排序，因此它們是O（N log N）平均情況。

我認(rèn)為這涵蓋了大多數(shù)（如果不是全部）內(nèi)置擴(kuò)展方法。實(shí)際保證很少; Linq本身將嘗試?yán)酶咝У臄?shù)據(jù)結(jié)構(gòu)，但編寫可能效率低下的代碼并不是免費(fèi)的。

反對(duì) 回復(fù) 2019-08-06

胡說叔叔

TA貢獻(xiàn)1804條經(jīng)驗(yàn) 獲得超8個(gè)贊

我早就知道如果枚舉是一個(gè).Count()返回。.CountIList

但是我總是有點(diǎn)疲憊有關(guān)Set操作的運(yùn)行時(shí)間復(fù)雜度：.Intersect()，.Except()，.Union()。

這是針對(duì).Intersect()（評(píng)論我的）反編譯的BCL（.NET 4.0 / 4.5）實(shí)現(xiàn)：

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;
  }}

結(jié)論：

性能是O（M + N）
當(dāng)集合已經(jīng)設(shè)置時(shí)，實(shí)現(xiàn)不會(huì)占用優(yōu)勢(shì)。（它可能不一定是直截了當(dāng)?shù)?，因?yàn)槭褂眠^的也需要匹配。）IEqualityComparer<T>

為了完整起見，這里都為實(shí)現(xiàn).Union()和.Except()。

擾流板警報(bào)：它們也具有O（N + M） 復(fù)雜度。

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;
  }}

反對(duì) 回復(fù) 2019-08-06

慕的地8271018

TA貢獻(xiàn)1796條經(jīng)驗(yàn) 獲得超4個(gè)贊

所有你能真正依賴的是，Enumerable方法是針對(duì)一般情況編寫的，不會(huì)使用樸素算法?？赡苡械谌降臇|西（博客等）描述了實(shí)際使用的算法，但這些并不是官方的，也不是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;
    }}

正如您所看到的，它需要付出一些努力來避免簡(jiǎn)單地枚舉每個(gè)元素的天真解決方案。

反對(duì) 回復(fù) 2019-08-06