¿Cuándo se debe utilizar Radix sort?

https://stackoverflow.com/questions/4146843

30-09-2019
|

Pregunta

Parece Radix sort tiene un muy buen rendimiento promedio caso, es decir, O (kN) http://en.wikipedia.org/wiki/Radix_sort

pero parece que la mayoría de la gente todavía está utilizando rápido Ordenado, ¿verdad?

Solución

Rápida especie tiene un promedio de O (N logN), pero también tiene un peor caso de O (n ^ 2), por lo que incluso debe, en la mayoría de los casos prácticos no lo puedo llegar a N ^ 2, siempre existe el riesgo que la entrada será de "mala orden" para usted. Este riesgo no existe en la base de clasificación. Creo que esto da una gran ventaja a Radix sort.

Otros consejos

Radix sort es difícil generalizar que la mayoría de otros algoritmos de ordenación. Requiere fija teclas de tamaño, y de alguna manera estándar de romper las claves en pedazos. Por lo tanto, no encuentra su camino en las bibliotecas.

Editado acuerdo con sus comentarios:

Radix sort sólo se aplica a números enteros, cadenas de tamaño fijo, puntos flotantes y "menor que", "mayor que" o "orden lexicográfico" predicados de comparación, mientras que las clases de comparación pueden adaptarse a diferentes órdenes.
k puede ser mayor que log N.
Rápida especie que se puede hacer en su lugar, se convierte en una especie radix menos eficiente.

Las otras respuestas aquí son horribles, que no dan ejemplos de cuando radix sort se utiliza realmente .

Un ejemplo es cuando la creación de un "array sufijo" usando el algoritmo DC3 skew (Kärkkäinen-Sanders-Burkhardt). El algoritmo es solamente lineal a tiempo si el algoritmo de clasificación es en tiempo lineal, y Radix sort es necesario y útil en este caso ya que las claves son cortos por la construcción (3-tuplas de números enteros).

A menos que tenga un enorme o las teclas extremadamente pequeñas, log (N) es por lo general menor que k, rara vez es mucho más alto. Así que la elección de una de propósito general algoritmo de ordenación con O (N log N) el rendimiento promedio caso no es peor que el uso de neccesarily Radix sort.

Corrección : Como @Mehrdad señaló en los comentarios, el argumento anterior no es sólida: o bien el tamaño de la clave es constante, entonces radix tipo es O (n), o el tamaño de la clave es k, entonces quicksort es O (k N log N). Por lo tanto, en teoría, Radix sort realmente tiene tiempo de ejecución asintótica mejor.

En la práctica, los tiempos de ejecución estará dominado por términos como:

radix para ordenar: c1 k N
quicksort: c2 log k N (N)

donde c1 c2 >>, porque "extraer" los bits de una clave más larga suele ser una operación costosa que implica desplazamientos de bit y operaciones lógicas (o al menos de acceso a memoria no alineada), mientras que las CPU modernas pueden comparar con las teclas 64, 128 o incluso 256 bits en una operación. Así que para muchos casos comunes, a menos que N es gigantesca, c1 será mayor que c2 registro (N)

Radix toma especie tiempo O (n k *). Pero hay que preguntar qué es K. K es el "número de dígitos" (un poco simplista, pero básicamente algo por el estilo).

Por lo tanto, cuántos dígitos tiene usted? Bastante respuesta, más de log (n) (log usando el "tamaño de dígitos" como base) que hace que el algoritmo de Radix O (n log n).

¿Por qué? Si tiene menos de dígitos (n) de registro, entonces usted tiene menos de n números posibles. Por lo tanto usted puede simplemente utilizar "contar tipo", que toma tiempo O (n) (simplemente contar el número de cada número que tiene). Así que supongo que tiene más de k> log (n) dígitos ...

Es por eso que la gente no utiliza Radix sort tanto. Aunque hay casos en los que vale la pena usarlo, en la mayoría de los casos rápida especie es mucho mejor.

cuando n> 128, debemos utilizar Ordenamiento Radix

cuando int32s ordenar, I eligen radix 256, por lo que k = log (256, 2 ^ 32) = 4, lo cual es significativo menor que log (2, n)

y en mi prueba, Radix sort es 7 veces más rápido que la clasificación rápida en el mejor de los casos.

public class RadixSort {
    private static final int radix=256, shifts[]={8,16,24}, mask=radix-1;
    private final int bar[]=new int[radix];
    private int s[] = new int[65536];//不使用额外的数组t，提高cpu的cache命中率

