¿Por qué no se usa Radix Sort con más frecuencia?

Es estable y tiene una complejidad temporal de O (n). Debería ser más rápido que algoritmos como Quicksort y Mergesort, pero casi nunca lo veo usado.

A diferencia de la clasificación por radix, la clasificación rápida es universal, mientras que la clasificación por radix solo es útil para las claves de longitud fija.

También debe comprender que O (f (n)) realmente significa en orden de K * f (n), donde K es una constante arbitraria. Para la clasificación por radix, esta K es bastante grande (al menos el orden de la cantidad de bits en los enteros ordenados), por otro lado, quicksort tiene una de las K más bajas entre todos los algoritmos de clasificación y la complejidad promedio de n * log (n). Por lo tanto, en el escenario de la vida real, quicksort será muy a menudo más rápido que la clasificación por radix.

La mayoría de los algoritmos de clasificación son de uso general. Dada una función de comparación, funcionan en cualquier cosa, y los algoritmos como Quicksort y Heapsort se ordenarán con O (1) memoria adicional.

La clasificación por radix es más especializada. Necesita una clave específica que esté en orden lexicográfico. Necesita un depósito para cada símbolo posible en la clave, y los depósitos deben contener muchos registros. (Alternativamente, necesita una gran variedad de cubos que contendrán todos los valores clave posibles). Es probable que necesite mucha más memoria para hacer la clasificación de radix, y la usará al azar. Nada de esto es bueno para las computadoras modernas, ya que es probable que obtenga fallas en la página, como Quicksort obtendrá errores de caché.

Finalmente, la gente en general ya no escribe sus propios algoritmos de clasificación. La mayoría de los idiomas tienen instalaciones de biblioteca para clasificar, y lo correcto es usarlos. Dado que la ordenación de radix no es de aplicación universal, por lo general tiene que adaptarse al uso real y utiliza mucha memoria adicional, es difícil colocarla en una función o plantilla de biblioteca.

Es bastante raro que las claves por las que ordena sean en realidad números enteros en un rango escaso conocido. Por lo general, tiene campos alfabéticos, que parecen admitir una ordenación no comparativa, pero dado que las cadenas del mundo real no se distribuyen de manera uniforme en todo el alfabeto, esto no funciona tan bien como debería en teoría.

Otras veces, el criterio se define solo operacionalmente (dados dos registros, puede decidir cuál viene primero, pero no puede evaluar qué tan 'abajo' en la escala está un registro aislado). Por lo tanto, el método a menudo no es aplicable, menos aplicable de lo que podría creer, o simplemente no más rápido que O (n * log (n)).

Lo uso todo el tiempo, en realidad más que una especie de comparación, pero admito que soy un bicho raro que trabaja más con números que con cualquier otra cosa (casi nunca trabajo con cuerdas, y generalmente son internados si es así en qué punto radix la ordenación puede ser útil nuevamente para filtrar duplicados y calcular intersecciones de conjuntos; prácticamente nunca hago comparaciones lexicográficas).

Un ejemplo básico es la clasificación de puntos de radix por una dimensión dada como parte de una búsqueda o división mediana o una forma rápida de detectar puntos coincidentes, fragmentos de clasificación de profundidad o clasificación de radix una matriz de índices utilizados en múltiples bucles para proporcionar un acceso más amigable para la caché patrones (no van y vienen en la memoria solo para regresar y volver a cargar la misma memoria en una línea de caché). Hay una aplicación muy amplia al menos en mi dominio (gráficos de computadora) solo para clasificar en teclas numéricas de 32 y 64 bits de tamaño fijo.

Una cosa que quería comentar y decir es que la clasificación de radix puede funcionar en números de coma flotante y negativos, aunque es difícil escribir una versión FP que sea lo más portátil posible. Además, aunque es O (n * K), K solo tiene que ser el número de bytes del tamaño de la clave (por ejemplo: un millón de enteros de 32 bits generalmente tomaría 4 pases de tamaño de byte si hay 2 ^ 8 entradas en el depósito ) El patrón de acceso a la memoria también tiende a ser mucho más amigable con la memoria caché que las clasificaciones rápidas, aunque normalmente necesita una matriz paralela y una pequeña matriz de cubos (el segundo generalmente puede caber bien en la pila). QS podría hacer 50 millones de intercambios para ordenar una matriz de un millón de enteros con patrones de acceso aleatorio esporádicos. La clasificación de radix puede hacer eso en 4 pases lineales, amigables con la caché, sobre los datos.

