Почему WhereSelectArrayIterator не реализует ICollection?

Question

Глядя на System.Linq.Enumerable через Reflector, я заметил, что итератор по умолчанию, используемый для методов расширения Select и Where - WhereSelectArrayIterator - не реализует интерфейс ICollection. Если я правильно читаю код, это вызывает замедление работы некоторых других методов расширения, таких как Count() и ToList():

public static IEnumerable<TResult> Select<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector)
{
    // code above snipped
    if (source is List<TSource>)
    {
        return new WhereSelectListIterator<TSource, TResult>((List<TSource>) source, null, selector);
    }
    // code below snipped
}

private class WhereSelectListIterator<TSource, TResult> : Enumerable.Iterator<TResult>
{
    // Fields
    private List<TSource> source; // class has access to List source so can implement ICollection
    // code below snipped
}


public class List<T> : IList<T>, ICollection<T>, IEnumerable<T>, IList, ICollection, IEnumerable
{
public List(IEnumerable<T> collection)
{
    ICollection<T> is2 = collection as ICollection<T>;
    if (is2 != null)
    {
        int count = is2.Count;
        this._items = new T[count];
        is2.CopyTo(this._items, 0); // FAST
        this._size = count;
    }
    else
    {
        this._size = 0;
        this._items = new T[4];
        using (IEnumerator<T> enumerator = collection.GetEnumerator())
        {
            while (enumerator.MoveNext())
            {
                this.Add(enumerator.Current);  // SLOW, CAUSES ARRAY EXPANSION
            }
        }
    }
}

}

Я проверил это с результатами, подтверждающими мое подозрение:

ICollection: 2388,5222 мс

IEnumerable: 3308,3382 мс

Вот тестовый код:

    // prepare source
    var n = 10000;
    var source = new List<int>(n);
    for (int i = 0; i < n; i++) source.Add(i);

    // Test List creation using ICollection
    var startTime = DateTime.Now;
    for (int i = 0; i < n; i++)
    {
        foreach(int l in source.Select(k => k)); // itterate to make comparison fair
        new List<int>(source);
    }
    var finishTime = DateTime.Now;
    Response.Write("ICollection: " + (finishTime - startTime).TotalMilliseconds + " ms <br />");

    // Test List creation using IEnumerable
    startTime = DateTime.Now;
    for (int i = 0; i < n; i++) new List<int>(source.Select(k => k));
    finishTime = DateTime.Now;
    Response.Write("IEnumerable: " + (finishTime - startTime).TotalMilliseconds + " ms");

Я что-то упустил или это будет исправлено в будущих версиях фреймворка?

Спасибо за ваши мысли.

Answer 1

LINQ to Objects использует некоторые приемы для оптимизации определенных операций. Например, если вы соедините два .Where заявления вместе, предикаты будут объединены в единый WhereArrayIteratorтак что предыдущие могут быть собраны мусором. Аналогично, Where с последующим Select создаст WhereSelectArrayIterator, передавая объединенные предикаты в качестве аргумента, так что оригинал WhereArrayiterator можно собрать мусор. Итак WhereSelectArrayIterator отвечает за отслеживание не только selector, но и в сочетании predicate что это может или не может быть основано на.

source Поле отслеживает только начальный список, который был дан. Из-за предиката результат итерации не всегда будет иметь такое же количество элементов, как source делает. Поскольку LINQ предназначен для ленивой оценки, он не должен оценивать source против predicate заранее, просто так, чтобы потенциально сэкономить время, если кто-то в конечном итоге звонит .Count(), Это вызвало бы такой же удар по производительности, как и вызов .ToList() на него вручную, и если пользователь провел его через несколько Where а также Select пункты, вы бы в конечном итоге создать несколько списков без необходимости.

Может ли LINQ to Objects быть реорганизован для создания SelectArrayIterator что он использует, когда Select вызывается прямо на массиве? Конечно. Будет ли это повысить производительность? Совсем немного. По какой цене? Меньшее повторное использование кода означает дополнительный код для поддержки и тестирования продвижения вперед.

И, таким образом, мы добрались до сути подавляющего большинства вопросов "Почему у языка / платформы X нет функции Y": с ​​каждой функцией и оптимизацией связана некоторая стоимость, и даже у Microsoft нет неограниченных ресурсов. Как и любая другая компания, они делают суждения, чтобы определить, как часто будет выполняться код, который выполняет Select на массиве, а затем вызывает .ToList() на нем, и стоит ли делать это быстрее, стоит написать и поддерживать другой класс в пакете LINQ.