    public void ensureSort(int len){
        if(s.length < len)
            s = new int[len];
    }   

    public void sort(int[] a){
        int n=a.length;
        ensureSort(n);
        for(int i=0;i<radix;i++)bar[i]=0;
        for(int i=0;i<n;i++)bar[a[i]&mask]++;//bar存放了桶内元素数量
        for(int i=1;i<radix;i++)bar[i]+=bar[i-1];//bar存放了桶内的各个元素在排序结果中的最大下标+1
        for(int i=0;i<n;i++)s[--bar[a[i]&mask]]=a[i];//对桶内元素，在bar中找到下标x=bar[slot]-1, 另s[x]=a[i]（同时--bar[slot]将下标前移，供桶内其它元素使用）

        for(int i=0;i<radix;i++)bar[i]=0;
        for(int i=0;i<n;i++)bar[(s[i]>>8)&mask]++;
        for(int i=1;i<radix;i++)bar[i]+=bar[i-1];
        for(int i=n-1;i>=0;i--)a[--bar[(s[i]>>8)&mask]]=s[i];//同一个桶内的元素，低位已排序，而放入t中时是从t的大下标向小下标放入的，所以应该逆序遍历s[i]来保证原有的顺序不变

        for(int i=0;i<radix;i++)bar[i]=0;
        for(int i=0;i<n;i++)bar[(a[i]>>16)&mask]++;
        for(int i=1;i<radix;i++)bar[i]+=bar[i-1];
        for(int i=n-1;i>=0;i--)s[--bar[(a[i]>>16)&mask]]=a[i];//同一个桶内的元素，低位已排序，而放入t中时是从t的大下标向小下标放入的，所以应该逆序遍历s[i]来保证原有的顺序不变

        for(int i=0;i<radix;i++)bar[i]=0;
        for(int i=0;i<n;i++)bar[(s[i]>>24)&mask]++;
        for(int i=129;i<radix;i++)bar[i]+=bar[i-1];//bar[128~255]是负数，比正数小
        bar[0] += bar[255];
        for(int i=1;i<128;i++)bar[i]+=bar[i-1];     
        for(int i=n-1;i>=0;i--)a[--bar[(s[i]>>24)&mask]]=s[i];//同一个桶内的元素，低位已排序，而放入t中时是从t的大下标向小下标放入的，所以应该逆序遍历s[i]来保证原有的顺序不变      
    }
}

k = "longitud del valor más largo de Array para ser ordenada"

n = "longitud de la matriz"

O (k * n) = "peor de los casos se ejecuta"

k * n = n ^ 2 (si k = n)

así que cuando se utiliza Radix sort asegúrese de que "el número entero más largo es más corto que el tamaño de la matriz" o viceversa. A continuación, va a vencer a la ordenación rápida!

El inconveniente es:. La mayor parte del tiempo no se puede asegurar cómo enteros se convierten en grandes, pero si usted tiene una gama fija de números Radix sort debe ser el camino a seguir

Aquí hay un enlace que compara la clasificación rápida y Ordenamiento Radix:

Is Radix sort más rápido que la clasificación rápida de número entero matrices? (sí lo es, 2-3x)

Aquí hay otro enlace que analiza los tiempos de ejecución de varios algoritmos:

Una cuestión de Sorts :

Lo que es más rápida en los mismos datos; un O (n) tipo o un O (n log (n)) tipo?

Respuesta: Depende. Depende de la cantidad de datos que se clasifican. Depende del hardware de su ser ejecutado en, y depende de la aplicación de los algoritmos.

Radix sort no es una especie y basados ??en la comparación sólo puede ordenar tipos numéricos como números enteros (incluyendo direcciones de puntero) y de punto flotante, y que es un poco difícil de soporte portable de coma flotante.

Es probablemente porque tiene un estrecho rango de aplicabilidad tales que muchas bibliotecas estándar eligen para omitirlo. Ni siquiera se puede dejar de proporcionar su propia comparación, ya que algunas personas podrían no querer ordenar números enteros incluso directamente tanto como el uso de los números enteros como índices a otra cosa para ser utilizado como una clave para la clasificación, por ejemplo, las clases basadas en la comparación permiten que la flexibilidad de todo lo que es probablemente un caso de simplemente prefieren una solución generalizada ajuste del 99% de las necesidades diarias de la gente en lugar de salir de la manera de atender a que el 1%.

