Clasificación externa

La ordenación externa es una clase de algoritmos de ordenación que pueden manejar cantidades masivas de datos . La ordenación externa es necesaria cuando los datos que se ordenan no caben en la memoria principal de un dispositivo informático (normalmente RAM ) y, en su lugar, deben residir en la memoria externa más lenta , normalmente una unidad de disco . Por tanto, los algoritmos de ordenación externa son algoritmos de memoria externa y, por tanto, aplicables en el modelo de memoria externa de computación .

Los algoritmos de ordenación externa generalmente se dividen en dos tipos: ordenación de distribución, que se parece a quicksort , y ordenación por combinación externa, que se parece a merge sort . La ordenación por combinación externa generalmente utiliza una estrategia híbrida de ordenación y combinación. En la fase de ordenación, se leen fragmentos de datos lo suficientemente pequeños como para caber en la memoria principal, se ordenan y se escriben en un archivo temporal. En la fase de combinación, los subarchivos ordenados se combinan en un solo archivo más grande.

Modelo

Los algoritmos de ordenamiento externo se pueden analizar en el modelo de memoria externa . En este modelo, una memoria caché o interna de tamaño $M$ y una memoria externa ilimitada se dividen en bloques de tamaño $B$ , y el tiempo de ejecución de un algoritmo está determinado por la cantidad de transferencias de memoria entre la memoria interna y la externa. Al igual que sus contrapartes que no tienen en cuenta la memoria caché , los algoritmos de ordenamiento externo asintóticamente óptimos logran un tiempo de ejecución (en notación Big O ) de . $O\left({\frac {N}{B}}\log _{\frac {M}{B}}{\frac {N}{B}}\right)$

Ordenación por combinación externa

Un ejemplo de ordenamiento externo es el algoritmo de ordenamiento por fusión externa , que utiliza un algoritmo de fusión de K-way . Ordena fragmentos que caben en la RAM y luego fusiona los fragmentos ordenados. ^[1]^[2]

El algoritmo primero ordena $M$ elementos a la vez y vuelve a colocar las listas ordenadas en la memoria externa. Realiza una fusión de dos vías en esas listas ordenadas, recurriendo si no hay suficiente memoria principal para fusionar de manera eficiente en una sola pasada. Durante una pasada de fusión, $B$ elementos de cada lista ordenada se encuentran en la memoria interna y el mínimo se imprime repetidamente. ${\tfrac {M}{B}}$

Por ejemplo, para ordenar 900 megabytes de datos utilizando solo 100 megabytes de RAM:

Lea 100 MB de los datos en la memoria principal y ordénelos mediante algún método convencional, como quicksort .
Escribe los datos ordenados en el disco.
Repita los pasos 1 y 2 hasta que todos los datos estén en fragmentos ordenados de 100 MB (hay 900 MB / 100 MB = 9 fragmentos), que ahora deben fusionarse en un solo archivo de salida.
Lee los primeros 10 MB (= 100 MB / (9 fragmentos + 1)) de cada fragmento ordenado en los búferes de entrada de la memoria principal y asigna los 10 MB restantes a un búfer de salida. (En la práctica, podría proporcionar un mejor rendimiento hacer que el búfer de salida sea más grande y los búferes de entrada un poco más pequeños).
Realice una fusión de 9 vías y almacene el resultado en el búfer de salida. Cada vez que se llene el búfer de salida, escríbalo en el archivo ordenado final y vacíelo. Cada vez que se vacíe alguno de los 9 búferes de entrada, rellénelo con los siguientes 10 MB de su fragmento ordenado asociado de 100 MB hasta que no haya más datos disponibles del fragmento.

El paso de fusión es clave para que la ordenación por fusión externa funcione externamente. El algoritmo de fusión solo realiza un paso por cada fragmento, por lo que no es necesario cargar todos los fragmentos a la vez; en cambio, se cargan partes secuenciales del fragmento según sea necesario. Y siempre que los bloques leídos sean relativamente grandes (como los 10 MB de este ejemplo), las lecturas pueden ser relativamente eficientes incluso en medios con un bajo rendimiento de lectura aleatoria, como los discos duros.

