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