Sin embargo, la falta de conciencia de poder hacer esto con una K pequeña, en números negativos junto con coma flotante, podría contribuir significativamente a la falta de popularidad de los tipos de radix.

En cuanto a mi opinión sobre por qué las personas no lo usan con más frecuencia, podría tener que ver con muchos dominios que generalmente no tienen la necesidad de ordenar números o usarlos como claves de búsqueda. Sin embargo, solo en base a mi experiencia personal, muchos de mis antiguos colegas tampoco lo usaron en los casos en que se adaptaba perfectamente, y en parte porque no sabían que podría funcionar en FP y negativos. Por lo tanto, aparte de que solo funciona en tipos numéricos, a menudo se cree que es incluso menos aplicable en general de lo que realmente es. Tampoco tendría tanto uso si pensara que no funciona en números de coma flotante y enteros negativos.

Algunos puntos de referencia:

Sorting 10000000 elements 3 times...

mt_sort_int: {0.135 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

mt_radix_sort: {0.228 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

std::sort: {1.697 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

qsort: {2.610 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

Y eso es solo con mi ingenua implementación ( mt_sort_inttambién es clasificación de radix pero con una rama de código más rápida dado que puede suponer que la clave es un número entero). Imagine lo rápido que podría ser una implementación estándar escrita por expertos.

El único caso en el que encontré que la clasificación de radix fue peor que la comparación rápida de C ++ std::sortfue por un número muy pequeño de elementos, digamos 32, momento en el que creo que std::sortcomienza a usar tipos más adecuados para el número más pequeño de elementos como ordenamientos o tipo de inserción, aunque en ese momento mi implementación solo usa std::sort.

Una razón más: en la actualidad, la ordenación generalmente se implementa con una rutina de ordenación proporcionada por el usuario adjunta a la lógica de ordenación proporcionada por el compilador. Con una clasificación de radix esto sería considerablemente más complejo y empeoraría aún más cuando la rutina de clasificación actúe sobre múltiples claves de longitud variable. (Diga, nombre y fecha de nacimiento).

En el mundo real, he implementado una clasificación de radix una vez. Esto fue en los viejos tiempos cuando la memoria era limitada, no podía llevar todos mis datos a la memoria a la vez. Eso significaba que el número de accesos a los datos era mucho más importante que O (n) frente a O (n log n). Hice una pasada a través de los datos asignando cada registro a un contenedor (mediante una lista de qué registros estaban en qué contenedores, sin mover realmente nada). Para cada contenedor no vacío (mi clave de clasificación era texto, habría un montón de contenedores vacíos) Comprobé si realmente podía llevar los datos a la memoria; en caso afirmativo, tráigalo y use quicksort. Si no, cree un archivo temporal que contenga solo los elementos en el contenedor y llame a la rutina de forma recursiva. (En la práctica, se desbordarían pocos contenedores). Esto provocó dos lecturas completas y una escritura completa en el almacenamiento de red y algo así como el 10% de esto en el almacenamiento local.

En la actualidad, estos problemas de big data son mucho más difíciles de encontrar, probablemente nunca volveré a escribir algo así. (Si me enfrentara con los mismos datos en estos días, simplemente especificaría el sistema operativo de 64 bits, agregaría RAM si se agita en ese editor).

Si todos sus parámetros son todos enteros y si tiene más de 1024 parámetros de entrada, la clasificación de radix siempre es más rápida.

¿Por qué?

Complexity of radix sort = max number of digits x number of input parameters.

Complexity of quick sort = log(number of input parameters) x   number of input parameters

Entonces la clasificación de radix es más rápida cuando

log(n)> max num of digits

El número entero máximo en Java es 2147483647. Que tiene 10 dígitos

Entonces la clasificación de radix siempre es más rápida cuando

log(n)> 10

Por lo tanto, la clasificación de radix siempre es más rápida cuando n>1024