Históricamente, en lugar de una clasificación, a veces se utilizaba un algoritmo de selección de reemplazo ^{[3] para realizar la distribución inicial, para producir en promedio la mitad de fragmentos de salida del doble de longitud.}

Pases adicionales

El ejemplo anterior es una ordenación de dos pasos: primero, ordenación y luego fusión. La ordenación finaliza con una única fusión de k vías, en lugar de una serie de pases de fusión de dos vías como en una ordenación de fusión en memoria típica. Esto se debe a que cada pase de fusión lee y escribe todos los valores desde y hacia el disco, por lo que reducir la cantidad de pases compensa con creces el costo adicional de una fusión de k vías.

La limitación de la fusión de un solo paso es que, a medida que aumenta la cantidad de fragmentos, la memoria se dividirá en más búferes, por lo que cada búfer es más pequeño. Con el tiempo, las lecturas se vuelven tan pequeñas que se dedica más tiempo a las búsquedas en el disco que a la transferencia de datos. Una unidad de disco duro magnética típica puede tener un tiempo de acceso de 10 ms y una velocidad de transferencia de datos de 100 MB/s, por lo que cada búsqueda lleva tanto tiempo como la transferencia de 1 MB de datos.

Por lo tanto, para ordenar, por ejemplo, 50 GB en 100 MB de RAM, utilizar un único pase de combinación de 500 direcciones no es eficiente: solo podemos leer 100 MB / 501 ≈ 200 KB de cada fragmento a la vez, por lo que 5/6 del tiempo del disco se gasta en búsquedas. Utilizar dos pases de combinación resuelve el problema. Entonces, el proceso de ordenamiento podría verse así:

Ejecute el paso de clasificación de fragmentos inicial como antes para crear fragmentos ordenados de 500×100 MB.
Ejecute un primer pase de fusión combinando fragmentos de 25 × 100 MB a la vez, lo que da como resultado fragmentos ordenados de 20 × 2,5 GB.
Ejecute un segundo pase de fusión para fusionar los fragmentos ordenados de 20 × 2,5 GB en un único resultado ordenado de 50 GB

Aunque esto requiere un paso adicional sobre los datos, cada lectura ahora tiene una longitud de 4 MB, por lo que solo se dedica 1/5 del tiempo del disco a la búsqueda. La mejora en la eficiencia de transferencia de datos durante los pasos de fusión (del 16,6 % al 80 % es casi una mejora de 5 veces) compensa con creces el número duplicado de pasos de fusión.

Las variaciones incluyen el uso de un medio intermedio como un disco de estado sólido para algunas etapas; el almacenamiento temporal rápido no necesita ser lo suficientemente grande como para contener todo el conjunto de datos, solo sustancialmente más grande que la memoria principal disponible. Repitiendo el ejemplo anterior con 1 GB de almacenamiento SSD temporal, el primer paso podría fusionar fragmentos ordenados de 10 × 100 MB leídos de ese espacio temporal para escribir fragmentos ordenados de 50 × 1 GB en el HDD. El alto ancho de banda y el rendimiento de lectura aleatoria de los SSD ayudan a acelerar el primer paso, y las lecturas del HDD para el segundo paso pueden ser de 2 MB, lo suficientemente grandes como para que las búsquedas no ocupen la mayor parte del tiempo de lectura. Los SSD también se pueden usar como búferes de lectura en una fase de fusión, lo que permite menos lecturas más grandes (lecturas de 20 MB en este ejemplo) desde el almacenamiento HDD. Dado el menor costo de la capacidad SSD en relación con la RAM, los SSD pueden ser una herramienta económica para ordenar entradas grandes con memoria muy limitada.

