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

Todo lo que puede contar es que los métodos Enumerables están bien escritos para el caso general y no utilizarán algoritmos ingenuos. Probablemente hay cosas de terceros (blogs, etc.) que describen los algoritmos realmente en uso, pero estos no son oficiales o garantizados en el sentido de que los algoritmos STL lo son.

Para ilustrar, aquí está el código fuente reflejado (cortesía de ILSpy) para Enumerable.Count del Sistema.Núcleo:

// 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 se puede ver, va a un cierto esfuerzo para evitar el ingenuo solución de simplemente enumerar cada elemento.

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

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

Aquí está la implementación de 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 aprovechar cuando las colecciones ya son conjuntos. (Se puede no ser necesariamente sencillo, porque el IEqualityComparer<T> usado también necesita coincidir.)

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

Alerta de Spoiler: ellos también tienen O(N+M) complejidad.

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

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

La respuesta correcta es "depende". depende de qué tipo de subyacente IEnumerable es. sé que para algunas colecciones (como las colecciones que implementan ICollection o IList) hay rutas de código especiales que se utilizan, sin embargo, la implementación real no está garantizada para hacer 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 caso O (n) rendimiento.

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 linq, siempre puede volver a implementarlo para su colección particular. También hay muchos blogs y proyectos de extensibilidad que extienden Linq a Objetos para agregar este tipo de garantías de rendimiento. echa un vistazo a Indexed LINQ que se extiende y agrega al conjunto de operadores para obtener más rendimiento beneficio.