在哪些情況下IEnumerable <T> .Count優化？

Question

使用reflector我注意到System.Linq.Enumerable.Count方法有一個條件來優化IEnumerable<T>實際上是ICollection<T>。如果轉換成功，則Count方法不需要遍歷每個元素，但可以調用ICollection的Count方法。

在此基礎上，我開始認爲IEnumerable<T>可以像一個集合的只讀視圖中使用，而不必我原先預期的基礎上IEnumerable<T>

的API我很感興趣，能否優化的性能損失的Count仍然成立時，IEnumerable<T>是Select聲明超過ICollection的結果，但基於反射的代碼，這種情況沒有優化，並且需要遍歷所有元素。

你是否從反射器得出了相同的結論？缺乏這種優化的原因可能是什麼？我似乎在這個普通的操作中浪費了很多時間。規格是否需要即使沒有這樣做可以確定計數，每個元素都會被評估？

Answer 1

延期評估Select的結果並不重要。 Count總是等於原始集合的計數，因此可以通過從Select返回可用於短路評估Count方法的特定對象直接檢索它。

它不是可以從一些與確定的數量（如List<T>）優化了Count()方法的評價上Select調用的返回值的原因是，它可以改變程序的含義。

的selector功能傳遞給Select方法允許有副作用和它的副作用是必需的確定性地發生，以預定的順序。

假設：

new[]{1,2,3}.Select(i => { Console.WriteLine(i); return 0; }).Count(); 

文檔需要此代碼打印

即使計數真的從一開始就知並可以優化，優化會改變程序的行爲。這就是爲什麼你無法避免枚舉集合的原因。這正是編譯器優化在純粹的函數式語言中更容易的原因之一。

---

UPDATE：顯然，目前還不清楚，這是完全可能實現Select和Count使Select S於ICollection<T>仍然會懶洋洋地評估，但Count()將在O（1）無需枚舉進行評估採集。我將在不更改任何方法的接口的情況下執行此操作。類似的事情已經爲ICollection<T>完成：

private interface IDirectlyCountable { 
    int Count {get;} 
} 
private class SelectICollectionIterator<TSource,TResult> : IEnumerable<T>, IDirectlyCountable { 
    ICollection<TSource> sequence; 
    Func<TSource,TResult> selector; 
    public SelectICollectionIterator(ICollection<TSource> source, Func<TSource,TResult> selector) { 
     this.sequence = source; 
     this.selector = selector; 
    } 
    public int Count { get { return sequence.Count; } } 
    // ... GetEnumerator ... 
} 
public static IEnumerable<TResult> Select<TSource,TResult>(this IEnumerable<TSource> source, Func<TSource,TResult> selector) { 
    // ... error handling omitted for brevity ... 
    if (source is ICollection<TSource>) 
     return new SelectICollectionIterator<TSource,TResult>((ICollection<TSource>)source, selector); 
    // ... rest of the method ... 
} 
public static int Count<T>(this IEnumerable<T> source) { 
    // ... 
    ICollection<T> collection = source as ICollection<T>; 
    if (collection != null) return collection.Count; 
    IDirectlyCountable countableSequence = source as IDirectlyCountable; 
    if (countableSequence != null) return countableSequence.Count; 
    // ... enumerate and count the sequence ... 
} 

這仍然將評估Count懶洋洋地。如果您更改了基礎集合，則計數將發生變化並且序列不會被緩存。唯一的區別是不會在selector委託中做副作用。

Answer 2

一個ICollection知道它包含的項目數（計數）。它不必迭代任何項目來確定它。以HashSet班（實施ICollection）爲例。

一個IEnumerable<T>不知道它包含多少項。您必須枚舉整個列表以確定項目數量（計數）。

在LINQ語句中包裝ICollection並不會使其效率更高。無論你如何扭轉，ICollection將不得不被列舉。

Answer 3

編輯02 - 2010：

在我看來，至少有兩種方法來解釋這個問題。

爲什麼該Select<T, TResult>擴展方法中，當 上的類的一個實例稱爲該 實現ICollection<T>，不 返回其提供 Count屬性的對象;以及爲什麼 Count<T>擴展方法不是 檢查此屬性，以便當 方法鏈接時提供O（1）性能？

這個版本的問題，使有關LINQ的擴展是如何工作的任何虛假假設，是因爲到ICollection<T>.Select.Count一個呼叫，畢竟，總是返回相同的值ICollection<T>.Count一個有效的問題。這就是梅爾達德對這個問題的解釋，他已經提供了一個徹底的迴應。

