Я совсем недавно начал использовать LINQ, и я действительно не встречал упоминания о сложности времени выполнения для любого из методов LINQ. Очевидно, здесь играет роль множество факторов, поэтому давайте ограничимся обсуждением простого IEnumerable
поставщика LINQ-to-Objects. Далее, давайте предположим, что любой Func
переданный в качестве селектора / мутатора / т. Д. Является дешевой операцией O (1).
Представляется очевидным , что все операции за один проход ( Select
, Where
, Count
, Take/Skip
, Any/All
и т.д.) будет O (п), так как они только должны пройти последовательность один раз; хотя даже это подвержено лени.
Для более сложных операций дела обстоят еще мрачнее; множество подобных операторов ( Union
, Distinct
, Except
и т.д.) работы с использованием GetHashCode
по умолчанию (AFAIK), так что кажется разумным предположить , что они используют хэш-таблицу внутри, что делает эти операции O (п), а также , в целом. А как насчет версий, в которых используется IEqualityComparer
?
OrderBy
потребуется сортировка, поэтому, скорее всего, мы смотрим на O (n log n). Что делать, если он уже отсортирован? Как насчет того, чтобы я сказал OrderBy().ThenBy()
и предоставил один и тот же ключ обоим?
Я мог видеть GroupBy
(и Join
) использовать либо сортировку, либо хеширование. Что это?
Contains
будет O (n) на a List
, но O (1) на a HashSet
- проверяет ли LINQ базовый контейнер, чтобы узнать, может ли он ускорить работу?
И реальный вопрос - до сих пор я полагаю, что операции производительны. Однако могу ли я на это рассчитывать? Например, контейнеры STL четко определяют сложность каждой операции. Есть ли аналогичные гарантии производительности LINQ в спецификации библиотеки .NET?
Еще вопрос (в ответ на комментарии): на
самом деле не думал об накладных расходах, но я не ожидал, что будет много простых Linq-to-Objects. В сообщении CodingHorror говорится о Linq-to-SQL, где я могу понять, что синтаксический анализ запроса и создание SQL увеличат стоимость - есть ли аналогичная стоимость для поставщика объектов? Если да, то отличается ли это от использования декларативным или функциональным синтаксисом?
Ответы:
Гарантий очень и очень мало, но есть несколько оптимизаций:
Методы расширения , которые используют индексный доступ, такие как
ElementAt
,Skip
,Last
илиLastOrDefault
, будет проверять, действительно ли основные орудия типаIList<T>
, так что вы получите O (1) доступ вместо O (N).В
Count
метод проверяет дляICollection
реализации, так что эта операция представляет собой О (1) вместо O (N).Distinct
,,GroupBy
Join
и я считаю, что методы агрегирования наборов (Union
,Intersect
иExcept
) используют хеширование, поэтому они должны быть близки к O (N) вместо O (N²).Contains
проверяетICollection
реализацию, поэтому это может быть O (1), если базовая коллекция также O (1), например aHashSet<T>
, но это зависит от фактической структуры данных и не гарантируется. Хеш-наборы переопределяютContains
метод, поэтому они равны O (1).OrderBy
методы используют стабильную быструю сортировку, поэтому их средний случай составляет O (N log N).Я думаю, что это касается большинства, если не всех встроенных методов расширения. На самом деле гарантий производительности очень мало; Сам Linq попытается воспользоваться преимуществами эффективных структур данных, но это не бесплатный пропуск для написания потенциально неэффективного кода.
источник
IEqualityComparer
перегрузок?IEqualityComparer
, я не могу заставить его повлиять на асимптотическую сложность.EqualityComparer
орудияGetHashCode
так же хорошо, какEquals
; но, конечно, в этом есть смысл.Orderby().ThenBy()
ещеN logN
или это(N logN) ^2
или что-то в этом роде?Я давно знаю, что
.Count()
возвращается,.Count
если перечисление являетсяIList
.Но я всегда был немного уставший о времени выполнения сложности операций Set:
.Intersect()
,.Except()
,.Union()
.Вот декомпилированная реализация BCL (.NET 4.0 / 4.5) для
.Intersect()
(мои комментарии):Выводы:
IEqualityComparer<T>
также должен совпадать.)Для полноты, вот реализации для
.Union()
и.Except()
.Спойлер: они тоже имеют O (N + M) сложность.
источник
Все, на что вы действительно можете положиться, это то, что методы Enumerable хорошо написаны для общего случая и не будут использовать наивные алгоритмы. Вероятно, существуют сторонние материалы (блоги и т. Д.), Которые описывают фактически используемые алгоритмы, но они не являются официальными и не гарантируются в том смысле, в каком есть алгоритмы STL.
Чтобы проиллюстрировать это, вот отраженный исходный код (любезно предоставленный ILSpy) для
Enumerable.Count
System.Core:Как видите, прилагаются некоторые усилия, чтобы избежать наивного решения простого перечисления каждого элемента.
источник
Enumerable.Count
он не повторяется, если нет очевидной альтернативы. Как бы вы сделали его менее наивным?Я только что выломал рефлектор, и они проверяют базовый тип при
Contains
вызове.источник
Правильный ответ - это зависит от обстоятельств. это зависит от типа базового IEnumerable. Я знаю, что для некоторых коллекций (например, коллекций, реализующих ICollection или IList) используются специальные пути кода, однако фактическая реализация не гарантирует ничего особенного. например, я знаю, что ElementAt () имеет особый случай для индексируемых коллекций, аналогично Count (). Но в целом вам, вероятно, следует предположить наихудшую производительность O (n).
В целом я не думаю, что вы найдете те гарантии производительности, которые вам нужны, хотя, если вы столкнетесь с конкретной проблемой производительности с оператором linq, вы всегда можете просто переопределить его для своей конкретной коллекции. Также существует множество блогов и проектов расширяемости, которые расширяют Linq до объектов, чтобы добавить такие гарантии производительности. ознакомьтесь с индексированным LINQ, который расширяет и дополняет набор операторов для получения дополнительных преимуществ в производительности.
источник