performance - pseudocódigo - ¿Cuándo deberíamos usar Radix sort?
radix sort pdf (11)
A menos que tenga una lista enorme o claves extremadamente pequeñas, el log (N) suele ser más pequeño que k, rara vez es mucho más alto. Por lo tanto, la elección de un algoritmo de clasificación de propósito general con el rendimiento promedio de casos O (N log N) no es necesariamente peor que el uso de radix sort.
Corrección : como señaló @Mehrdad en los comentarios, el argumento anterior no es correcto: el tamaño de la clave es constante, luego el orden de radix es O (N), o el tamaño de la clave es k, luego el quicksort es O (k N log NORTE). Entonces, en teoría, el tipo de radix realmente tiene un mejor tiempo de ejecución asintótico.
En la práctica, los tiempos de ejecución estarán dominados por términos como:
tipo de raíz: c1 k N
quicksort: c2 k N log (N)
donde c1 >> c2, porque "extraer" bits de una clave más larga suele ser una operación costosa que implica cambios de bit y operaciones lógicas (o al menos acceso a memoria no alineado), mientras que las CPU modernas pueden comparar claves con 64, 128 o incluso 256 bits en una operación Entonces, para muchos casos comunes, a menos que N sea gigantesco, c1 será más grande que c2 log (N)
Parece que el género Radix tiene un muy buen rendimiento promedio de casos, es decir, O (kN) : http://en.wikipedia.org/wiki/Radix_sort
pero parece que la mayoría de las personas todavía usan Quick Sort, ¿no?
Aquí hay un enlace que compara quicksort y radixsort:
¿Radix ordena más rápido que quicksort para matrices de enteros? (sí lo es, 2-3x)
Aquí hay otro enlace que analiza los tiempos de ejecución de varios algoritmos:
Que es más rápido en los mismos datos; un tipo O (n) o un tipo O (nLog (n))?
Respuesta: depende. Depende de la cantidad de datos que se ordenan. Depende del hardware en el que se ejecuta y depende de la implementación de los algoritmos.
Editado de acuerdo a sus comentarios:
- La ordenación de radix solo se aplica a enteros, cadenas de tamaño fijo, puntos flotantes y a predicados de comparación de "menor que", "mayor que" o "orden lexicográfico", mientras que los géneros de comparación pueden acomodar órdenes diferentes.
- k puede ser mayor que log N.
- Se puede hacer una clasificación rápida en su lugar, el ordenamiento de radix se vuelve menos eficiente.
El ordenamiento de radix no es una ordenación basada en la comparación y solo puede ordenar tipos numéricos como enteros (incluidas las direcciones de puntero) y coma flotante, y es un poco difícil admitir de forma portátil el punto flotante.
Probablemente sea porque tiene un rango de aplicabilidad tan limitado que muchas bibliotecas estándar eligen omitirlo. Ni siquiera puede dejar que proporcione su propio comparador, ya que algunas personas pueden no querer incluso ordenar enteros directamente, sino usar los enteros como índices para otra cosa que se utilizará como clave para ordenar, por ejemplo, los géneros basados en comparación permiten todo esa flexibilidad, por lo que probablemente se trate de preferir una solución generalizada que satisfaga el 99% de las necesidades diarias de las personas en lugar de hacer un esfuerzo por satisfacer ese 1%.
Dicho esto, a pesar de la aplicabilidad estrecha, en mi dominio encuentro más uso para clases de radix que introsorts o quicksorts. Estoy en ese 1% y casi nunca trabajo con, por ejemplo, claves de cadena, pero a menudo encuentro casos de uso para números que se benefician al ser ordenados. Es porque mi base de código gira en torno a los índices de entidades y componentes (sistema de componente de entidad), así como cosas como mallas indexadas y hay una gran cantidad de datos numéricos.
Como resultado, el género radix se vuelve útil para todo tipo de cosas en mi caso. Un ejemplo común en mi caso es eliminar índices duplicados. En ese caso, realmente no necesito que se clasifiquen los resultados, pero a menudo un tipo de raíz puede eliminar duplicados más rápido que las alternativas.
Otra es encontrar, por ejemplo, una división mediana para un árbol kd a lo largo de una dimensión dada. La clasificación por radix de los valores de punto flotante del punto para una dimensión dada me da una posición mediana rápidamente en tiempo lineal para dividir el nodo del árbol.
Otro es primitivas de nivel superior ordenadas en profundidad por z para una transparencia alfa semiapropiada si no vamos a hacerlo en un sombreador de fragmentación. Eso también se aplica a GUIs y software de gráficos vectoriales para elementos z-order.
Otro es el acceso secuencial amigable con el caché usando una lista de índices. Si los índices se atraviesan muchas veces, a menudo mejora el rendimiento si los clasifico con anterioridad para que el recorrido se realice en orden secuencial en lugar de orden aleatorio. Este último podría zigzaguear hacia adelante y hacia atrás en la memoria, desalojando los datos de las líneas de caché solo para volver a cargar la misma región de memoria repetidamente dentro del mismo bucle. Cuando ordeno primero los índices antes de acceder a ellos repetidamente, eso deja de suceder y puedo reducir las fallas de la memoria caché considerablemente. En realidad, este es mi uso más común para tipos de radix y es la clave para que mi ECS sea compatible con la memoria caché cuando los sistemas quieren acceder a entidades con dos o más componentes.
En mi caso, tengo un tipo de raíz multiproceso que uso bastante 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 ]
Puedo promediar algo así como 6-7 ms para ordenar un millón de números una sola vez en mi pequeño hardware, que no es tan rápido como me gustaría, ya que los usuarios pueden percibir 6-7 milisegundos a veces en contextos interactivos, pero aún así un todo mucho mejor que 55-85 ms, como con el caso de std::sort de C ++ o qsort de C, que definitivamente daría lugar a hipo muy evidente en las velocidades de fotogramas. Incluso he escuchado de personas que implementan clases de radix usando SIMD, aunque no tengo idea de cómo lo lograron. No soy lo suficientemente inteligente como para encontrar una solución así, aunque incluso mi ingenioso sistema de radix funciona bastante bien en comparación con las bibliotecas estándar.
El ordenamiento de radix toma el tiempo O (k * n). Pero tienes que preguntar qué es K. K es la "cantidad de dígitos" (un poco simplista pero básicamente algo así).
Entonces, ¿cuántos dígitos tienes? Bastante respuesta, más que log (n) (log usando el "tamaño de dígito" como base) que hace que el algoritmo Radix O (n log n).
¿Porqué es eso? Si tiene menos de log (n) dígitos, entonces tiene menos de n números posibles. Por lo tanto, puede simplemente usar "tipo de recuento" que toma el tiempo O (n) (simplemente cuente cuántos de cada número tiene). Así que supongo que tiene más de k> log (n) dígitos ...
Es por eso que la gente no usa mucho el género Radix. Aunque hay casos en los que vale la pena usarlo, en la mayoría de los casos el ordenamiento rápido es mucho mejor.
El tipo de raíz es más difícil de generalizar que la mayoría de los otros algoritmos de clasificación. Requiere claves de tamaño fijo, y alguna forma estándar de romper las llaves en pedazos. Por lo tanto, nunca encuentra su camino en las bibliotecas.
Las otras respuestas aquí son horribles, no dan ejemplos de cuándo se usa realmente el género radix.
Un ejemplo es cuando se crea una "matriz de sufijos" usando el algoritmo skew DC3 (Kärkkäinen-Sanders-Burkhardt). El algoritmo es solo de tiempo lineal si el algoritmo de ordenamiento es de tiempo lineal, y la ordenación de radix es necesaria y útil aquí porque las claves son cortas por construcción (3-tuplas de enteros).
Un ejemplo sería cuando está ordenando un conjunto muy grande o una matriz de números enteros. Los tipos de distribución de radix y cualquier otro tipo son extremadamente rápidos ya que los elementos de datos se colocan principalmente en una matriz de colas (10 colas máximas para una ordenación LSD de raíz) y se vuelven a asignar a una ubicación de índice diferente de los mismos datos de entrada que se ordenarán. No hay bucles anidados, por lo que el algoritmo tiende a comportarse de forma más lineal a medida que el número de enteros de entrada de datos que se van a clasificar se vuelve significativamente más grande. A diferencia de otros métodos de ordenación, como el método bubbleSort extremadamente ineficiente, la ordenación de radix no implementa operaciones de comparación para ordenar. Es solo un proceso simple de reasignación de enteros a diferentes posiciones de índice hasta que finalmente se ordena la entrada. Si desea probar una clase de radix LSD para usted, he escrito una y almacenada en github, que puede probarse fácilmente en una js ide en línea, como el sandbox de codificación elocuente de javascript. Siéntase libre de jugar con él y ver cómo se comporta con diferentes números de n. He probado con hasta 900,000 enteros sin clasificar con un tiempo de ejecución <300ms. Aquí está el enlace si desea jugar con él.
https://gist.github.com/StBean/4af58d09021899f14dfa585df6c86df6
cuando n> 128, debemos usar RadixSort
cuando ordenar int32s, elijo radix 256, entonces k = log (256, 2 ^ 32) = 4, que es significativamente más pequeño que log (2, n)
y en mi prueba, el orden de radix es 7 veces más rápido que el quicksort 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 en matriz que se va a ordenar"
n = "longitud de la matriz"
O (k * n) = "peor caso en ejecución"
k * n = n ^ 2 (si k = n)
por lo tanto, cuando utilice el método de clasificación de radix, asegúrese de que "el número entero más largo sea más corto que el tamaño de matriz" o viceversa. ¡Entonces vas a vencer a Quicksort!
El inconveniente es que la mayoría de las veces no se puede asegurar el tamaño de los enteros grandes, pero si se tiene un rango fijo de números, la clasificación de radix debería ser el camino a seguir.
La clasificación rápida tiene un promedio de O (N logN), pero también tiene un peor caso de O (N ^ 2), por lo que incluso en la mayoría de los casos prácticos no llegará a N ^ 2, siempre existe el riesgo de que la entrada estará en "mal estado" para ti. Este riesgo no existe en el orden de radix. Creo que esto le da una gran ventaja al tipo de raíz.