Комментарии 27
Я считаю, чтобы обойти ограничения неэффективного IEnumerable<> (который возвращают все методы LINQ), проще доделать сам LINQ и автоматически получить лучшую производительность не изучая новых методов и не редактируя код. Как это сделать написАл в статье Улучшаем LINQ для работы с IReadOnly-коллекциями.
Достаточно опасная конструкция, которая может принести проблемы в процессе поддержки кода.
Если вам нужна максимальная скорость — используйте unsafe fixed указатели, индексаторы, арифметику указателей, for циклы и т.д. Если нужно удобство и безопасность — LINQ + foreach. Умолчу о том сколько мусора генерируют конструкции LINQ в процессе исполнения.
По своему опыту могу сказать, что необходимость в экономии на спичках при создании приложения под .NET возникает крайне редко. Обычно при обработке мультимедиа, работе с БД на уровне BLOB'ов и т.д.
Если вам нужна максимальная скорость — используйте unsafe fixed указатели, индексаторы, арифметику указателей, for циклы и т.д. Если нужно удобство и безопасность — LINQ + foreach. Умолчу о том сколько мусора генерируют конструкции LINQ в процессе исполнения.
По своему опыту могу сказать, что необходимость в экономии на спичках при создании приложения под .NET возникает крайне редко. Обычно при обработке мультимедиа, работе с БД на уровне BLOB'ов и т.д.
Я писал такой экстеншн, просто нужно писать по-человечески, тогда и проблем не будет:
В результате ничего опасного в этом коде нет, читается легко, передавать кол-во элементов не надо, сам умный, догадается. Ну а ToList можно оставить как есть — отдаем приблизительное количество элементов, если вдруг их будет больше, список расширится. В любом случае одна переаллокация лучше, чем несколько.
Остается написать только такие обертки для всех стандартных LINQ-методов, что займет полчаса, и потом пользоваться сколько душе угодно, радуясь возросшей на ровном месте производительности. Когда я работал с шейрпойнтом, возможность задать списку примерное количество элементов сказалось на скорости загрузки страницы в 3 раза — с 3 секунд до одной.
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 секунд до одной.
Ну то есть не для всех, понятное дело, а только для тех, кто не изменяет количества элементов. А вот ToList можно написать для практически всех экстеншнов, т.к. потом можно посмотреть, сколько памяти занято, и если список ест много памяти, хотя заполнено мало, можно его просто вызвать TrimExcess.
Добавил этот вариант
Мне кажется это тут лишнее, так как буквально сегодня проверял, что будет если из пустой коллекции вызвать ToArray — возвращается пустой массив, и это как мне кажется логично.
Если эту проверку убрать, то при попытке создания массива с отрицательным размером выпадет OverflowException, что будет не очень понятно. А так мы сразу увидим, что проблема в параметре count
Насчет for — его не получится использовать, так как тогда внутри цикла придется писать:
array[i] = source[i];А это даже не скомпилируется, потому что к IEnumerable нельзя обратиться по индексу
List<User> users = GetUsers();
string[] array = users.Select(u => u.Name).ToArray(users.Count);
Не самый лучший пример — тут стандартный ToArray() справится без вашего экстеншна одим выделением. Надо было чтобы в примере GetUsers() возращал что-то не реализующее ICollection (правда проблема в том, что и вы сами _скорее всего_ не узнаете, сколько там элементов, если это не ICollection).
Select возвращает IEnumerable а не ICollection (хотя ничто и не мешало сделать его реализацию для WhereSelectListIterator).
Немного оффтоп. Скажите пожалуйста, не попадалась ли кому-нибудь на глаза информация о вычислительной сложности всех linq-операций а не только ToArray/ToList?
Я вам так ее скажу — все операции я как-то просмотрел в декомпиляторе, это куда проще, чем искать информацию о них в инете. Поскольку результат оказался очень даже логичным — не вижу причин, чтобы вычислительная сложность внезапно поменялась.
Такие операции, как ToList, ToArray, ToDictionary и ToLookup, а также операции, возвращающие скалярное значение и обрабатывающие всю коллекцию — Min, Sum, Any и им подобные — имеют линейную сложность. Операции First и Single имеют константную сложность.
Операции Where и Select имеют условно-линейную сложность (я говорю «условно», потому что исполняются они лениво).
Операция SelectMany работает лениво, общая сложность — линейная относительно числа элементом на выходе.
Операция Join работает подобно SelectMany для первого аргумента, и подобно ToLookup — для второго (собственно, там, фактически, и делается сначала ToLookup над вторым аргументом, а потом SelectMany над первым). Общая сложность — линейная относительно суммы входов и выхода.
Операция GroupBy — это замаскированный ToLookup.
Что еще осталось?..
Такие операции, как ToList, ToArray, ToDictionary и ToLookup, а также операции, возвращающие скалярное значение и обрабатывающие всю коллекцию — Min, Sum, Any и им подобные — имеют линейную сложность. Операции First и Single имеют константную сложность.
Операции Where и Select имеют условно-линейную сложность (я говорю «условно», потому что исполняются они лениво).
Операция SelectMany работает лениво, общая сложность — линейная относительно числа элементом на выходе.
Операция Join работает подобно SelectMany для первого аргумента, и подобно ToLookup — для второго (собственно, там, фактически, и делается сначала ToLookup над вторым аргументом, а потом SelectMany над первым). Общая сложность — линейная относительно суммы входов и выхода.
Операция GroupBy — это замаскированный ToLookup.
Что еще осталось?..
ToList, как отмечается в статье, все-таки NLogN из-за копирования.
Нет. Поскольку увеличение размера внутреннего массива выполняется по экспоненциальному закону — никакого логарифма не появляется. Последняя операция копирования «съедает» все предыдущие.
Кстати, ToArray реализован через ToList — поэтому ToList самый быстрый из методов материализации.
PS Вспомнил, чего не хватает. OrderBy выполняется на O(NLogN) — что неудивительно.
Кстати, ToArray реализован через ToList — поэтому ToList самый быстрый из методов материализации.
PS Вспомнил, чего не хватает. OrderBy выполняется на O(NLogN) — что неудивительно.
OrderBy — квиксорт. У него худший случай O(N*N). Это не MergeSort
ToArray не реализован через ToList.
Про Single уже отписали
Если не помните — лучше не пишите. Народ ведь читает коментарии, и потом с умным видом на собеседованиях пересказывает. Экспоненциальный рост заблуждений, просто потому что кто-то не проверяет что пишет.
ToArray не реализован через ToList.
Про Single уже отписали
Если не помните — лучше не пишите. Народ ведь читает коментарии, и потом с умным видом на собеседованиях пересказывает. Экспоненциальный рост заблуждений, просто потому что кто-то не проверяет что пишет.
Среднее время выполнения быстрой сортировки — все-таки N log N. Про худший случай согласен.
По поводу ToArray — да, я ошибся, он не через ToList работает. Но алгоритм такой же, как если бы работал через ToList: все также есть массив, растущий удвоением размера, начиная с 4 — а в конце элементы копируются из него в итоговый массив.
По поводу ToArray — да, я ошибся, он не через ToList работает. Но алгоритм такой же, как если бы работал через ToList: все также есть массив, растущий удвоением размера, начиная с 4 — а в конце элементы копируются из него в итоговый массив.
Важно отметить что Single имеет константную сложность только в том случае, если не задан предикат. Если он задан, то сложность линейная.
оба эти метода очень неэффективны, если они не знают количество элементов в последовательности (что почти всегда происходит, когда вы используете их в Linq-запросе).
Вопрос в том, откуда же взять это количество для более эффективных запросов — особенно в тех случаях, когда
ToArray делается поверх IQueryable, чтобы добиться материализации, или просто поверх ленивого генератора/энумератора.
В методе ToArray не отлавливается ситуация когда source.Count > count. В итоге можно получить массив большего размера, чем ожидалось. Добавьте после цикла проверку if(i != count) throw new ArgumentOutOfRangeException();
Однако, в них есть кое-что беспокоящее меня: оба эти метода очень неэффективны, если они не знают количество элементов в последовательности
Как раз они знают про количество, т.к. эти методы в конечном итоге проверяют, а не реализует ли параметр IEnumerable[T] ещё и ICollection[T]. А если это так используют его свойство Count и метод CopyTo. (Что уж точно будет быстрее, чем вызывать Add в цикле)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Оптимизация методов ToArray и ToList путём предоставления количества элементов