¿Qué garantías hay sobre la complejidad en tiempo de ejecución (Big-O) de los métodos LINQ?

Recientemente comencé a usar LINQ bastante, y realmente no he visto ninguna mención de la complejidad del tiempo de ejecución para ninguno de los métodos LINQ. Obviamente, hay muchos factores en juego aquí, así que limitemos la discusión al IEnumerableproveedor simple de LINQ-to-Objects. Además, supongamos que cualquiera que se Funcpase como selector / mutador / etc.es una operación barata de O (1).

Parece obvio que todas las operaciones de un solo paso ( Select, Where, Count, Take/Skip, Any/All, etc.) serán O (n), ya que sólo tienen que caminar la secuencia de una vez; aunque incluso esto está sujeto a la pereza.

Las cosas son más turbias para las operaciones más complejas; la puesta a punto como operadores ( Union, Distinct, Except, etc.) mediante el trabajo GetHashCodepor defecto (que yo sepa), por lo que parece razonable suponer que están utilizando una tabla hash interna, haciendo que estas operaciones O (n), así, en general. ¿Qué pasa con las versiones que usan un IEqualityComparer?

OrderBynecesitaría una especie, por lo que lo más probable es que estemos mirando O (n log n). ¿Y si ya está ordenado? ¿Qué tal si digo OrderBy().ThenBy()y proporciono la misma clave para ambos?

Pude ver GroupBy(y Join) usar clasificación o hash. Cual es

Containssería O (n) en a List, pero O (1) en a HashSet- ¿LINQ verifica el contenedor subyacente para ver si puede acelerar las cosas?

Y la verdadera pregunta: hasta ahora, lo he estado tomando con fe en que las operaciones están funcionando. Sin embargo, ¿puedo contar con eso? Los contenedores STL, por ejemplo, especifican claramente la complejidad de cada operación. ¿Existen garantías similares sobre el rendimiento de LINQ en la especificación de la biblioteca .NET?

Más pregunta (en respuesta a los comentarios):
Realmente no había pensado en la sobrecarga, pero no esperaba que hubiera mucho para Linq-to-Objects simples. La publicación CodingHorror está hablando de Linq-to-SQL, donde puedo entender que analizar la consulta y hacer que SQL agregue un costo: ¿también hay un costo similar para el proveedor de Objetos? Si es así, ¿es diferente si usa la sintaxis declarativa o funcional?

Hay muy, muy pocas garantías, pero hay algunas optimizaciones:

• Los métodos de extensión que utilizan acceso indexado, tales como ElementAt, Skip, Lasto LastOrDefault, comprobará para ver si o no los implementos tipo subyacenteIList<T> , por lo que se obtiene O (1) acceso en lugar de O (N).

• El Countmétodo busca una ICollectionimplementación, por lo que esta operación es O (1) en lugar de O (N).

• Distinct, GroupBy Joiny creo que también los métodos de agregación de conjuntos ( Union, Intersecty Except) usan hash, por lo que deberían estar cerca de O (N) en lugar de O (N²).

• Containscomprueba una ICollectionimplementación, por lo que puede ser O (1) si la colección subyacente también es O (1), como a HashSet<T>, pero esto depende de la estructura de datos real y no está garantizado. Los conjuntos hash anulan elContains método, por eso son O (1).

• OrderBy Los métodos usan una ordenación rápida estable, por lo que son casos promedio O (N log N).

Creo que cubre la mayoría, si no todos, de los métodos de extensión integrados. Realmente hay muy pocas garantías de rendimiento; El propio Linq intentará aprovechar las estructuras de datos eficientes, pero no es un pase libre para escribir código potencialmente ineficiente.

Hace tiempo que sé que .Count()regresa .Countsi la enumeración es un IList.

Pero yo era siempre un poco cansados de la complejidad en tiempo de ejecución de las operaciones Set: .Intersect(), .Except(), .Union().

Aquí está la implementación BCL (.NET 4.0 / 4.5) descompilada para .Intersect()(comentarios míos):

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;
  }
}

Conclusiones:

• el rendimiento es O (M + N)
• la implementación no se aprovecha cuando las colecciones ya están configuradas. (Puede que no sea necesariamente sencillo, porque el usado IEqualityComparer<T>también debe coincidir).

Para completar, aquí están las implementaciones para .Union()y .Except().

Alerta de spoiler: ellos también tienen complejidad 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;
  }
}

Todo lo que realmente puede confiar es que los métodos Enumerable están bien escritos para el caso general y no usarán algoritmos ingenuos. Probablemente haya material de terceros (blogs, etc.) que describa los algoritmos realmente en uso, pero estos no son oficiales ni están garantizados en el sentido en que lo son los algoritmos STL.

Para ilustrar, aquí está el código fuente reflejado (cortesía de ILSpy) Enumerable.Countde 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;
    }
}

Como puede ver, se requiere un esfuerzo para evitar la ingenua solución de simplemente enumerar cada elemento.

Acabo de romper el reflector y verifican el tipo subyacente cuando Containsse llama.

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);
}

La respuesta correcta es "depende". depende del tipo de IEnumerable subyacente. Sé que para algunas colecciones (como las colecciones que implementan ICollection o IList) hay rutas de código especiales que se utilizan, sin embargo, no se garantiza que la implementación real haga nada especial. por ejemplo, sé que ElementAt () tiene un caso especial para colecciones indexables, de manera similar con Count (). Pero, en general, probablemente debería asumir el peor rendimiento de O (n).

En general, no creo que vaya a encontrar el tipo de garantías de rendimiento que desea, aunque si se encuentra con un problema de rendimiento particular con un operador de linq, siempre puede volver a implementarlo para su colección particular. También hay muchos blogs y proyectos de extensibilidad que extienden Linq a Objects para agregar este tipo de garantías de rendimiento. Eche un vistazo a Indexed LINQ, que se extiende y se suma al conjunto de operadores para obtener más beneficios de rendimiento.