algorithm - ordenamiento - ¿Cuál es el algoritmo más rápido para ordenar una lista vinculada?
cual es el mejor metodo de ordenamiento en java (11)
Tengo curiosidad si O (n log n) es lo mejor que puede hacer una lista vinculada.
Como sé, el mejor algoritmo de clasificación es O (n * log n), cualquiera que sea el contenedor; se ha demostrado que la ordenación en el sentido amplio de la palabra (estilo mergesort / quicksort, etc.) no puede ir más abajo. Usar una lista vinculada no le dará un mejor tiempo de ejecución.
El único algoritmo que se ejecuta en O (n) es un algoritmo de "pirateo" que se basa en el conteo de valores en lugar de la clasificación.
Como se ha dicho muchas veces, el límite inferior de la clasificación basada en la comparación para los datos generales va a ser O (n log n). Para resumir brevemente estos argumentos, ¡hay n! diferentes formas en que se puede ordenar una lista. Cualquier tipo de árbol de comparación que tenga n! (que está en O (n ^ n)) posibles géneros finales va a necesitar al menos log (n!) como su altura: esto le da un límite inferior O (log (n ^ n)), que es O (n log n).
Entonces, para datos generales en una lista enlazada, la mejor clasificación posible que funcionará con cualquier dato que pueda comparar dos objetos será O (n log n). Sin embargo, si tiene un dominio más limitado de las cosas para trabajar, puede mejorar el tiempo que toma (al menos proporcional a n). Por ejemplo, si está trabajando con números enteros que no superen cierto valor, puede usar Clasificación de conteo o Ordenar por Radix , ya que estos usan los objetos específicos que está ordenando para reducir la complejidad con proporción a n. Tenga cuidado, sin embargo, estos agregan algunas otras cosas a la complejidad que no puede considerar (por ejemplo, Counting Sort y Radix sort ambos agregan factores que se basan en el tamaño de los números que está ordenando, O (n + k) ) donde k es el tamaño del mayor número para Counting Sort, por ejemplo).
Además, si tiene objetos que tienen un hash perfecto (o al menos un hash que mapea todos los valores de manera diferente), puede intentar usar un orden de conteo o radix en sus funciones hash.
Dependiendo de una serie de factores, en realidad puede ser más rápido copiar la lista a una matriz y luego usar una Quicksort .
La razón por la que esto podría ser más rápido es porque una matriz tiene un rendimiento de memoria caché mucho mejor que una lista vinculada. Si los nodos de la lista están dispersos en la memoria, puede estar generando errores de caché en cualquier lugar. Por otra parte, si la matriz es grande obtendrá errores de caché de todos modos.
Mergesort se paralela mejor, por lo que puede ser una mejor opción si eso es lo que desea. También es mucho más rápido si lo realiza directamente en la lista vinculada.
Dado que ambos algoritmos se ejecutan en O (n * log n), tomar una decisión informada implicaría perfilarlos a ambos en la máquina en la que desea ejecutarlos.
--- EDITAR
Decidí probar mi hipótesis y escribí un C-programa que midió el tiempo (utilizando clock() ) para ordenar una lista vinculada de ints. Intenté con una lista vinculada donde cada nodo estaba asignado con malloc() y una lista vinculada donde los nodos se distribuían linealmente en una matriz, por lo que el rendimiento de la memoria caché sería mejor. Los comparé con el qsort incorporado, que incluía copiar todo de una lista fragmentada a una matriz y copiar el resultado nuevamente. Cada algoritmo se ejecutó en los mismos 10 conjuntos de datos y los resultados se promediaron.
Estos son los resultados:
N = 1000:
Lista fragmentada con tipo de combinación: 0.000000 segundos
Matriz con qsort: 0.000000 segundos
Lista empaquetada con tipo de combinación: 0.000000 segundos
N = 100000:
Lista fragmentada con tipo de combinación: 0.039000 segundos
Matriz con qsort: 0.025000 segundos
Lista empaquetada con tipo de combinación: 0.009000 segundos
N = 1000000:
Lista fragmentada con tipo de fusión: 1.162000 segundos
Matriz con qsort: 0.420000 segundos
Lista empaquetada con tipo de combinación: 0.112000 segundos
N = 100000000:
Lista fragmentada con tipo de combinación: 364.797000 segundos
Matriz con qsort: 61.166000 segundos
Lista empaquetada con tipo de combinación: 16.525000 segundos
Conclusión:
Al menos en mi máquina, copiar en una matriz vale la pena para mejorar el rendimiento de la memoria caché, ya que rara vez tiene una lista de enlaces completa en la vida real. Cabe señalar que mi máquina tiene un Phenom II de 2,8 GHz, pero solo 0,6 GHz de RAM, por lo que el caché es muy importante.
Es razonable esperar que no pueda hacer nada mejor que O (N log N) en tiempo de ejecución .
Sin embargo, la parte interesante es investigar si puedes ordenarla in-place , stably , su peor comportamiento y así sucesivamente.
Simon Tatham, de la fama de Putty, explica cómo ordenar una lista vinculada con el tipo de fusión . Concluye con los siguientes comentarios:
Al igual que cualquier algoritmo de ordenamiento que se precie, este tiene un tiempo de ejecución O (N log N). Debido a que esto es Mergesort, el peor tiempo de ejecución del caso sigue siendo O (N log N); no hay casos patológicos
El requisito de almacenamiento auxiliar es pequeño y constante (es decir, algunas variables dentro de la rutina de clasificación). Gracias al comportamiento inherentemente diferente de las listas enlazadas de las matrices, esta implementación Mergesort evita el costo de almacenamiento auxiliar O (N) normalmente asociado con el algoritmo.
También hay una implementación de ejemplo en C que funciona tanto para listas unidas como dobles.
Como @Jørgen Fogh menciona a continuación, la notación de grandes O puede ocultar algunos factores constantes que pueden hacer que un algoritmo tenga un mejor rendimiento debido a la ubicación de la memoria, debido a un bajo número de elementos, etc.
Este es un buen documento sobre este tema. Su conclusión empírica es que Treesort es el mejor, seguido de Quicksort y Mergesort. El tipo de sedimento, el tipo de burbuja y el tipo de selección funcionan muy mal.
UN ESTUDIO COMPARATIVO DE ALGORITMOS DE CLASIFICACIÓN DE LA LISTA VINCULADA por Ching-Kuang Shene
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.9981
La clasificación de fusión no requiere acceso O (1) y es O (n ln n). No hay algoritmos conocidos para clasificar datos generales que sean mejores que O (n ln n).
Los algoritmos de datos especiales como radix sort (límites de tamaño de datos) o histograma sort (cuenta datos discretos) podrían ordenar una lista vinculada con una función de crecimiento menor, siempre que use una estructura diferente con acceso O (1) como almacenamiento temporal .
Otra clase de datos especiales es una especie de comparación de una lista casi ordenada con k elementos fuera de servicio. Esto se puede ordenar en operaciones O (kn).
Copiar la lista a una matriz y volver sería O (N), por lo que cualquier algoritmo de clasificación se puede utilizar si el espacio no es un problema.
Por ejemplo, dada una lista vinculada que contiene uint_8 , este código lo ordenará en O (N) tiempo utilizando una ordenación de histograma:
#include <stdio.h>
#include <stdint.h>
#include <malloc.h>
typedef struct _list list_t;
struct _list {
uint8_t value;
list_t *next;
};
list_t* sort_list ( list_t* list )
{
list_t* heads[257] = {0};
list_t* tails[257] = {0};
// O(N) loop
for ( list_t* it = list; it != 0; it = it -> next ) {
list_t* next = it -> next;
if ( heads[ it -> value ] == 0 ) {
heads[ it -> value ] = it;
} else {
tails[ it -> value ] -> next = it;
}
tails[ it -> value ] = it;
}
list_t* result = 0;
// constant time loop
for ( size_t i = 255; i-- > 0; ) {
if ( tails[i] ) {
tails[i] -> next = result;
result = heads[i];
}
}
return result;
}
list_t* make_list ( char* string )
{
list_t head;
for ( list_t* it = &head; *string; it = it -> next, ++string ) {
it -> next = malloc ( sizeof ( list_t ) );
it -> next -> value = ( uint8_t ) * string;
it -> next -> next = 0;
}
return head.next;
}
void free_list ( list_t* list )
{
for ( list_t* it = list; it != 0; ) {
list_t* next = it -> next;
free ( it );
it = next;
}
}
void print_list ( list_t* list )
{
printf ( "[ " );
if ( list ) {
printf ( "%c", list -> value );
for ( list_t* it = list -> next; it != 0; it = it -> next )
printf ( ", %c", it -> value );
}
printf ( " ]/n" );
}
int main ( int nargs, char** args )
{
list_t* list = make_list ( nargs > 1 ? args[1] : "wibble" );
print_list ( list );
list_t* sorted = sort_list ( list );
print_list ( sorted );
free_list ( list );
}
Los géneros de comparación (es decir, los basados en elementos comparativos) no pueden ser más rápidos que n log n . No importa cuál sea la estructura de datos subyacente. Ver Wikipedia .
Otros tipos de ordenamiento que aprovechan que haya muchos elementos idénticos en la lista (como el tipo de recuento) o alguna distribución esperada de elementos en la lista son más rápidos, aunque no puedo pensar en ninguno que funcione particularmente bien en una lista enlazada
Mergesort es lo mejor que puedes hacer aquí.
No es una respuesta directa a su pregunta, pero si usa una lista de omisiones , ya está ordenada y tiene el tiempo de búsqueda O (log N).
Un ordenamiento de Radix es particularmente adecuado para una lista vinculada, ya que es fácil hacer una tabla de punteros que corresponde a cada valor posible de un dígito.
Aquí hay una implementación que atraviesa la lista una sola vez, recolecta ejecuciones, luego programa las fusiones de la misma manera que mergesort.
La complejidad es O (n log m) donde n es el número de elementos y m es el número de carreras. El mejor caso es O (n) (si los datos ya están clasificados) y el peor caso es O (n log n) como se esperaba.
Requiere memoria temporal O (log m); el tipo se hace in situ en las listas.
(actualizado a continuación, el comentarista uno hace un buen punto que debería describirlo aquí)
La esencia del algoritmo es:
while list not empty
accumulate a run from the start of the list
merge the run with a stack of merges that simulate mergesort''s recursion
merge all remaining items on the stack
La acumulación de ejecuciones no requiere mucha explicación, pero es bueno aprovechar la oportunidad para acumular tanto las carreras ascendentes como las descendentes (invertidas). Aquí prepende elementos más pequeños que la cabeza de la ejecución y agrega elementos mayores o iguales al final de la ejecución. (Tenga en cuenta que anteponiendo debe utilizar estricto menos de preservar la estabilidad de clasificación).
Es más fácil pegar el código de fusión aquí:
int i = 0;
for ( ; i < stack.size(); ++i) {
if (!stack[i])
break;
run = merge(run, stack[i], comp);
stack[i] = nullptr;
}
if (i < stack.size()) {
stack[i] = run;
} else {
stack.push_back(run);
}
Considere clasificar la lista (dagibecfjh) (ignorando ejecuciones). Los estados de pila proceden de la siguiente manera:
[ ]
[ (d) ]
[ () (a d) ]
[ (g), (a d) ]
[ () () (a d g i) ]
[ (b) () (a d g i) ]
[ () (b e) (a d g i) ]
[ (c) (b e) (a d g i ) ]
[ () () () (a b c d e f g i) ]
[ (j) () () (a b c d e f g i) ]
[ () (h j) () (a b c d e f g i) ]
Entonces, finalmente, combine todas estas listas.
Tenga en cuenta que el número de elementos (ejecuciones) en la pila [i] es cero o 2 ^ iy el tamaño de la pila está limitado por 1 + log2 (nruns). Cada elemento se fusiona una vez por nivel de pila, de ahí las comparaciones O (n log m). Hay una similitud pasajera con Timsort aquí, aunque Timsort mantiene su pila usando algo así como una secuencia de Fibonacci donde esto usa poderes de dos.
La acumulación de tiradas aprovecha cualquier dato ya ordenado, de modo que la mejor complejidad de caso es O (n) para una lista ya ordenada (una ejecución). Dado que estamos acumulando ejecuciones tanto ascendentes como descendentes, las ejecuciones siempre tendrán una longitud mínima de 2. (Esto reduce la profundidad máxima de la pila en al menos una, pagando el costo de encontrar las ejecuciones en primer lugar). La peor complejidad del caso es O (n log n), como se esperaba, para datos altamente aleatorios.
(Um ... Segunda actualización)
O simplemente vea wikipedia en mergesort de abajo hacia arriba .