Оптимизация методов ToArray и ToList путём предоставления количества элементов

[novar]

Я считаю, чтобы обойти ограничения неэффективного IEnumerable<> (который возвращают все методы LINQ), проще доделать сам LINQ и автоматически получить лучшую производительность не изучая новых методов и не редактируя код. Как это сделать написАл в статье Улучшаем LINQ для работы с IReadOnly-коллекциями.

[Deranged]

Достаточно опасная конструкция, которая может принести проблемы в процессе поддержки кода.
Если вам нужна максимальная скорость — используйте unsafe fixed указатели, индексаторы, арифметику указателей, for циклы и т.д. Если нужно удобство и безопасность — LINQ + foreach. Умолчу о том сколько мусора генерируют конструкции LINQ в процессе исполнения.
По своему опыту могу сказать, что необходимость в экономии на спичках при создании приложения под .NET возникает крайне редко. Обычно при обработке мультимедиа, работе с БД на уровне BLOB'ов и т.д.

[PsyHaSTe]

Я писал такой экстеншн, просто нужно писать по-человечески, тогда и проблем не будет:

public static class LinqExtensions
{
    public static TResult[] SelectToArray<T, TResult>(this ICollection<T> source, Func<T, TResult> func)
    {
        if (source == null) 
            throw new ArgumentNullException("source");
        TResult[] result = new TResult[source.Count];
        int i = 0;
        foreach (var value in source)
        {
            result[i++] = func(value);
        }
        return result;
    }
}

В результате ничего опасного в этом коде нет, читается легко, передавать кол-во элементов не надо, сам умный, догадается. Ну а ToList можно оставить как есть — отдаем приблизительное количество элементов, если вдруг их будет больше, список расширится. В любом случае одна переаллокация лучше, чем несколько.

Остается написать только такие обертки для всех стандартных LINQ-методов, что займет полчаса, и потом пользоваться сколько душе угодно, радуясь возросшей на ровном месте производительности. Когда я работал с шейрпойнтом, возможность задать списку примерное количество элементов сказалось на скорости загрузки страницы в 3 раза — с 3 секунд до одной.

[PsyHaSTe]

Ну то есть не для всех, понятное дело, а только для тех, кто не изменяет количества элементов. А вот ToList можно написать для практически всех экстеншнов, т.к. потом можно посмотреть, сколько памяти занято, и если список ест много памяти, хотя заполнено мало, можно его просто вызвать TrimExcess.

[Charoplet]

Добавил этот вариант

[Charoplet]

Мне кажется это тут лишнее, так как буквально сегодня проверял, что будет если из пустой коллекции вызвать ToArray — возвращается пустой массив, и это как мне кажется логично.

Если эту проверку убрать, то при попытке создания массива с отрицательным размером выпадет OverflowException, что будет не очень понятно. А так мы сразу увидим, что проблема в параметре count

Насчет for — его не получится использовать, так как тогда внутри цикла придется писать:

array[i] = source[i];

А это даже не скомпилируется, потому что к IEnumerable нельзя обратиться по индексу

[Nagg]

List<User> users = GetUsers();
string[] array = users.Select(u => u.Name).ToArray(users.Count);

Не самый лучший пример — тут стандартный ToArray() справится без вашего экстеншна одим выделением. Надо было чтобы в примере GetUsers() возращал что-то не реализующее ICollection (правда проблема в том, что и вы сами _скорее всего_ не узнаете, сколько там элементов, если это не ICollection).

[kekekeks]

Select возвращает IEnumerable а не ICollection (хотя ничто и не мешало сделать его реализацию для WhereSelectListIterator).

[Nagg]

Уупс! Не досмотрел Select в листинге :)

[vba]

Немного оффтоп. Скажите пожалуйста, не попадалась ли кому-нибудь на глаза информация о вычислительной сложности всех linq-операций а не только ToArray/ToList?

[mayorovp]

Я вам так ее скажу — все операции я как-то просмотрел в декомпиляторе, это куда проще, чем искать информацию о них в инете. Поскольку результат оказался очень даже логичным — не вижу причин, чтобы вычислительная сложность внезапно поменялась.

Такие операции, как ToList, ToArray, ToDictionary и ToLookup, а также операции, возвращающие скалярное значение и обрабатывающие всю коллекцию — Min, Sum, Any и им подобные — имеют линейную сложность. Операции First и Single имеют константную сложность.

Операции Where и Select имеют условно-линейную сложность (я говорю «условно», потому что исполняются они лениво).

Операция SelectMany работает лениво, общая сложность — линейная относительно числа элементом на выходе.

Операция Join работает подобно SelectMany для первого аргумента, и подобно ToLookup — для второго (собственно, там, фактически, и делается сначала ToLookup над вторым аргументом, а потом SelectMany над первым). Общая сложность — линейная относительно суммы входов и выхода.

Операция GroupBy — это замаскированный ToLookup.

Что еще осталось?..

[Sane]

ToList, как отмечается в статье, все-таки NLogN из-за копирования.

[mayorovp]

Нет. Поскольку увеличение размера внутреннего массива выполняется по экспоненциальному закону — никакого логарифма не появляется. Последняя операция копирования «съедает» все предыдущие.

Кстати, ToArray реализован через ToList — поэтому ToList самый быстрый из методов материализации.

PS Вспомнил, чего не хватает. OrderBy выполняется на O(NLogN) — что неудивительно.

[GrigoryPerepechko]

OrderBy — квиксорт. У него худший случай O(N*N). Это не MergeSort
ToArray не реализован через ToList.
Про Single уже отписали

Если не помните — лучше не пишите. Народ ведь читает коментарии, и потом с умным видом на собеседованиях пересказывает. Экспоненциальный рост заблуждений, просто потому что кто-то не проверяет что пишет.

[mayorovp]

Среднее время выполнения быстрой сортировки — все-таки N log N. Про худший случай согласен.

По поводу ToArray — да, я ошибся, он не через ToList работает. Но алгоритм такой же, как если бы работал через ToList: все также есть массив, растущий удвоением размера, начиная с 4 — а в конце элементы копируются из него в итоговый массив.

[xXxVano]

Важно отметить что Single имеет константную сложность только в том случае, если не задан предикат. Если он задан, то сложность линейная.

[mayorovp]

Да, так и есть. Спасибо за уточнение.

[lair]

оба эти метода очень неэффективны, если они не знают количество элементов в последовательности (что почти всегда происходит, когда вы используете их в Linq-запросе).

Вопрос в том, откуда же взять это количество для более эффективных запросов — особенно в тех случаях, когда ToArray делается поверх IQueryable, чтобы добиться материализации, или просто поверх ленивого генератора/энумератора.

[RouR]

В методе ToArray не отлавливается ситуация когда source.Count > count. В итоге можно получить массив большего размера, чем ожидалось. Добавьте после цикла проверку if(i != count) throw new ArgumentOutOfRangeException();

[RouR]

Опечатка. Я про source.Count < count

[Charoplet]

Добавил

[Ordos]

Однако, в них есть кое-что беспокоящее меня: оба эти метода очень неэффективны, если они не знают количество элементов в последовательности

Как раз они знают про количество, т.к. эти методы в конечном итоге проверяют, а не реализует ли параметр IEnumerable[T] ещё и ICollection[T]. А если это так используют его свойство Count и метод CopyTo. (Что уж точно будет быстрее, чем вызывать Add в цикле)

[mayorovp]

Если коллекции сделать Select — то она перестает быть коллекцией, и информация о количестве теряется.