Parece Radix sort tiene un muy buen rendimiento promedio caso, es decir, O (kN): http://en.wikipedia.org/wiki/Radix_sort¿Cuándo deberíamos usar Radix sort?
pero parece que la mayoría de las personas siguen utilizando Ordenación rápida, ¿no es así?
La clasificación rápida tiene un promedio de O (N logN), pero también tiene el 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 sea "mala" para usted. Este riesgo no existe en el orden de radix. Creo que esto le da una gran ventaja al tipo de raíz.
Es poco probable que sea la principal ventaja.Otros géneros basados en comparación (como heapsort o mergesort) no tienen un peor comportamiento de peor caso que el de quicksort. –
el peor de los casos para quicksort no es realmente un argumento, ya que es por eso que las personas comúnmente usan la asignación rápida aleatoria, es decir, mezclan los datos de entrada antes de clasificarlos realmente. esto prácticamente elimina la posibilidad de tener un tiempo de ejecución N^2. – nburk
Introsort, que usa quicksort, se encarga de esto. Esto no es un argumento – Mehrdad
Editado acuerdo con sus comentarios:
"Se puede hacer una clasificación rápida en el lugar", también puede ordenar radix binaria, aunque eso aumenta la probabilidad de que k sea mayor que log N. –
Su primer punto no es del todo correcto: la ordenación de radix se puede aplicar fácilmente a cadenas de longitud fija. Y el predicado de comparación es obligatorio sin importar qué tipo de algoritmo use. –
"La ordenación de radix solo se aplica a enteros": ¿por qué? Siempre pensé que si ordenaba por los bits del exponente y los bits de la mantisa en el orden correcto, también puede usarlo para ordenar el número de puntos flotantes. Y en teoría, * podrías * usarlo en cadenas, solo k casi siempre será mayor que log N entonces. – Niki
La ordenación de radix 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.
A menos que tenga enorme lista o teclas extremadamente pequeñas, el registro (N) suele ser menor que k, rara vez es mucho mayor. 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 @Mehrdad señaló en los comentarios, el argumento anterior no es sólida: o bien el tamaño de la clave es constante, entonces especie radix es O (N), o el tamaño de la clave es k, entonces quicksort es O (k N log N). 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 será dominado por términos como:
radix para ordenar: c1 k N
quicksort: c2 log k N (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 la 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á mayor que c2 log (N)
Esto no es cierto para todos los casos. 'k' no necesita contar un poco, podría ser un conteo de bytes, por ejemplo, si está ordenando enteros de 4 bytes,' N' necesitaría ser menor que 16 para que 'log N' sea menor que 4 –
O (N log N) es ** ** mentira **. No existe tal cosa. Es O (k N log N) vs. O (k N) - si no me cree, pregúntese cómo en el mundo la clasificación podría ser independiente del tamaño del elemento. – Mehrdad
@Mehrdad: Parece un argumento sobre semántica. De la forma en que lo aprendí, el N in O (N log N) es el tamaño de la entrada, p. en bits Entonces, o bien los elementos tienen tamaño constante, o solo hay elementos N/k. – Niki
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 tiene? 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).
¿Por qué 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 Radix mucho. Aunque hay casos en los que vale la pena usarlo, en la mayoría de los casos el ordenamiento rápido es mucho mejor.
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)
por lo que cuando utilice el orden de Radix asegúrese de que "el entero más largo es más corto que el tamaño de la matriz" o viceversa. ¡Entonces vas a vencer a Quicksort!
El inconveniente es que la mayoría de las veces no se puede asegurar la gran cantidad de enteros, pero si tiene un rango fijo de números, la clasificación de radix debería ser el camino a seguir.
cuando n> 128, debemos utilizar Ordenamiento Radix
cuando tipo int32s, elijo radix 256, por lo que k = log (256, 2^32) = 4, lo cual es significativo menor que log (2, n)
y, en mi opinión, la clasificación de radix es 7 veces más rápida que la del 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]来保证原有的顺序不变
}
}
¿No necesita Radix-256 256 veces la memoria del tamaño de la matriz original? –
no, como puede ver en los códigos, solo necesita bar [256] ys [original.length], es adicional 1 vez la memoria de la matriz original – zhuwenbin
Las otras respuestas aquí son horribles, no dan ejemplos de cuando Radix sort se utiliza realmente.
Un ejemplo es cuando se crea una "matriz de sufijos" utilizando el algoritmo DCS skew (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).
Totalmente de acuerdo. No se mencionan cuándo se usa en realidad, y no hay puntos de referencia del mundo real que comparen los dos algoritmos. – johndoevodka
Aquí hay un enlace que compara la clasificación rápida y Ordenamiento Radix:
Is radix sort faster than quicksort for integer arrays? (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.
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 para ordenar. 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 va 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
Radix sort no es una especie basada en la comparación y puede ordenar únicos tipos numéricos como números enteros (incluyendo direcciones de puntero) y de punto flotante, y que es un poco difícil de soportar de forma portátil de punto flotante.
Probablemente sea porque tiene un rango de aplicabilidad tan limitado que muchas bibliotecas estándar eligen omitirlo. Ni siquiera puede dejar que proporciones tu 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 la clasificación, p. Los géneros basados en comparación permiten toda esa flexibilidad, por lo que es probable que solo se prefiera una solución generalizada que se ajuste al 99% de las necesidades diarias de las personas en lugar de salir del camino para atender 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, la ordenación de 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 determinada. 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 de ordenación en profundidad por z para la 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 radix multiproceso que uso con bastante frecuencia. 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 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 los usuarios a veces en contextos interactivos, pero aún mucho mejor que 55-85 ms como con el caso de C++ std::sort o C qsort 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.
La mayoría de las personas usa una rutina de ordenación proporcionada por su marco preferido sin siquiera preocuparse por el algoritmo. –
El ordenamiento de radix no es bueno con diferentes tipos de datos, pero cuando desea ordenar unsigned int y desea hacer el ordenamiento en un procesador multi-core como GPU, el ordenamiento de radix es más rápido. – tintin