Al igual que las ordenaciones en memoria, las ordenaciones externas eficientes requieren un tiempo O ( n log n ): los conjuntos de datos que crecen exponencialmente requieren un número de pasadas que aumenta linealmente y que toman cada una O(n) tiempo. ^[4] Bajo suposiciones razonables, al menos 500 GB de datos almacenados en un disco duro se pueden ordenar usando 1 GB de memoria principal antes de que una tercera pasada se vuelva ventajosa, y muchas veces esa cantidad de datos se pueden ordenar antes de que una cuarta pasada se vuelva útil. ^[5]

El tamaño de la memoria principal es importante. Duplicar la memoria dedicada a la clasificación reduce a la mitad la cantidad de fragmentos y la cantidad de lecturas por fragmento, lo que reduce la cantidad de búsquedas necesarias en aproximadamente tres cuartas partes. La relación entre la memoria RAM y el almacenamiento en disco en los servidores suele hacer que sea conveniente realizar clasificaciones enormes en un grupo de máquinas ^[6] en lugar de en una máquina con múltiples pasadas. Los medios con un alto rendimiento de lectura aleatoria, como las unidades de estado sólido (SSD), también aumentan la cantidad que se puede clasificar antes de que las pasadas adicionales mejoren el rendimiento.

Ordenación de distribución externa

La ordenación por distribución externa es análoga a la ordenación rápida . El algoritmo encuentra aproximadamente pivotes y los utiliza para dividir los $N$ elementos en submatrices de tamaño aproximadamente igual, cada uno de cuyos elementos es más pequeño que el siguiente, y luego recurre hasta que los tamaños de las submatrices sean menores que el tamaño del bloque . Cuando las submatrices son menores que el tamaño del bloque, la ordenación se puede realizar rápidamente porque todas las lecturas y escrituras se realizan en la memoria caché y en el modelo de memoria externa se requieren operaciones. ${\tfrac {M}{B}}$ ${\estilo de visualización O(1)}$

Sin embargo, encontrar exactamente los pivotes no sería lo suficientemente rápido como para hacer que la distribución externa sea asintóticamente óptima . En cambio, encontramos una cantidad ligeramente menor de pivotes. Para encontrar estos pivotes, el algoritmo divide los $N$ elementos de entrada en fragmentos, toma todos los elementos y utiliza de forma recursiva el algoritmo de la mediana de las medianas para encontrar los pivotes. ^[7] ${\tfrac {M}{B}}$ ${\tfrac {N}{M}}$ ${\sqrt {\tfrac {M}{16B}}}$ ${\sqrt {\tfrac {M}{B}}}$

Existe una dualidad , o similitud fundamental, entre los algoritmos basados en fusión y distribución. ^[8]

Actuación

El Sort Benchmark, creado por el científico informático Jim Gray , compara algoritmos de ordenamiento externo implementados mediante hardware y software optimizados. Las implementaciones ganadoras utilizan varias técnicas:

Utilizando el paralelismo
- Se pueden utilizar varias unidades de disco en paralelo para mejorar la velocidad de lectura y escritura secuencial. Esto puede ser una mejora muy rentable: un ganador del Sort Benchmark en la categoría Penny Sort centrada en el costo utiliza seis discos duros en una máquina de gama media. ^[9]
- El software de clasificación puede utilizar múltiples subprocesos para acelerar el proceso en computadoras multinúcleo modernas.
- El software puede utilizar E/S asincrónica para que una ejecución de datos se pueda ordenar o fusionar mientras otras ejecuciones se leen o escriben en el disco.
- Varias máquinas conectadas mediante enlaces de red rápidos pueden ordenar cada una parte de un enorme conjunto de datos en paralelo. ^[10]
Aumentar la velocidad del hardware
- El uso de más RAM para la clasificación puede reducir la cantidad de búsquedas en el disco y evitar la necesidad de más pasadas.
- Las memorias externas rápidas, como las unidades de estado sólido, pueden acelerar las clasificaciones, ya sea si los datos son lo suficientemente pequeños como para caber completamente en los SSD o, más raramente, para acelerar la clasificación de fragmentos del tamaño de un SSD en una clasificación de tres pasadas.
- Muchos otros factores pueden afectar la velocidad máxima de clasificación del hardware: velocidad de la CPU y número de núcleos, latencia de acceso a la RAM, ancho de banda de entrada/salida, velocidad de lectura/escritura del disco, tiempo de búsqueda del disco y otros. "Equilibrar" el hardware para minimizar los cuellos de botella es una parte importante del diseño de un sistema de clasificación eficiente.
- La relación costo-eficiencia y la velocidad absoluta pueden ser fundamentales, especialmente en entornos de clúster donde los costos de nodo más bajos permiten comprar más nodos.
Aumentar la velocidad del software
- Algunos participantes de Sort Benchmark utilizan una variación de la clasificación por radix para la primera fase de clasificación: separan los datos en uno de los muchos "contenedores" en función del comienzo de su valor. Los datos de Sort Benchmark son aleatorios y especialmente adecuados para esta optimización.
- Compactar la entrada, los archivos intermedios y la salida puede reducir el tiempo empleado en E/S, pero no está permitido en el punto de referencia de clasificación.
- Debido a que Sort Benchmark ordena registros largos (100 bytes) utilizando claves cortas (10 bytes), el software de ordenación a veces reorganiza las claves por separado de los valores para reducir el volumen de E/S de memoria.

