En informática , la clasificación de números enteros es el problema algorítmico de ordenar una colección de valores de datos mediante claves enteras . Los algoritmos diseñados para la clasificación de números enteros también se pueden aplicar a menudo a problemas de clasificación en los que las claves son números de punto flotante , números racionales o cadenas de texto. [1] La capacidad de realizar aritmética de enteros en las claves permite que los algoritmos de clasificación de enteros sean más rápidos que los algoritmos de clasificación de comparación en muchos casos, dependiendo de los detalles de qué operaciones están permitidas en el modelo de computación y del tamaño de los números enteros que se van a ordenar. .
Los algoritmos de clasificación de enteros, incluida la clasificación por casillero , la clasificación por conteo y la clasificación por base, son ampliamente utilizados y prácticos. No se cree que otros algoritmos de clasificación de enteros con límites de tiempo más pequeños en el peor de los casos sean prácticos para arquitecturas informáticas con 64 bits o menos por palabra. Se conocen muchos de estos algoritmos, cuyo rendimiento depende de una combinación del número de elementos a clasificar, el número de bits por clave y el número de bits por palabra del ordenador que realiza el algoritmo de clasificación.
Los límites de tiempo para los algoritmos de ordenación de enteros normalmente dependen de tres parámetros: el número n de valores de datos a ordenar, la magnitud K de la clave más grande posible a ordenar y el número w de bits que se pueden representar en una sola palabra de máquina de la computadora en la que se va a realizar el algoritmo. Normalmente, se supone que w ≥ log 2 (max( n , K )) ; es decir, que las palabras de máquina sean lo suficientemente grandes como para representar un índice en la secuencia de datos de entrada, y también lo suficientemente grandes como para representar una única clave. [2]
Los algoritmos de clasificación de enteros generalmente están diseñados para funcionar en modelos informáticos de máquina de puntero o de máquina de acceso aleatorio . La principal diferencia entre estos dos modelos está en cómo se puede abordar la memoria. La máquina de acceso aleatorio permite utilizar cualquier valor que esté almacenado en un registro como dirección de operaciones de lectura y escritura de memoria, con un costo unitario por operación. Esta capacidad permite implementar rápidamente ciertas operaciones complejas sobre datos mediante búsquedas en tablas. Por el contrario, en el modelo de máquina de punteros, las operaciones de lectura y escritura utilizan direcciones almacenadas en punteros y no está permitido realizar operaciones aritméticas en estos punteros. En ambos modelos, se pueden agregar valores de datos y, normalmente, también se pueden realizar sobre ellos operaciones booleanas bit a bit y operaciones de desplazamiento binario, en unidad de tiempo por operación. Sin embargo, diferentes algoritmos de clasificación de enteros hacen suposiciones diferentes sobre si la multiplicación de enteros también se permite como operación de unidad de tiempo. [3] También se han considerado otros modelos de computación más especializados, como la máquina de acceso aleatorio paralelo . [4]
Andersson, Miltersen y Thorup (1999) demostraron que en algunos casos las multiplicaciones o búsquedas en tablas requeridas por algunos algoritmos de clasificación de números enteros podrían reemplazarse por operaciones personalizadas que se implementarían más fácilmente en hardware pero que normalmente no están disponibles en computadoras de uso general. Thorup (2003) mejoró esto mostrando cómo reemplazar estas operaciones especiales por las instrucciones de manipulación de campos de bits ya disponibles en los procesadores Pentium .
En los modelos informáticos de memoria externa , ningún algoritmo de clasificación de enteros conocido es más rápido que la clasificación por comparación. Los investigadores han demostrado que, en estos modelos, clases restringidas de algoritmos que están limitados en la forma en que manipulan sus claves no pueden ser más rápidos que la clasificación por comparación, [5] y que un algoritmo de clasificación de enteros que sea más rápido que la clasificación por comparación implicaría la falsedad de un Conjetura estándar en codificación de redes . [6]
Una cola de prioridad es una estructura de datos para mantener una colección de elementos con prioridades numéricas, que tiene operaciones para encontrar y eliminar el elemento con el valor de prioridad mínimo. Las colas de prioridad basadas en comparación, como el montón binario, toman un tiempo logarítmico por actualización, pero otras estructuras como el árbol de van Emde Boas o la cola de cubo pueden ser más rápidas para entradas cuyas prioridades son números enteros pequeños. Estas estructuras de datos se pueden utilizar en el algoritmo de clasificación por selección , que clasifica una colección de elementos buscando y eliminando repetidamente el elemento más pequeño de la colección y devolviendo los elementos en el orden en que se encontraron. Se puede utilizar una cola de prioridad para mantener la colección de elementos en este algoritmo, y el tiempo para este algoritmo en una colección de n elementos puede estar limitado por el tiempo para inicializar la cola de prioridad y luego realizar n operaciones de búsqueda y eliminación. Por ejemplo, el uso de un montón binario como cola de prioridad en la clasificación por selección conduce al algoritmo de clasificación del montón , un algoritmo de clasificación por comparación que requiere O ( n log n ) tiempo. En cambio, usar la clasificación por selección con una cola de cubos proporciona una forma de clasificación por casilleros , y el uso de árboles de van Emde Boas u otras colas de prioridad de enteros conduce a otros algoritmos rápidos de clasificación de enteros. [7]
En lugar de utilizar una cola de prioridad de enteros en un algoritmo de clasificación, es posible ir en la otra dirección y utilizar algoritmos de clasificación de enteros como subrutinas dentro de una estructura de datos de cola de prioridad de enteros. Thorup (2007) utilizó esta idea para mostrar que, si es posible realizar la clasificación de enteros en el tiempo T ( n ) por clave, entonces el mismo límite de tiempo se aplica al tiempo por operación de inserción o eliminación en una estructura de datos de cola de prioridad. La reducción de Thorup es complicada y supone la disponibilidad de operaciones de multiplicación rápidas o búsquedas en tablas, pero también proporciona una cola de prioridad alternativa que utiliza solo sumas y operaciones booleanas con tiempo T ( n ) + T (log n ) + T (log log n ) +... por operación, como máximo multiplicando el tiempo por un logaritmo iterado . [7]
Los algoritmos clásicos de clasificación de enteros de clasificación por casillero , clasificación por conteo y clasificación por base son ampliamente utilizados y prácticos. [8] Gran parte de la investigación posterior sobre algoritmos de clasificación de números enteros se ha centrado menos en la practicidad y más en mejoras teóricas en su análisis del peor de los casos , y no se cree que los algoritmos que provienen de esta línea de investigación sean prácticos para las computadoras actuales de 64 bits. arquitecturas, aunque los experimentos han demostrado que algunos de estos métodos pueden ser una mejora en la clasificación por base para datos con 128 o más bits por clave. [9] Además, para grandes conjuntos de datos, los patrones de acceso a la memoria casi aleatorios de muchos algoritmos de clasificación de números enteros pueden perjudicarlos en comparación con los algoritmos de clasificación de comparación que se han diseñado teniendo en cuenta la jerarquía de la memoria . [10]
La clasificación de enteros proporciona uno de los seis puntos de referencia en el conjunto de puntos de referencia de Matemáticas Discretas de DARPA High Productivity Computing Systems , [11] y uno de los once puntos de referencia en el conjunto de puntos de referencia paralelos de NAS .
La clasificación por casillero o la clasificación por conteo pueden ordenar n elementos de datos que tengan claves en el rango de 0 a K − 1 en el tiempo O ( n + K ) . En la clasificación por casilleros (a menudo llamada clasificación por depósitos), los punteros a los elementos de datos se distribuyen en una tabla de depósitos, representados como tipos de datos de colección , como listas vinculadas , utilizando las claves como índices en la tabla. Luego, todos los depósitos se concatenan para formar la lista de salida. [12] La clasificación por conteo utiliza una tabla de contadores en lugar de una tabla de depósitos, para determinar la cantidad de elementos con cada clave. Luego, se utiliza un cálculo de suma de prefijos para determinar el rango de posiciones en la salida ordenada en las que se deben colocar los valores con cada clave. Finalmente, en una segunda pasada por la entrada, cada elemento se mueve a la posición de su clave en la matriz de salida. [13] Ambos algoritmos implican sólo bucles simples sobre los datos de entrada (tomando el tiempo O ( n ) ) y sobre el conjunto de claves posibles (tomando el tiempo O ( K ) ), dando su límite de tiempo general O ( n + K ) .
La clasificación por base es un algoritmo de clasificación que funciona para claves más grandes que la clasificación por casillero o la clasificación por conteo realizando múltiples pasadas sobre los datos. Cada pasada clasifica la entrada usando solo una parte de las claves, utilizando un algoritmo de clasificación diferente (como clasificación por casillero o clasificación por conteo) que es adecuado solo para claves pequeñas. Para dividir las claves en partes, el algoritmo de clasificación de bases calcula la notación posicional para cada clave, de acuerdo con alguna base elegida ; entonces, la parte de la clave utilizada para el i- ésimo paso del algoritmo es el i- ésimo dígito en la notación posicional para la clave completa, comenzando desde el dígito menos significativo y avanzando hasta el más significativo. Para que este algoritmo funcione correctamente, el algoritmo de clasificación utilizado en cada pasada sobre los datos debe ser estable : los elementos con dígitos iguales no deben cambiar de posición entre sí. Para lograr una mayor eficiencia, se debe elegir la base de modo que esté cerca del número de elementos de datos, n . Además, el uso de una potencia de dos cercana a n como base permite que las claves para cada pasada se calculen rápidamente utilizando únicamente operaciones rápidas de desplazamiento binario y máscara. Con estas opciones, y con la clasificación por casillero o la clasificación por conteo como algoritmo base, el algoritmo de clasificación por base puede ordenar n elementos de datos que tengan claves en el rango de 0 a K − 1 en el tiempo O ( n log n K ) . [14]
Se han desarrollado muchos algoritmos de clasificación de enteros cuyo análisis teórico muestra que se comportan mejor que la clasificación por comparación, la clasificación por casillero o la clasificación por base para combinaciones suficientemente grandes de parámetros que definen el número de elementos a clasificar, el rango de claves y el tamaño de la palabra de la máquina. Qué algoritmo tiene el mejor rendimiento depende de los valores de estos parámetros. Sin embargo, a pesar de sus ventajas teóricas, estos algoritmos no suponen una mejora para los rangos típicos de estos parámetros que surgen en los problemas prácticos de clasificación. [9]
Se puede utilizar un árbol de Van Emde Boas como cola de prioridad para ordenar un conjunto de n claves, cada una en el rango de 0 a K − 1 , en el tiempo O ( n log log K ) . Esta es una mejora teórica con respecto a la clasificación por bases cuando K es suficientemente grande. Sin embargo, para utilizar un árbol de Van Emde Boas, se necesita una memoria direccionable directamente de K palabras o se necesita simularla usando una tabla hash , reduciendo el espacio a lineal pero haciendo que el algoritmo sea aleatorio. Otra cola de prioridad con rendimiento similar (incluida la necesidad de aleatorización en forma de tablas hash) es el Y-fast trie de Willard (1983).
Kirkpatrick y Reisch (1984) desarrollaron una técnica más sofisticada con un sabor similar y con mejor rendimiento teórico. Observaron que cada paso de clasificación de base puede interpretarse como una técnica de reducción de rango que, en tiempo lineal, reduce el tamaño máximo de clave en un factor de n ; en cambio, su técnica reduce el tamaño de la clave a la raíz cuadrada de su valor anterior (reduciendo a la mitad el número de bits necesarios para representar una clave), nuevamente en tiempo lineal. Al igual que en la clasificación por base, interpretan las claves como números de base b de dos dígitos para una base b que es aproximadamente √ K . Luego agrupan los elementos que se van a clasificar en depósitos según sus dígitos altos, en tiempo lineal, utilizando una memoria de dirección directa grande pero no inicializada o una tabla hash. Cada depósito tiene un representante, el elemento del depósito con la clave más grande; luego clasifican la lista de elementos utilizando como claves los dígitos altos para los representantes y los dígitos bajos para los no representantes. Al agrupar nuevamente los elementos de esta lista en depósitos, cada depósito se puede colocar en orden y, al extraer los representantes de la lista ordenada, los depósitos se pueden concatenar en orden. Así, en tiempo lineal, el problema de clasificación se reduce a otro problema de clasificación recursivo en el que las claves son mucho más pequeñas, la raíz cuadrada de su magnitud anterior. Repetir esta reducción de rango hasta que las claves sean lo suficientemente pequeñas como para ordenarlas por cubos conduce a un algoritmo con tiempo de ejecución O ( n log log n K ) .
Un complicado algoritmo aleatorio de Han y Thorup (2002) en el modelo de cálculo Word RAM permite que estos límites de tiempo se reduzcan aún más, a O ( n √ log log K ) .
Se dice que un algoritmo de clasificación de enteros no es conservador si requiere un tamaño de palabra w que sea significativamente mayor que log max( n , K ) . [15] Como ejemplo extremo, si w ≥ K , y todas las claves son distintas, entonces el conjunto de claves se puede ordenar en tiempo lineal representándolo como un vector de bits , con un bit 1 en la posición i cuando i es uno de los claves de entrada y luego eliminando repetidamente el bit menos significativo. [dieciséis]
El algoritmo de clasificación empaquetado no conservador de Albers y Hagerup (1997) utiliza una subrutina, basada en la red de clasificación bitónica de Ken Batcher , para fusionar dos secuencias ordenadas de claves, cada una de las cuales es lo suficientemente corta como para empaquetarse en una sola palabra de máquina. La entrada al algoritmo de clasificación empaquetada, una secuencia de elementos almacenados uno por palabra, se transforma en una forma empaquetada, una secuencia de palabras que contiene cada una de ellas múltiples elementos en orden ordenado, al usar esta subrutina repetidamente para duplicar el número de elementos empaquetados en cada una. palabra. Una vez que la secuencia está empaquetada, Albers y Hagerup utilizan una forma de clasificación por fusión para ordenarla; Cuando se fusionan dos secuencias para formar una única secuencia más larga, se puede utilizar la misma subrutina de clasificación bitónica para extraer repetidamente palabras empaquetadas que constan de los elementos restantes más pequeños de las dos secuencias. Este algoritmo obtiene suficiente aceleración a partir de su representación empaquetada para ordenar su entrada en tiempo lineal siempre que sea posible que una sola palabra contenga claves Ω(log n log log n ) ; es decir, cuando log K log n log log n ≤ cw para alguna constante c > 0 .
La clasificación por casillero, la clasificación por conteo, la clasificación por base y la clasificación por árbol de Van Emde Boas funcionan mejor cuando el tamaño de la clave es pequeño; para claves suficientemente grandes, se vuelven más lentas que los algoritmos de clasificación por comparación. Sin embargo, cuando el tamaño de la clave o el tamaño de la palabra es muy grande en relación con el número de elementos (o de manera equivalente, cuando el número de elementos es pequeño), puede volver a ser posible ordenar rápidamente, utilizando diferentes algoritmos que aprovechen el paralelismo inherente. en la capacidad de realizar operaciones aritméticas con palabras grandes.
Ajtai, Fredman y Komlós (1984) proporcionaron un primer resultado en esta dirección utilizando el modelo de computación de sonda celular (un modelo artificial en el que la complejidad de un algoritmo se mide sólo por el número de accesos a la memoria que realiza). Basándose en su trabajo, Fredman y Willard (1994) describieron dos estructuras de datos, el montón Q y el montón atómico, que se pueden implementar en una máquina de acceso aleatorio. El Q-heap es una versión de bits paralelos de un trie binario y permite que tanto las operaciones de cola de prioridad como las consultas sucesoras y predecesoras se realicen en tiempo constante para conjuntos de O ((log N ) 1/4 ) elementos, donde N ≤ 2 w es el tamaño de las tablas precalculadas necesarias para implementar la estructura de datos. El montón atómico es un árbol B en el que cada nodo del árbol se representa como un montón Q; permite operaciones de cola con prioridad de tiempo constante (y por lo tanto clasificación) para conjuntos de (log N ) O (1) elementos.
Andersson et al. (1998) proporcionan un algoritmo aleatorio llamado clasificación de firmas que permite la clasificación temporal lineal de conjuntos de hasta 2 O ((log w ) 1/2 − ε ) elementos a la vez, para cualquier constante ε > 0 . Como en el algoritmo de Kirkpatrick y Reisch, realizan una reducción de rango utilizando una representación de las claves como números en base b para una elección cuidadosa de b . Su algoritmo de reducción de rango reemplaza cada dígito por una firma, que es un valor hash con O (log n ) bits, de modo que diferentes valores de dígitos tienen firmas diferentes. Si n es suficientemente pequeño, los números formados por este proceso de reemplazo serán significativamente más pequeños que las claves originales, lo que permitirá que el algoritmo de clasificación empaquetado no conservador de Albers y Hagerup (1997) clasifique los números reemplazados en tiempo lineal. A partir de la lista ordenada de números reemplazados, es posible formar un trie comprimido de las claves en tiempo lineal, y los hijos de cada nodo en el trie se pueden ordenar recursivamente usando solo claves de tamaño b , después de lo cual un recorrido del árbol produce el orden ordenado de los elementos.
Fredman y Willard (1993) introdujeron el modelo de análisis transdicotómico para algoritmos de clasificación de números enteros, en el que no se supone nada sobre el rango de claves de números enteros y se debe limitar el rendimiento del algoritmo únicamente en función del número de valores de datos. Alternativamente, en este modelo, se supone que el tiempo de ejecución de un algoritmo en un conjunto de n elementos es el peor tiempo de ejecución para cualquier combinación posible de valores de K y w . El primer algoritmo de este tipo fue el algoritmo de clasificación de árboles de fusión de Fredman y Willard , que se ejecuta en el tiempo O ( n log n /log log n ) ; esta es una mejora con respecto a la clasificación por comparación para cualquier elección de K y w . Una versión alternativa de su algoritmo que incluye el uso de números aleatorios y operaciones de división de enteros mejora esto a O( n √ log n ) .
Desde su trabajo, se han desarrollado algoritmos aún mejores. Por ejemplo, aplicando repetidamente la técnica de reducción de rango de Kirkpatrick-Reisch hasta que las claves sean lo suficientemente pequeñas como para aplicar el algoritmo de clasificación empaquetado de Albers-Hagerup, es posible ordenar en el tiempo O ( n log log n ) ; sin embargo, la parte de reducción de rango de este algoritmo requiere una gran memoria (proporcional a √ K ) o aleatorización en forma de tablas hash. [17]
Han y Thorup (2002) mostraron cómo ordenar en tiempo aleatorio O ( n √ log log n ) . Su técnica implica utilizar ideas relacionadas con la clasificación por firmas para dividir los datos en muchas sublistas pequeñas, de un tamaño lo suficientemente pequeño como para que la clasificación por firmas pueda ordenar cada una de ellas de manera eficiente. También es posible utilizar ideas similares para ordenar números enteros de forma determinista en el tiempo O ( n log log n ) y el espacio lineal. [18] Usando solo operaciones aritméticas simples (sin multiplicaciones ni búsquedas en tablas) es posible ordenar en tiempo esperado aleatorio O ( n log log n ) [19] o de manera determinista en tiempo O ( n (log log n ) 1 + ε ) para cualquier constante ε > 0 . [1]