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

.net algorithm

Question

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

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

Las cosas son más oscuras para las operaciones más complejas; los operadores set-like ( Union , Distinct , Except , etc.) trabajan usando GetHashCode por defecto (afaik), por lo que parece razonable suponer que están usando una tabla hash internamente, haciendo estas operaciones O (n) también, en general. ¿Qué pasa con las versiones que usan un IEqualityComparer ?

OrderBy necesitaría un ordenamiento, por lo que lo más probable es que estemos viendo O (n log n). ¿Qué pasa si ya está ordenado? ¿Qué tal si digo OrderBy().ThenBy() y proporciono la misma clave a ambos?

Pude ver GroupBy (y Join ) usando sorting o hash. ¿Cuál es?

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

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

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

Answer 1

Acabo de romper reflector y comprueban el tipo subyacente cuando se llama a 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);
}

Answer 2

Hace mucho que sé que .Count() devuelve .Count si la enumeración es un IList .

Pero siempre estaba un poco cansado sobre la complejidad en tiempo de ejecución de las operaciones de Set: .Intersect() , .Except() , .Union() .

Aquí está la implementación descompilada de BCL (.NET 4.0 / 4.5) 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 aprovecha cuando las colecciones ya son conjuntos. (Puede que no sea necesariamente sencillo, porque el 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;
  }
}

Answer 3

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

• Los métodos de extensión que usan acceso indexado, como ElementAt , Skip , Last o LastOrDefault , verificarán si el tipo subyacente implementa IList<T> , de modo que obtenga O (1) acceso en lugar de O (N).

• El método Count verifica la implementación de ICollection , de modo que esta operación sea O (1) en lugar de O (N).

• Distinct , GroupBy Join , y creo que los métodos de agregación de conjuntos ( Union , Intersect y Except ) usan hash, por lo que deben estar cerca de O (N) en lugar de O (N²).

• Contains comprobaciones para una implementación de ICollection , por lo que puede ser O (1) si la colección subyacente también es O (1), como HashSet<T> , pero esto depende de la estructura de datos real y no está garantizada. Los conjuntos Hash anulan el método Contains , es por eso que son O (1).

• OrderBy métodos OrderBy usan un quicksort estable, por lo que son el caso promedio O (N log N).

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

Answer 4

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

En general, no creo que vayas a encontrar el tipo de garantías de rendimiento que deseas, aunque si te encuentras con un problema de rendimiento particular con un operador de linq siempre puedes volver a implementarlo para tu colección en particular. También hay muchos blogs y proyectos de extensibilidad que amplían Linq to Objects para agregar estos tipos de garantías de rendimiento. revise el LINQ indexado que se extiende y se agrega al operador para obtener más beneficios de rendimiento.

Answer 5

Todo lo que realmente puede suponer es que los métodos Enumerable están bien escritos para el caso general y no usarán algoritmos ingenuos. Probablemente existan elementos de terceros (blogs, etc.) que describan los algoritmos actualmente en uso, pero estos no son oficiales o están garantizados en el sentido de que son algoritmos STL.

Para ilustrar, aquí está el código fuente reflejado (cortesía de ILSpy) para Enumerable.Count from 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 esfuerza por evitar la ingenua solución de simplemente enumerar cada elemento.