LINQ to Objects GroupBy método

Question

¿Cómo funciona el método LINQ To Objects GroupBy? ¿Se ve a través de toda la colección para cada clave? ¿Hay alguna manera de decir al método GroupBy que la colección está ordenada?

Answer 1

GroupBy, si se hace con sensatez, funcionaría en un único pase hacia adelante solo. Una implementación básica (no el suyo) sería algo comparables a:

var data = new Dictionary<TKey, List<TValue>>(comparer); 
foreach(var item in source) { 
    var key = keySelector(item); 
    List<TValue> list; 
    if(!data.TryGetValue(key, out list)) 
    { 
     data.Add(key, list = new List<TValue>()); 
    } 
    list.Add(itemSelector(item)); 
} 

que, básicamente, por los grupos clave, la creación de una lista para cada clave única, que contiene los valores.

podría hacer cosas como comparar con la última clave (para ayudar con los datos ordenados), pero ... necesitaría un perfil para saber si vale la pena.

Answer 2

vamos a ver en la sobrecarga de

IEnumerable<IGrouping<TKey, TSource>> Enumerable.GroupBy<TSource, TKey>(
    this IEnumerable<TSource> source, 
    Func<TSource, TKey> keySelector 
); 

como el más simple de entender. Efectivamente el código va a hacer algo como esto:

enumerar source

Para cada element en origen, elemento de mapa de key = keySelector(element)

Ver si key es en un diccionario introducido por TKey si no lo es, agregue el key con el valor a List<TSource> y el primer artículo element else, obtenga el List<TSource> asociado a la clave y agregue element a la lista

Ahora tiene una asignación de diccionario TKey ->TSource y puede producir fácilmente una secuencia de IGrouping<TKey, TElement>.

así que algo como

var dictionary = new Dictionary<TKey, List<TSource>> dictionary; 
foreach(var element in source) { 
    key = keySelector(element); 
    List<TSource> list; 
    if(!dictionary.TryGetValue(key, out list)) { 
     list = new List<TSource>(); 
     dictionary.Add(key, list); 
    } 
    list.Add(element); 
} 

Desde aquí se puede producir fácilmente una secuencia de IGrouping<TKey, TSource>.

No veo por qué crees que la lista que se está ordenando importa.

Answer 3

¿Se ve en toda la colección para cada clave?

No. La aplicación de GroupBy es O (n), no O (n^2)