Comparación entre timsort y quicksort

Question

¿Por qué escucho sobre quicksort ser el algoritmo de clasificación global más rápido cuando timsort (de acuerdo con la wikipedia) parece funcionar mucho mejor? Google no pareció mostrar ningún tipo de comparación.

Answer 1

TimSort es un mergesort altamente optimizado, es estable y más rápido que el viejo mergesort.

cuando se comparan con quicksort, tiene dos ventajas:

1. Es increíblemente rápido para la secuencia de datos casi ordenada (incluyendo inversa ordenadas de datos);
2. El peor de los casos sigue siendo O (N * LOG (N)).

Para ser sincero, no creo que el n. ° 1 sea una ventaja, pero sí me impresionó.

Estas son las ventajas de QuickSort

1. QuickSort es muy muy simple, incluso una aplicación altamente sintonizado, podemos escribir sus códigos pseduo dentro de 20 líneas;
2. QuickSort es el más rápido en la mayoría de los casos;
3. El consumo de memoria es LOG (N).

Actualmente, Java 7 SDK implementa timsort y una nueva variante de quicksort: es decir, Dual Pivot QuickSort.

Si necesita una clasificación estable, intente con timsort, de lo contrario, comience con la ruta rápida.

Answer 2

Más o menos, tiene que ver con el hecho de que Timsort es un algoritmo de clasificación híbrido. Esto significa que, si bien los dos tipos subyacentes que utiliza (clasificación Mergesort e Insertion) son peores que Quicksort para muchos tipos de datos, Timsort solo los usa cuando es ventajoso hacerlo.

En un nivel un poco más profundo, como Patrick87 estados, quicksort es el peor de los casos O (n) algoritmo. La elección de un buen pivote no es hard, pero garantizar una orden rápida O (n log n) tiene como resultado una clasificación generalmente más lenta en promedio.

Para obtener más información sobre Timsort, consulte this answer y la publicación de blog vinculada. Básicamente, asume que la mayoría de los datos ya están parcialmente ordenados, y construye "corridas" de datos ordenados que permiten fusiones eficientes utilizando mergesort.

Answer 3

En general, quicksort es el mejor algoritmo para matriz primitiva. Esto se debe a la localidad de memoria y al caché.

JDK7 usa TimSort para matriz de objetos. La matriz de objetos solo contiene la referencia del objeto. El objeto en sí se almacena en Heap. Para comparar el objeto, necesitamos leer el objeto del montón. Esto es como leer de una parte del montón para un objeto, luego leer al azar el objeto de otra parte del montón. Habrá una gran cantidad de errores de caché. Supongo que por esta razón la localidad de memoria ya no es importante. Esta puede ser la razón por la cual JDK solo utiliza TimSort para matriz de objetos en lugar de matriz primitiva.

Esto es solo mi suposición.

Answer 4

Aquí hay números de referencia de mi máquina (i7-6700 CPU, 3.4GHz, Ubuntu 16.04, gcc 5.4.0, los parámetros: SIZE = 100000 y corre = 3):

$ ./demo 
Running tests 
stdlib qsort time:     12246.33 us per iteration 
##quick sort time:     5822.00 us per iteration 
merge sort time:     8244.33 us per iteration 
...  
##tim sort time:     7695.33 us per iteration 
in-place merge sort time:   6788.00 us per iteration  
sqrt sort time:      7289.33 us per iteration  
... 
grail sort dyn buffer sort time: 7856.67 us per iteration 

El punto de referencia proviene de proyecto de Swenson sort en la que tal como se aplica varios algoritmos de ordenación en C. Presumiblemente, sus implementaciones son lo suficientemente buenas para ser representativa , pero no los he investigado

Así que realmente no se puede decir. Los números de referencia solo son relevantes durante un máximo de dos años y luego debe repetirlos. Posiblemente, timsort venció qsort waaay en 2011 cuando se formuló la pregunta, pero los tiempos han cambiado. O qsort siempre fue el más rápido, pero timsort lo superó con datos no aleatorios. O el código de Swenson no es tan bueno y un programador mejor cambiaría la tendencia a favor de timsort. O tal vez yo aspire y no usé el CFLAGS correcto al compilar el código. O ... Entiendes el punto.