Véase también

Referencias

^ Donald Knuth , El arte de la programación informática , Volumen 3: Ordenación y búsqueda , Segunda edición. Addison-Wesley, 1998, ISBN 0-201-89685-0 , Sección 5.4: Ordenación externa, págs. 248-379.
^ Ellis Horowitz y Sartaj Sahni , Fundamentos de estructuras de datos , H. Freeman & Co., ISBN 0-7167-8042-9 .
^ Donald Knuth , El arte de la programación informática , Volumen 3: Ordenación y búsqueda , Segunda edición. Addison-Wesley, 1998, ISBN 0-201-89685-0 , Sección 5.4: Ordenación externa, págs. 254 y siguientes.
^ Una forma de ver esto es que, dada una cantidad fija de memoria (por ejemplo, 1 GB) y un tamaño de lectura mínimo (por ejemplo, 2 MB), cada pasada de fusión puede fusionar una cierta cantidad de ejecuciones (como 500) en una, creando una situación de dividir y vencer similar a la ordenación por fusión en memoria.
^ Por ejemplo, supongamos que hay 500 GB de datos para ordenar, 1 GB de memoria intermedia y un solo disco con una tasa de transferencia de 200 MB/s y un tiempo de búsqueda de 20 ms. Una única fase de fusión de 500 vías utilizará búferes de 2 MB cada uno y necesitará realizar 250 K búsquedas mientras lee y luego escribe 500 GB. Pasará 5000 segundos buscando y 5000 s transfiriendo. Realizar dos pasadas de fusión como se describió anteriormente eliminaría casi por completo el tiempo de búsqueda, pero agregaría 5000 s adicionales de tiempo de transferencia de datos, por lo que este es aproximadamente el punto de equilibrio entre una ordenación de dos y tres pasadas.
^ Chris Nyberg, Mehul Shah, Sort Benchmark Home Page (enlaces a ejemplos de ordenaciones paralelas)
^ Aggarwal, Alok; Vitter, Jeffrey (1988). "La complejidad de entrada/salida de la clasificación y problemas relacionados" (PDF) . Comunicaciones de la ACM . 31 (9): 1116–1127. doi :10.1145/48529.48535.
^ JS Vitter , Algoritmos y estructuras de datos para memoria externa , Serie sobre fundamentos y tendencias en informática teórica, ahora Publishers, Hanover, MA, 2008, ISBN 978-1-60198-106-6 .
^ Nikolas Askitis, OzSort 2.0: Ordenar hasta 252 GB por un centavo
^ Rasmussen y otros, TritonSort

Enlaces externos

STXXL, un conjunto de herramientas de algoritmos que incluye ordenamiento por fusión externo
Un ejemplo de combinación de ordenamiento externo
Implementación de una fusión K-Way
Ordenación de memoria externa en Java
Ejemplo de implementación de pennysort usando matrices Judy
Ordenar punto de referencia