¿Cuál es el algoritmo más rápido para ordenar una lista vinculada?

Question

Tengo curiosidad por saber si O (n log n) es lo mejor que puede hacer una lista vinculada.

Answer 1

Es razonable esperar que no se puede hacer nada mejor que O (N log N) en tiempo de ejecución.

Sin embargo, la parte interesante es investigar si puede ordenarlo in-place, stably, su comportamiento en el peor de los casos, y así sucesivamente.

Simon Tatham, de la fama de Putty, explica cómo sort a linked list with merge sort. Concluye con los siguientes comentarios:

Como 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 más adelante, la notación de orden O puede ocultar algunos factores constantes que pueden causar un algoritmo para realizar mejor gracias a la localidad de memoria, debido a un bajo número de artículos, etc.

Answer 2

No es una respuesta directa a su pregunta, pero si usa Skip List, ya está ordenada y tiene el tiempo de búsqueda O (log N).

Answer 3

Mergesort es lo mejor que puede hacer aquí.

Answer 4

Como sé, el mejor algoritmo de clasificación es O (n * log n), cualquiera que sea el contenedor - se ha demostrado que la clasificación en el sentido amplio de la palabra (estilo mergesort/quicksort etc.) no puede bajar. 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 recuento de valores en lugar de en la ordenación.

Answer 5

Merge sort no requiere O (1) acceso y es O (n ln n). Ningún algoritmo conocido para clasificar datos generales es mejor que O (n ln n).

Los algoritmos de datos especiales tales como radix sort (límites de tamaño de datos) o histograma (cuenta datos discretos) podrían ordenar una lista vinculada con una función de crecimiento menor, siempre que utilice una estructura diferente con O (1) acceso 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 enlazada que contiene uint_8, este código ordenarla en tiempo O (N) utilizando un histograma para ordenar:

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

Answer 6

tipo de comparación (es decir, los basados ​​en la comparación de elementos) no puede ser posiblemente más rápido que n log n. No importa cuál sea la estructura de datos subyacente. Ver Wikipedia.

Otros tipos de ordenamiento que aprovechan la existencia de 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 ningún eso funciona particularmente bien en una lista vinculada.

Answer 7

en función de una número de factores, en realidad puede ser más rápido copiar la lista a una matriz y luego usar un Quicksort.

La razón por la que esto podría ser más rápido es porque una matriz tiene un mejor rendimiento de caché que una lista vinculada. Si los nodos de la lista están dispersos en la memoria, puede que esté generando omisiones 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 crear un perfil de ambos en la máquina en la que desea ejecutarlos.

--- EDITAR

decidí probar mi hipótesis y escribió un programa en C, que mide el tiempo (usando clock()) tomado para ordenar una lista enlazada de enteros. 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 fragmentado con combinación para ordenar: 0,000000 segundo

matriz con qsort: 0,000000 segundos

lista Lleno de fusión especie : 0.000000 segundos

N = 100,000:

lista fragmentado con combinación para ordenar: 0.039000 segundos

matriz con qsort: 0.025000 segundos

lista Lleno de combinación para ordenar: 0.009000 segundos

N = 1000000 :

Lista fragmentada con tipo de fusión: 1.162000 secon ds

Matriz con qsort: 0.420000 segundo

lista Lleno de combinación para ordenar: 0.112000 segundos

N = 100000000:

lista fragmentado con combinación para ordenar: 364.797000 segundo

matriz con qsort: 61.166000 segundos

Lista completada con tipo de combinación: 16.525000 segundos

Conclusión:

Al menos en mi máquina, copiar en una matriz es bien vale la pena para mejorar el rendimiento de la caché, ya que rara vez se tiene una lista enlazada completamente lleno 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.

Answer 8

Como se ha indicado muchas veces, el límite inferior en 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).

Por lo tanto, para datos generales en una lista vinculada, la mejor clasificación posible que funcionará en 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 Counting Sort o Radix Sort, ya que estos utilizan 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 asigna todos los valores de forma diferente), puede intentar usar un orden de recuento o radix en sus funciones hash.

Answer 9

A Radix sort es particularmente adecuado para una lista vinculada, ya que es fácil hacer una tabla de punteros que correspondan a cada posible valor de un dígito.

Answer 10

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 lista enlazada algoritmos de ordenación por Ching-Kuang Shene

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.9981

Answer 11

Here's an implementation que atraviesa la lista sólo una vez, recoleciones, a continuación, programa las fusiones de la misma manera que mergesort hace.

La complejidad es O (n log m) donde n es el número de elementos y m es el número de ejecuciones. 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 comentarista uno hace un buen punto para que yo describo 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 carreras no requiere mucha explicación, pero es Es bueno aprovechar la oportunidad para acumular tanto carreras ascendentes como 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 prepending debe utilizar estricta menos-que para preservar la estabilidad de clasificación.)

Es más fácil simplemente pegar el código 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 ordenar la lista (d a g i b e c f j h) (corre haciendo caso omiso). 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) ] 

Luego, 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.

Las tiradas de acumulación aprovechan los datos ya clasificados para que la mejor complejidad de caso sea 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 ver Wikipedia sobre bottom-up mergesort.