Какие гарантии находятся там на сложности во время выполнения (Большой-O) из методов LINQ?
Я недавно начал использовать LINQ вполне немного, и я действительно не видел упоминания о сложности во время выполнения ни для одного из методов LINQ. Очевидно, существует много факторов в действии здесь, поэтому давайте ограничим обсуждение плоскостью IEnumerable Поставщик LINQ к объектам. Далее, давайте предположим что любой Func переданный в как селектор / мутатор / и т.д. является дешевым O (1) операция.
Кажется очевидным что все однопроходные операции (Select, Where, Count, Take/Skip, Any/All, и т.д.), будет O (n), так как они только должны обойти последовательность однажды; хотя даже это подвергается лени.
Вещи более темны для более сложных операций; подобные набору операторы (Union, Distinct, Except, и т.д.) использование работы GetHashCode по умолчанию (afaik), таким образом, кажется разумным предположить, что они используют хеш-таблицу внутренне, делая эти операции O (n) также, в целом. Что относительно версий, которые используют IEqualityComparer?
OrderBy нуждался бы в виде, настолько скорее всего, мы смотрим на O (n, регистрируют n). Что, если это уже отсортировано? Что было бы, если я говорю OrderBy().ThenBy() и предоставьте тот же ключ обоим?
Я видел GroupBy (и Join) использование или сортировка или хеширование. Который является этим?
Contains был бы O (n) на a List, но O (1) на a HashSet - LINQ проверяет базовый контейнер, чтобы видеть, может ли он ускорить вещи?
И реальный вопрос - до сих пор, я брал его на вере, что операции производительны. Однако я могу положиться на это? Контейнеры STL, например, ясно указывают сложность каждой операции. Есть ли какие-либо подобные гарантии на производительности LINQ в спецификации библиотеки.NET?
Больше вопроса (в ответ на комментарии):
Действительно не думал об издержках, но я не ожидал там быть очень для простого Linq к объектам. Сообщение CodingHorror говорит о Linq-SQL, где я могу понять парсинг запроса, и создание SQL добавило бы стоимость - существует ли подобная стоимость для поставщика Объектов также? Если так, действительно ли это отличается при использовании декларативного или функционального синтаксиса?
4 ответа
Очень, очень мало гарантий, но есть несколько оптимизаций:
Расширение методы, использующие индексированный доступ, такие как
ElementAt,Skip,LastилиLastOrDefault, проверяют, является ли базовый тип реализуетIList, так что вы получаете доступ O (1) вместо O (N).Метод
Countпроверяет реализациюICollection, поэтому эта операция равна O (1) вместо O (N).Distinct,GroupByJoin, а также методы агрегирования наборов (Union,IntersectиExcept) используют хеширование, поэтому они должны быть близки к O (N) вместо O (N²).Содержитпроверки реализацииICollection, поэтому может быть O (1), если базовая коллекция также O (1), напримерHashSet, но это зависит от фактической структуры данных и не гарантируется. Наборы хэшей переопределяют методContains, поэтому они равны O (1).Методы OrderByиспользуют стабильную быструю сортировку, поэтому в них используется средний случай O (N log N).
Я думаю, что это касается большинства, если не всех встроенных методов расширения. На самом деле гарантий производительности очень мало; Сам Linq попытается воспользоваться преимуществами эффективных структур данных, но это не бесплатный пропуск для написания потенциально неэффективного кода.
Все, на что вы можете рассчитывать, это то, что методы Enumerable хорошо написаны для общего случая и не будут использовать наивные алгоритмы. Возможно, есть сторонние материалы (блоги и т.д.), которые описывают реально используемые алгоритмы, но они не являются официальными или гарантированными в том смысле, как алгоритмы STL.
Для примера, вот отраженный исходный код (любезно предоставленный ILSpy) для Enumerable.Count из System.Core:
// System.Linq.Enumerable
public static int Count<TSource>(this IEnumerable<TSource> source)
{
checked
{
if (source == null)
{
throw Error.ArgumentNull("source");
}
ICollection<TSource> collection = source as ICollection<TSource>;
if (collection != null)
{
return collection.Count;
}
ICollection collection2 = source as ICollection;
if (collection2 != null)
{
return collection2.Count;
}
int num = 0;
using (IEnumerator<TSource> enumerator = source.GetEnumerator())
{
while (enumerator.MoveNext())
{
num++;
}
}
return num;
}
}
Как вы можете видеть, он прилагает некоторые усилия, чтобы избежать наивного решения простого перечисления каждого элемента.
Я только что разобрался с reflector, и они действительно проверяют базовый тип при вызове Contains.
public static bool Contains<TSource>(this IEnumerable<TSource> source, TSource value)
{
ICollection<TSource> is2 = source as ICollection<TSource>;
if (is2 != null)
{
return is2.Contains(value);
}
return source.Contains<TSource>(value, null);
}
Правильный ответ - "зависит". Это зависит от того, какой тип лежит в основе IEnumerable. Я знаю, что для некоторых коллекций (например, коллекций, реализующих ICollection или IList) есть специальные кодовые пути, которые используются, однако не гарантируется, что фактическая реализация делает что-то особенное. Например, я знаю, что ElementAt() имеет специальный случай для индексируемых коллекций, аналогично с Count(). Но в целом вы должны предположить, что в худшем случае производительность O(n).
В общем, я не думаю, что вы найдете гарантии производительности, которые вам нужны, хотя если вы столкнетесь с конкретной проблемой производительности оператора linq, вы всегда можете просто переделать его для вашей конкретной коллекции. Также существует множество блогов и проектов по расширению, которые расширяют Linq to Objects, чтобы добавить такие гарантии производительности. Посмотрите Indexed LINQ, который расширяет и добавляет набор операторов для увеличения производительности.