Какие гарантии существуют в отношении сложности выполнения (Big-O) методов LINQ?

120

Я совсем недавно начал использовать 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()и предоставил один и тот же ключ обоим?

Я мог видеть GroupByJoin) использовать либо сортировку, либо хеширование. Что это?

Containsбудет O (n) на a List, но O (1) на a HashSet- проверяет ли LINQ базовый контейнер, чтобы узнать, может ли он ускорить работу?

И реальный вопрос - до сих пор я полагаю, что операции производительны. Однако могу ли я на это рассчитывать? Например, контейнеры STL четко определяют сложность каждой операции. Есть ли аналогичные гарантии производительности LINQ в спецификации библиотеки .NET?

Еще вопрос (в ответ на комментарии): на
самом деле не думал об накладных расходах, но я не ожидал, что будет много простых Linq-to-Objects. В сообщении CodingHorror говорится о Linq-to-SQL, где я могу понять, что синтаксический анализ запроса и создание SQL увеличат стоимость - есть ли аналогичная стоимость для поставщика объектов? Если да, то отличается ли это от использования декларативным или функциональным синтаксисом?

tzaman
источник
Хотя я действительно не могу ответить на ваш вопрос, я хочу прокомментировать, что в целом большая часть производительности будет «накладной» по сравнению с основной функциональностью. Это, конечно, не тот случай, когда у вас очень большие наборы данных (> 10 тыс. Элементов), поэтому мне любопытно, в каком случае вы хотите знать.
Анри
2
Re: "А разве вы используете декларативный или функциональный синтаксис?" - компилятор переводит декларативный синтаксис в функциональный синтаксис, чтобы они были одинаковыми.
Джон Раш
«Контейнеры STL четко определяют сложность каждой операции». Контейнеры .NET также четко определяют сложность каждой операции. Расширения Linq похожи на алгоритмы STL, а не на контейнеры STL. Так же, как когда вы применяете алгоритм STL к контейнеру STL, вам необходимо объединить сложность расширения Linq со сложностью операции (операций) контейнера .NET для правильного анализа результирующей сложности. Это включает учет специализаций шаблонов, как упоминается в ответе Ааронаута.
Timbo
Основной вопрос заключается в том, почему Microsoft не больше беспокоила, что оптимизация IList <T> будет иметь ограниченную полезность, учитывая, что разработчику пришлось бы полагаться на недокументированное поведение, если бы его код зависел от его производительности.
Эдвард Брей
AsParallel () в результирующем наборе List; должен дать вам ~ O (1) <O (n)
Задержка

Ответы:

121

Гарантий очень и очень мало, но есть несколько оптимизаций:

  • Методы расширения , которые используют индексный доступ, такие как 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), например a HashSet<T>, но это зависит от фактической структуры данных и не гарантируется. Хеш-наборы переопределяют Containsметод, поэтому они равны O (1).

  • OrderBy методы используют стабильную быструю сортировку, поэтому их средний случай составляет O (N log N).

Я думаю, что это касается большинства, если не всех встроенных методов расширения. На самом деле гарантий производительности очень мало; Сам Linq попытается воспользоваться преимуществами эффективных структур данных, но это не бесплатный пропуск для написания потенциально неэффективного кода.

Aaronaught
источник
Как насчет IEqualityComparerперегрузок?
tzaman
@tzaman: А что с ними? Если вы не используете действительно неэффективный обычай IEqualityComparer, я не могу заставить его повлиять на асимптотическую сложность.
Aaronaught
1
О верно. Я не реализовал EqualityComparerорудия GetHashCodeтак же хорошо, как Equals; но, конечно, в этом есть смысл.
tzaman
2
@imgen: циклические соединения - это O (N * M), которое обобщается до O (N²) для несвязанных множеств. Linq использует хеш-соединения, которые являются O (N + M), что обобщается на O (N). Это предполагает наполовину приличную хеш-функцию, но в .NET это сложно испортить.
Aaronaught
1
есть Orderby().ThenBy()еще N logNили это (N logN) ^2или что-то в этом роде?
М.казем Ахгары
10

Я давно знаю, что .Count()возвращается, .Countесли перечисление является IList.

Но я всегда был немного уставший о времени выполнения сложности операций Set: .Intersect(), .Except(), .Union().