Dicho esto, a pesar de la aplicabilidad estrecho, en mi dominio yo he hallado más el uso de Ordenamiento Radix que introsorts o quicksorts. Estoy en ese 1% y casi nunca trabajo con, por ejemplo, claves de cadena, pero a menudo se encuentran los casos de uso para los números que se benefician de ser ordenados. Es porque mis gira alrededor de índices código base a entidades y componentes (sistema entidad de componente), así como cosas como mallas indexados y hay una gran cantidad de datos numéricos.

Como resultado, se convierte en una especie radix útil para todo tipo de cosas en mi caso. Un ejemplo común en mi caso es la eliminación de los índices duplicados. En ese caso, realmente no necesita que los resultados sean ordenados, pero a menudo una especie radix pueden eliminar duplicados rápido que las alternativas.

Otra es encontrar, por ejemplo, una división mediana para una kd-árbol a lo largo de una dimensión dada. Hay Radix clasificación de los valores de punto flotante de punto para una dimensión dada me da una posición media con rapidez en el tiempo lineal para dividir el nodo del árbol.

Otra es la profundidad de clasificación de las primitivas de alto nivel por z de transparencia alfa semi-apropiada si no vamos a estar haciendo en un shader de fragmentación. Esto también se aplica al software de interfaces gráficas de usuario y los gráficos vectoriales a elementos de orden z.

Otra es de acceso secuencial caché ambiente usando una lista de índices. Si los índices son atravesados ??muchas veces, a menudo mejora el rendimiento si Radix sort ellos con antelación para que el recorrido se realiza en orden secuencial en lugar de orden aleatorio. Este último podría zig-zag hacia atrás y adelante en la memoria, el desalojo de los datos de líneas de caché sólo para recargar la misma región de memoria repetidamente dentro del mismo bucle. Cuando Radix sort los índices primero antes de acceder a ellos en varias ocasiones, que deja de pasar y pueden reducir considerablemente los errores de caché. Esto es en realidad mi uso más común para el Ordenamiento Radix y es la clave de mi ECS siendo caché de usar cuando los sistemas quieren entidades de acceso con dos o más componentes.

En mi caso tengo una raíz multiproceso tipo que uso muy a menudo. Algunos puntos de referencia:

--------------------------------------------
- test_mt_sort
--------------------------------------------
Sorting 1,000,000 elements 32 times...

mt_radix_sort: {0.234000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]

std::sort: {1.778000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]

qsort: {2.730000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]

Me puede promedio algo así como 6-7 ms para ordenar un millón de números de una sola vez en mi hardware de mala muerte, que no es tan rápido como me gustaría desde 6-7 milisegundos todavía pueden ser vistos por los usuarios a veces en contextos interactivos, pero todavía mucho mejor que el 55-85 ms como con el caso de std::sort C ++ 's o qsort de C que sin duda conducir a hipo muy evidentes en velocidades de fotogramas. Incluso he oído hablar de personas que implementan Ordenamiento Radix usando SIMD, aunque no tengo ni idea de cómo se las arreglaron eso. Soy lo suficientemente inteligente como para no llegar a una solución de este tipo, aunque incluso mi radix poco ingenuo tipo sabe muy bien en comparación con las bibliotecas estándar.

Un ejemplo sería cuando está ordenando un conjunto muy grande o una matriz de enteros. Una especie radix y cualquier otro tipo de distribución de tipos son extremadamente rápido ya que los elementos de datos principalmente se están en cola en una matriz de colas (máximo 10 colas para una LSD radix especie) y reasignan a una ubicación de índice diferente de los mismos datos de entrada que ser resuelto. No hay bucles anidados por lo que el algoritmo tiende a comportarse de manera más lineal a medida que el número de enteros de entrada de datos a clasificar se convierte en mucho más grande. A diferencia de otros métodos de clasificación, al igual que el método BubbleSort extremadamente ineficiente, la raíz especie no implementa operaciones de comparación para ordenar. Es sólo un simple proceso de reasignación de números enteros a diferentes posiciones de índice hasta que la entrada es finalmente ordenadas. Si desea poner a prueba una base LSD clase por sí mismo, he escrito un out y almacenado en github que puede ser probado fácilmente en un JS en línea IDE como caja de arena de codificación elocuente de JavaScript. Siéntase libre de jugar con él y ver cómo se comporta con los números de n diferentes. He probado con hasta 900.000 enteros sin ordenar con un tiempo de ejecución <300 ms. Aquí está el enlace si desea jugar un rato con él.

https://gist.github.com/StBean/4af58d09021899f14dfa585df6c86df6

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow