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

Ответ 1

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

• Методы расширения, использующие индексированный доступ, такие как ElementAt, Skip, Last или LastOrDefault, будут проверять, реализует ли базовый тип IList<T>, так что вы получаете O (1) вместо O (N).

• Метод Count проверяет реализацию ICollection, поэтому эта операция O (1) вместо O (N).

• Distinct, GroupBy Join, и я также считаю, что методы агрегации-агрегации (Union, Intersect и Except) используют хеширование, поэтому они должны быть близки к O ( N) вместо O (N²).

• Contains проверяет реализацию ICollection, поэтому может быть O (1), если базовая коллекция также O (1), такая как HashSet<T>, но это зависит от фактического структуры данных и не гарантируется. Хэш-наборы переопределяют метод Contains, поэтому они являются O (1).

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

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

Ответ 2

Все, на что вы можете положиться, - это то, что методы 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;
    }
}

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

Ответ 3

Я давно знаю, что .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;
  }
}

Ответ 4

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

Ответ 5

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

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