但我將問題閱讀爲詢問...

如果Count<T>擴展方法一類的一個目的 實施ICollection<T>提供O（1） 性能，爲什麼 它提供爲O（n）的性能爲 的 Select<T, TResult> 延伸的返回值方法？

在這個版本的問題，有一個錯誤的假設：即LINQ的擴展方法通過組裝的小集合後，一個又一個（在內存中），並通過IEnumerable<T>接口暴露他們一起工作。

如果是這樣的LINQ的擴展是如何工作的，該Select方法可能是這個樣子：

public static IEnumerable<TResult> Select<T, TResult>(this IEnumerable<T> source, Func<T, TResult> selector) { 
    List<TResult> results = new List<TResult>(); 

    foreach (T input in source) 
     results.Add(selector(input)); 

    return results; 
} 

而且，如果這是的Select實施，我想你會發現大部分的代碼，利用這種方法會表現得完全一樣。但這樣做會很浪費，而且事實上會在我的原始答案中描述的某些情況下導致例外。

在現實中，我相信Select方法的實現是非常接近這樣的事情：

public static IEnumerable<TResult> Select<T, TResult>(this IEnumerable<T> source, Func<T, TResult> selector) { 
    foreach (T input in source) 
     yield return selector(input); 

    yield break; 
} 

這是爲了提供懶惰的評價，並解釋了爲什麼Count屬性不爲O訪問（1 ）時間到Count方法。

換句話說

所以，而邁赫達德回答爲什麼Select沒有設計不同，這樣Select.Count會表現不同的的問題，我提出我的最佳答案的的問題，爲什麼Select.Count的行爲方式，是否。

---

原來的答案：

方法的副作用是沒有答案的。

根據邁赫達德的回答是：

這其實並不重要的是選擇的 結果懶洋洋地評估。

我不買這個。讓我解釋一下爲什麼。

對於初學者來說，可以考慮以下兩個非常相似的方法：

public static IEnumerable<double> GetRandomsAsEnumerable(int N) { 
    Random r = new Random(); 

    for (int i = 0; i < N; ++i) 
     yield return r.NextDouble(); 

    yield break; 
} 

public static double[] GetRandomsAsArray(int N) { 
    Random r = new Random(); 

    double[] values = new double[N]; 
    for (int i = 0; i < N; ++i) 
     values[i] = r.NextDouble(); 

    return values; 
} 

OK，就這些方法做什麼？每個用戶都會返回任意數量的隨機雙打（最多可達int.MaxValue）。這兩種方法是否被懶惰地評估過或者沒有關係？要回答這個問題，我們來看看下面的代碼：

public static double Invert(double value) { 
    return 1.0/value; 
} 

public static void Test() { 
    int a = GetRandomsAsEnumerable(int.MaxValue).Select(Invert).Count(); 
    int b = GetRandomsAsArray(int.MaxValue).Select(Invert).Count(); 
} 

你猜這兩個方法調用會發生什麼嗎？讓我饒了你將該代碼複製，並測試它自己的麻煩：

的第一變量，a，將（之後的時間可能顯著量）被初始化爲int.MaxValue（目前2147483647）。 second one，b，很可能會被OutOfMemoryException打斷。

由於Select和其他Linq擴展方法是懶惰評估，它們允許你做你根本無法做的事情。以上是一個相當平凡的例子。但我的主要觀點是質疑懶惰評估並不重要。 Mehrdad的聲明說，一個Count財產「從一開始就真正知道並且可以優化」實際上引發了這個問題。 Select方法可能看起來很簡單，但Select並不是特別的;它返回一個IEnumerable<T>就像Linq擴展方法的其餘部分一樣，對於這些方法來「知道」Count的返回值需要完整的集合才能被緩存，因此禁止懶惰評估。

懶惰評價就是答案。

由於這個原因，我不得不同意一位原來的迴應者（他們的回答現在似乎已經消失），懶惰的評估真的是這裏的答案。方法副作用需要考慮的觀點實際上是次要的，因爲無論如何，這已經被確保爲副作用。

後記：我做出了非常自信的陳述，並強調了我的觀點，主要是因爲我想澄清我的論點是什麼，而不是對任何其他反應（包括Mehrdad的）的任何不敬，錯過了商標。