¿En qué casos son IEnumerable <T>. ¿Optimizado?

Question

Usando reflector Me he dado cuenta que el método System.Linq.Enumerable.Count tiene una condición para optimizarlo para el caso cuando el IEnumerable<T> aprobado es de hecho un ICollection<T>. Si el reparto tiene éxito, el método Count no necesita iterar sobre cada elemento, pero puede llamar al método Count de ICollection.

En base a esta Estaba empezando a pensar que IEnumerable<T> se puede utilizar como una vista de sólo lectura de una colección, sin tener la pérdida de rendimiento que originalmente esperaba basado en la API de IEnumerable<T>

estaba interesado si la optimización del Count aún se conserva cuando el IEnumerable<T> es el resultado de una declaración Select en un ICollection, pero en función del código reflejado este caso no está optimizado y requiere una iteración a través de todos los elementos.

¿Saca las mismas conclusiones del reflector? ¿Cuál podría ser el motivo de la falta de esta optimización? Parece que hay mucho tiempo perdido en esta operación común. ¿La especificación requiere que cada elemento se evalúa incluso si el recuento se puede determinar sin hacer eso?

Answer 1

Realmente no importa que el resultado de Select se evalúe con holgura. El Count es siempre equivalente al recuento de la colección original, por lo que podría haberse recuperado directamente devolviendo un objeto específico de Select que podría usarse para la evaluación de cortocircuito del método Count.

La razón por la que no es posible optimizar cabo la evaluación del método Count() en el valor de retorno de una llamada Select de algo con el recuento determinado (como un List<T>) es que podría cambiar el significado del programa.

Se deja que la función selector pasado a Select método para tienen efectos secundarios y sus efectos secundarios están obligados a ocurrir de manera determinista, en un orden predeterminado.

Supongamos:

new[]{1,2,3}.Select(i => { Console.WriteLine(i); return 0; }).Count(); 

La documentación requiere este código para imprimir

pesar de que el recuento es muy conocido desde el principio y podría ser optimizado, la optimización cambiaría el comportamiento del programa. Es por eso que no puedes evitar la enumeración de la colección de todos modos. Esa es exactamente una de las razones por las que las optimizaciones del compilador son mucho más sencillas en los lenguajes funcionales puros.

---

ACTUALIZACIÓN: Al parecer, no está claro que es perfectamente posible implementar Select y Count modo que Select s en ICollection<T> todavía se perezosamente evaluados pero el Count() serán evaluados en O (1) sin la enumeración de la colección. Voy a hacer eso sin cambiar la interfaz de ningún método. Algo similar se hace ya para ICollection<T>:

private interface IDirectlyCountable { 
    int Count {get;} 
} 
private class SelectICollectionIterator<TSource,TResult> : IEnumerable<T>, IDirectlyCountable { 
    ICollection<TSource> sequence; 
    Func<TSource,TResult> selector; 
    public SelectICollectionIterator(ICollection<TSource> source, Func<TSource,TResult> selector) { 
     this.sequence = source; 
     this.selector = selector; 
    } 
    public int Count { get { return sequence.Count; } } 
    // ... GetEnumerator ... 
} 
public static IEnumerable<TResult> Select<TSource,TResult>(this IEnumerable<TSource> source, Func<TSource,TResult> selector) { 
    // ... error handling omitted for brevity ... 
    if (source is ICollection<TSource>) 
     return new SelectICollectionIterator<TSource,TResult>((ICollection<TSource>)source, selector); 
    // ... rest of the method ... 
} 
public static int Count<T>(this IEnumerable<T> source) { 
    // ... 
    ICollection<T> collection = source as ICollection<T>; 
    if (collection != null) return collection.Count; 
    IDirectlyCountable countableSequence = source as IDirectlyCountable; 
    if (countableSequence != null) return countableSequence.Count; 
    // ... enumerate and count the sequence ... 
} 

Esto todavía evaluará la Count perezosamente. Si cambia la colección subyacente, se cambiará el recuento y la secuencia no se almacenará en caché. La única diferencia será no hacer los efectos secundarios en el delegado selector.

Answer 2

Un ICollection sabe la cantidad de elementos (Cuenta) que contiene. No tiene que iterar ningún elemento para determinarlo. Tomemos como ejemplo la clase HashSet (que implementa ICollection).

Un IEnumerable<T> no sabe cuántos elementos contiene. Debe enumerar toda la lista para determinar el número de elementos (Count).

Envolviendo el ICollection en una declaración LINQ, no lo hace más eficiente. No importa cómo gire y gire, se tendrá que enumerar ICollection.

Answer 3

Edición 02-Feb-2010:

Tal como lo veo, hay por lo menos dos maneras de interpretar esta pregunta.

¿Por qué el método Select<T, TResult> extensión, cuando llama en una instancia de una clase que implementa ICollection<T>, no devolver un objeto que proporciona una propiedad Count; y ¿por qué el método de extensión Count<T> no marca esta propiedad para que proporcione rendimiento O (1) cuando los dos métodos están encadenados?

Esta versión de la pregunta no hace suposiciones falsas acerca de cómo funcionan las extensiones de LINQ, y es una pregunta válida desde una llamada a ICollection<T>.Select.Count será, después de todo, siempre devuelven el mismo valor que ICollection<T>.Count. Así es como Mehrdad interpretó la pregunta, a la que ha proporcionado una respuesta completa.

Pero I lea la pregunta como preguntando ...

Si el método Count<T> extensión proporciona un rendimiento O (1) para un objeto de una clase aplicación de ICollection<T>, ¿por qué tampoco proporciona O (n) rendimiento para el valor de retorno de la extensión Select<T, TResult> ¿método?

En esta versión de la pregunta, existe una suposición errónea: que los métodos de extensión Linq trabajan juntos por unión de pequeñas colecciones uno tras otro (en memoria) y exponiéndolos a través de la interfaz de IEnumerable<T>.

Si esto fuera cómo funcionaban las extensiones de LINQ, el método Select podría ser algo como esto:

public static IEnumerable<TResult> Select<T, TResult>(this IEnumerable<T> source, Func<T, TResult> selector) { 
    List<TResult> results = new List<TResult>(); 

    foreach (T input in source) 
     results.Add(selector(input)); 

    return results; 
} 

Por otra parte, si esto fuera la implementación de Select, creo que iba a encontrar la mayoría del código que utiliza este método se comportaría de la misma manera. Pero sería un desperdicio, y de hecho causaría excepciones en ciertos casos como el que describí en mi respuesta original.

En realidad, creo que la implementación del método Select es mucho más cercano a algo como esto:

public static IEnumerable<TResult> Select<T, TResult>(this IEnumerable<T> source, Func<T, TResult> selector) { 
    foreach (T input in source) 
     yield return selector(input); 

    yield break; 
} 

Se trata de proporcionar la evaluación perezosa, y explica por qué una propiedad Count no es accesible en O (1) tiempo para el método Count.

En otras palabras, mientras que Mehrdad respondió a la pregunta de por qué Select no fue diseñado forma diferente para que Select.Count se comportan de manera diferente, he ofrecido mi mejor respuesta a la pregunta de por qué Select.Count comporta como lo hace.

---

respuesta original: efectos secundarios

método no es la respuesta.

Según la respuesta de Mehrdad:

Realmente no importa que el resultado de Select se evalúa con pereza.

No compro esto. Déjame explicar por qué.

Para empezar, tenga en cuenta los siguientes dos métodos muy similares:

public static IEnumerable<double> GetRandomsAsEnumerable(int N) { 
    Random r = new Random(); 

    for (int i = 0; i < N; ++i) 
     yield return r.NextDouble(); 

    yield break; 
} 

public static double[] GetRandomsAsArray(int N) { 
    Random r = new Random(); 

    double[] values = new double[N]; 
    for (int i = 0; i < N; ++i) 
     values[i] = r.NextDouble(); 

    return values; 
} 

bien, ¿qué hacen estos métodos? Cada uno devuelve tantos dobles aleatorios como desee el usuario (hasta int.MaxValue). ¿Importa si alguno de los métodos es evaluado o no?Para responder a esta pregunta, vamos a echar un vistazo al código siguiente:

public static double Invert(double value) { 
    return 1.0/value; 
} 

public static void Test() { 
    int a = GetRandomsAsEnumerable(int.MaxValue).Select(Invert).Count(); 
    int b = GetRandomsAsArray(int.MaxValue).Select(Invert).Count(); 
} 

se puede adivinar lo que sucederá con estos dos llamadas a métodos? Deja que te ahorraré la molestia de copiar el código y probar por ti mismo:

La primera variables, a, será (después de una cantidad potencialmente significativo de tiempo) se inicializa a int.MaxValue (actualmente 2147483647). El segundo uno, b, muy probablemente será interrumpido por un OutOfMemoryException.

Dado que Select y los otros métodos de extensión de Linq se evalúan con holgazanería, le permiten hacer cosas que simplemente no podría hacer de otra manera. Lo anterior es un ejemplo bastante trivial. Pero mi punto principal es disputar la afirmación de que la evaluación perezosa no es importante. La afirmación de Mehrdad de que una propiedad Count "es realmente conocida desde el principio y podría optimizarse" en realidad plantea la pregunta. El problema puede parecer sencillo para el método Select, pero Select no es realmente especial; devuelve un IEnumerable<T> al igual que el resto de los métodos de extensión Linq, y para que estos métodos "conozcan" el Count de sus valores de retorno requeriría que las colecciones completas se almacenaran en caché y, por lo tanto, prohibiría la evaluación diferida.

La evaluación lenta es la respuesta.

Por esta razón, tengo que estar de acuerdo con uno de los respondedores originales (cuya respuesta ahora parece haber desaparecido) que evaluación perezosa realmente es la respuesta aquí. La idea de que los efectos secundarios del método deben tenerse en cuenta es realmente secundaria, ya que esto ya está garantizado como un subproducto de la evaluación perezosa de todos modos.

Posdata: He hecho declaraciones muy enérgicas y he enfatizado mis puntos principalmente porque quería dejar en claro cuál es mi argumento, no por falta de respeto a ninguna otra respuesta, incluida la de Mehrdad, que creo que es perspicaz, pero pierde la marca.