Rendimiento de los clasificadores de colecciones .NET integrados

Question

Hubo una pregunta acerca de cómo ordenar una lista. Hubo varios métodos dados desde Basic List.Sort() a List.OrderBy(). Lo más risible fue un Roll-your-own-SelectionSort. Inmediatamente voté eso, pero me hizo pensar; ¿no aplicaría OrderBy() de Linq a una lista, haría lo mismo? myList.OrderBy (x => x.Property) .ToList() produciría un iterador que básicamente encuentra el valor mínimo de la proyección en lo que queda de la colección y yield la devuelve. Cuando revisamos toda la lista, es un tipo de selección.

Lo que me hizo pensar; ¿Qué algoritmos usan los clasificadores incorporados para listas, listas ordenadas, enumeraciones, etc. y, por extensión, se debe evitar alguno de ellos para colecciones grandes? Una SortedList, ya que permanece ordenada por clave, probablemente usaría un InsertionSort de un solo paso en cada adición; encuentre el primer índice con un valor mayor que el nuevo e inserte antes. Las listas y matrices probablemente se fusionen de manera bastante eficiente, pero no conozco el algoritmo real detrás de Sort(). Hemos discutido OrderBy.

Lo que sé arriba parece indicar que List.Sort() o Array.Sort() son las mejores opciones para una lista de tamaño conocido, y se debe desalentar el uso de Linq para ordenar una lista o matriz en memoria . Para una transmisión, realmente no hay otra manera que OrderBy() enumerable; la pérdida de rendimiento se ve mitigada por el hecho de que puede mantener los datos como una secuencia en lugar de tener que tenerlos todos antes de ordenarlos.

EDIT:

El consenso general es que Sort() se da más rápido de una aplicación concreta de una lista o matriz. OrderBy es razonable pero más lento porque agrega O (N) complejidad de extraer una matriz del enumerable pasado. La inicialización de SortedList termina siendo O (N^2) debido a lo que está debajo del capó. Moraleja de la historia, use List.Sort() en lugar de List.OrderBy() cuando tenga una Lista real.

Answer 1

Enumerable.OrderBy() sorbe el IEnumerable <> en una matriz y utiliza ordenación rápida. O (n) requisitos de almacenamiento. Lo hace una clase interna en System.Core.dll, EnumerableSort<TElement>.QuickSort(). El costo de almacenamiento lo hace no competitivo simplemente clasificando la lista, si tiene una, ya que la Lista <> se ordena en el lugar. Linq a menudo optimiza verificando las verdaderas capacidades de IEnumerable con el operador is. No funcionará aquí desde List <> .Sort es destructivo.

Lista <> .Sortand Array.Sort use en el lugar de ordenación rápida.

SortedList <> tiene O (n) complejidad para una inserción, que domina la complejidad O (log (n)) de encontrar el punto de inserción. Entonces, poner N elementos no ordenados costará O (n^2). SortedDictionary <> usa un árbol rojo-negro, lo que le da complejidad a la inserción O (log (n)). Por lo tanto, O (nlog (n)) para llenarlo, lo mismo que el tipo rápido amortizado.

Answer 2

Un vistazo rápido a través del reflector me dice que los métodos de clasificación de lista utilizan la clasificación rápida http://en.wikipedia.org/wiki/Quicksort través System.Collections.Generic.GenericArraySortHelper

SortedList utiliza Array.BinarySearch de averiguar dónde insertar cosas en cada uno Añadir

Enumeradores no tiene lógica de clasificación

Quicksort es una buena elección de clasificación para la mayoría de las situaciones, aunque puede acercarse a O (n^2) si no tiene suerte con los datos de entrada.

Si usted sospecha que sus datos de entrada a ser un gran pila de datos en un orden de mala suerte (ya clasificada) para la clasificación rápida de un truco es cambiar aleatoriamente los datos en primer lugar (que siempre es barato) y luego realizar la ordenación de la datos aleatorizados. Existen algunos trucos que el algoritmo de quicksort puede implementar para mitigar el problema de clasificar los datos de entrada ya ordenados (o casi ordenados), no sé si la implementación de BCL hace alguno de estos.

Answer 3

Una forma de averiguar el rendimiento de cada método es para medirlo:

List<int> createUnsortedList() 
{ 
    List<int> list = new List<int>(); 
    for (int i = 0; i < 1000000; ++i) 
     list.Add(random.Next()); 
    return list; 
} 

void Method1() 
{ 
    List<int> list = createUnsortedList(); 
    list.Sort(); 
} 

void Method2() 
{ 
    List<int> list = createUnsortedList(); 
    list.OrderBy(x => x).ToList(); 
} 

Resultado:

• Método1: 0,67 segundos (list.sort)
• Método 2: 3.10 segundos (OrderBy)

Esto muestra que el rendimiento de OrderBy es razonable incluso para listas muy grandes, pero no es tan rápido como el método de ordenación incorporado en una lista. Probablemente esto se deba a que el código para OrderBy es ligeramente más flexible: se necesita un selector de clave que se debe evaluar para cada elemento.

Answer 4

Sí, sus suposiciones parecen correctas. Hice una pequeña prueba para confirmarlo.

En 5000000 enteros,

data.Sort();       // 500 ms 
data = data.OrderBy(a => a).ToList(); // 5000 ms