Вот декомпилированная реализация BCL (.NET 4.0 / 4.5) для .Intersect()(мои комментарии):

private static IEnumerable<TSource> IntersectIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
{
  Set<TSource> set = new Set<TSource>(comparer);
  foreach (TSource source in second)                    // O(M)
    set.Add(source);                                    // O(1)

  foreach (TSource source in first)                     // O(N)
  {
    if (set.Remove(source))                             // O(1)
      yield return source;
  }
}

Выводы:

  • производительность O (M + N)
  • реализация не использует преимущества, когда коллекции уже . (Это может быть не обязательно просто, потому что используемый IEqualityComparer<T>также должен совпадать.)

Для полноты, вот реализации для .Union() и .Except().

Спойлер: они тоже имеют O (N + M) сложность.

private static IEnumerable<TSource> UnionIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
{
  Set<TSource> set = new Set<TSource>(comparer);
  foreach (TSource source in first)
  {
    if (set.Add(source))
      yield return source;
  }
  foreach (TSource source in second)
  {
    if (set.Add(source))
      yield return source;
  }
}


private static IEnumerable<TSource> ExceptIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
{
  Set<TSource> set = new Set<TSource>(comparer);
  foreach (TSource source in second)
    set.Add(source);
  foreach (TSource source in first)
  {
    if (set.Add(source))
      yield return source;
  }
}
Кристиан Диаконеску
источник
8

Все, на что вы действительно можете положиться, это то, что методы Enumerable хорошо написаны для общего случая и не будут использовать наивные алгоритмы. Вероятно, существуют сторонние материалы (блоги и т. Д.), Которые описывают фактически используемые алгоритмы, но они не являются официальными и не гарантируются в том смысле, в каком есть алгоритмы STL.

Чтобы проиллюстрировать это, вот отраженный исходный код (любезно предоставленный ILSpy) для Enumerable.CountSystem.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;
    }
}

Как видите, прилагаются некоторые усилия, чтобы избежать наивного решения простого перечисления каждого элемента.

Марсело Кантос
источник
перебор всего объекта для получения Count (), если это IEnnumerable, кажется мне довольно наивным ...
Зонко
4
@Zonko: Я не понимаю твою точку зрения. Я изменил свой ответ, чтобы показать, что Enumerable.Countон не повторяется, если нет очевидной альтернативы. Как бы вы сделали его менее наивным?
Марсело Кантос
Что ж, да, методы реализованы максимально эффективно с учетом исходников. Однако иногда наиболее эффективным способом является наивный алгоритм, и при использовании linq следует проявлять осторожность, поскольку он скрывает реальную сложность вызовов. Если вы не знакомы с базовой структурой объектов, которыми вы управляете, вы легко можете использовать неправильные методы для своих нужд.
Zonko
@MarceloCantos Почему массивы не обрабатываются? Это же для метода ElementAtOrDefault referencesource.microsoft.com/#System.Core/System/Linq/...
Freshblood
@Freshblood Они такие. (Массивы реализуют ICollection.) Однако я не знаю об ElementAtOrDefault. Я предполагаю, что массивы также реализуют ICollection <T>, но мой .Net в наши дни довольно ржавый.
Марсело Кантос,
3

Я только что выломал рефлектор, и они проверяют базовый тип при 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);
}
ChaosPandion
источник
3

Правильный ответ - это зависит от обстоятельств. это зависит от типа базового IEnumerable. Я знаю, что для некоторых коллекций (например, коллекций, реализующих ICollection или IList) используются специальные пути кода, однако фактическая реализация не гарантирует ничего особенного. например, я знаю, что ElementAt () имеет особый случай для индексируемых коллекций, аналогично Count (). Но в целом вам, вероятно, следует предположить наихудшую производительность O (n).

В целом я не думаю, что вы найдете те гарантии производительности, которые вам нужны, хотя, если вы столкнетесь с конкретной проблемой производительности с оператором linq, вы всегда можете просто переопределить его для своей конкретной коллекции. Также существует множество блогов и проектов расширяемости, которые расширяют Linq до объектов, чтобы добавить такие гарантии производительности. ознакомьтесь с индексированным LINQ, который расширяет и дополняет набор операторов для получения дополнительных преимуществ в производительности.

Люк
источник