Aplicaciones prácticas de Radix Sort

Question

Radix sort es teóricamente muy rápido cuando se sabe que las claves están en un cierto rango limitado, digamos $n$ valores en el intervalo $[0\dots n^k -1]$ por ejemplo.Si $k<\lg$ n que acaba de convertir los valores a base $n$, que lleva $ heta(n)$ tiempo, hacer una base de $n$ radix sort y, a continuación, volver a convertir a su base original para un total de $ heta(nk)$ algoritmo.

Sin embargo, he leído que en la práctica radix sort es típicamente mucho más lento que hacer, por ejemplo, un estudio aleatorizado de quicksort:

Para matrices grandes, radix sort tiene el menor número de instrucciones, pero debido a su relativamente pobre rendimiento de la caché, su general el rendimiento es peor que la memoria versiones optimizadas de mergesort y quicksort.

Es radix sort sólo un buen teórica del algoritmo, o tiene en común usos prácticos?

Answer 1

Radix tipo son a menudo, en la práctica, la forma más rápida y la más útil tipo de máquinas en paralelo.

• Zagha y Blelloch:Radix sort para que el vector de multiprocesadores. La supercomputación, 1991: 712-721.
• Blelloch, Leiserson, Maggs, Plaxton, Smith, y Zagha:Una Comparación de los Algoritmos de Ordenación para la Conexión de la Máquina CM-2. Symp Algoritmos Paralelos y el Arco (SPAA-3):3-16, 1991.
• Arpaci-Dusseau, Arpaci-Dusseau, Culler, Hellerstein, y Patterson:De alto rendimiento de la clasificación por redes de estaciones de trabajo. Conf en Mgt de Datos, (SIGMOD-1997):243-254.
• Arpaci-Dusseau, Arpaci-Dusseau, Culler, Hellerstein, y Patterson.La búsqueda de la clasificación registro:experiencias en sintonía AHORA la clasificación. ACM Sigmetrics Symp Paralelo y Distribuido Herramientas, (SPDT-2):124-133, 1998.

En cada nodo de la multiprocesador probablemente hacer algo como un quicksort, pero radix sort permite que múltiples nodos para trabajar juntos con menos de sincronización de las distintas ordenaciones recursivas.

Hay otras situaciones también.Si usted necesita un ordenación estable (una especie donde siempre dos llaves son iguales que la estancia en el mismo orden en lugar de llegar reorganizado) entonces yo no soy consciente de que cualquier versión de quicksort, que será de uso.Mergesort es también estable (si se aplica correctamente).Su enlace es la primera vez que he oído a nadie decir que mergesort podría ser hecho de tener un mejor comportamiento de la caché de radix sort.

Answer 2

@Robert:Su enlace es bastante sorprendente (en realidad no he podido encontrar el citado de la sentencia).Mi experiencia personal es que de entrada aleatorio, radix sort es mucho más rápido que el STL std::sort(), que utiliza una variante de quicksort.Yo solía hacer un algoritmo 50% más rápido mediante la sustitución de std::sort() con un inestable radix sort.No estoy seguro de lo que es la "memoria de la versión optimizada" de quicksort, pero dudo de que puede ser dos veces tan rápido como el STL versión.

Este blog evalúa radix sort, junto con varios otros algoritmos de ordenación.Brevemente, en esta evaluación, std::sort() toma 5.1 seg para ordenar los 50 millones de números enteros, mientras que en el lugar/inestable radix sort toma 2.0 seg.Estable radix sort debe ser aún más rápido.

Radix sort es también ampliamente utilizado de forma estable la ordenación de las cadenas.Variantes de radix sort, a veces visto para la construcción de sufijo de matrices, BWT, etc.

Answer 3

Radix Sort también es una forma natural de ordenar palabras de longitud fija sobre un alfabeto fijo, por ejemplo, en el algoritmo Kärkkäinen & Sanders (http://www.cs.cmu.edu/~guyb/realworld/paperss04/kasa03.pdf)