Clasificación externa

La ordenación externa es una clase de algoritmos de ordenación que pueden manejar grandes cantidades de datos . Se requiere cuando los datos que se van a ordenar no caben en la memoria principal de un dispositivo informático (normalmente la RAM ) y, en su lugar, deben residir en la memoria externa , más lenta , generalmente un disco duro . Por lo tanto, los algoritmos de ordenación externa son algoritmos de memoria externa y, en consecuencia, aplicables al modelo de computación de memoria externa .

Los algoritmos de ordenación externa generalmente se dividen en dos tipos: ordenación por distribución, similar a quicksort , y ordenación por fusión externa, similar a mergesort . La ordenación por fusión externa suele utilizar una estrategia híbrida de ordenación y fusión. En la fase de ordenación, se leen, ordenan y escriben en un archivo temporal fragmentos de datos lo suficientemente pequeños como para caber en la memoria principal. En la fase de fusión, los subarchivos ordenados se combinan en un único archivo de mayor tamaño.

Modelo

Los algoritmos de ordenación externa pueden analizarse en el modelo de memoria externa . En este modelo, una caché o memoria 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 el número de transferencias de memoria entre la memoria interna y la externa. Al igual que sus contrapartes que no tienen en cuenta la caché , los algoritmos de ordenación externa asintóticamente óptimos alcanzan un tiempo de ejecución (en notación Big O ) de $O\left({\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}\right)$ .

ordenación de fusión externa

Un ejemplo de ordenación externa es el algoritmo de ordenación por fusión externa , que utiliza un algoritmo de fusión de K vías . Ordena bloques que caben en la RAM y luego fusiona los bloques 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 ${\tfrac {M}{B}}$ - fusión de listas ordenadas, recursiva si no hay suficiente memoria principal para fusionarlas eficientemente 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 muestra repetidamente.

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

Lee 100 MB de los datos en la memoria principal y ordénalos mediante algún método convencional, como quicksort .
Escriba los datos ordenados en el disco.
Repita los pasos 1 y 2 hasta que todos los datos estén en bloques ordenados de 100 MB (hay 900 MB / 100 MB = 9 bloques), que ahora deben fusionarse en un único archivo de salida.
Lee los primeros 10 MB (= 100 MB / (9 fragmentos + 1)) de cada fragmento ordenado en búferes de entrada en la memoria principal y asigna los 10 MB restantes para un búfer de salida. (En la práctica, podría ofrecer un mejor rendimiento aumentar el tamaño del búfer de salida y reducir ligeramente el de los búferes de entrada).
Realiza una fusión de 9 vías y almacena el resultado en el búfer de salida. Cada vez que el búfer de salida se llene, escribe su contenido en el archivo final ordenado y vacíalo. Cada vez que se vacíe cualquiera de los 9 búferes de entrada, llénalo con los siguientes 10 MB de su bloque ordenado de 100 MB asociado hasta que no haya más datos disponibles del bloque.

La fase de fusión es clave para que la ordenación por fusión externa funcione correctamente. El algoritmo de fusión solo realiza una pasada por cada bloque, por lo que no es necesario cargar todos los bloques a la vez; en su lugar, se cargan partes secuenciales del bloque 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 rendimiento de lectura aleatoria bajo, como los discos duros.

Históricamente, en lugar de una ordenación, a veces se utilizaba un algoritmo de selección por 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 muestra una ordenación en dos pasadas: primero se ordena y luego se fusiona. La ordenación finaliza con una única fusión de k vías, en lugar de una serie de pasadas de fusión de dos vías como en una ordenación por fusión típica en memoria. Esto se debe a que cada pasada de fusión lee y escribe todos los valores en el disco, por lo que la reducción del número de pasadas compensa con creces el coste adicional de una fusión de k vías.

La limitación de la fusión en una sola pasada radica en que, a medida que aumenta el número de bloques, la memoria se divide en más búferes, por lo que cada búfer es más pequeño. Finalmente, 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. Un disco duro magnético típico 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 consume el mismo tiempo que transferir 1 MB de datos.

Por lo tanto, para ordenar, digamos, 50 GB en 100 MB de RAM, usar una sola pasada de fusión de 500 vías no es eficiente: solo podemos leer 100 MB / 501 ≈ 200 KB de cada bloque a la vez, por lo que 5/6 del tiempo del disco se dedican a la búsqueda. Usar dos pasadas de fusión resuelve el problema. Entonces, el proceso de ordenación podría verse así:

Ejecute la pasada inicial de ordenación de fragmentos como antes para crear fragmentos ordenados de 500 × 100 MB.
Ejecuta una primera pasada de fusión combinando 25 fragmentos de 100 MB a la vez, lo que dará como resultado 20 fragmentos ordenados de 2,5 GB.
Ejecuta una segunda pasada de fusión para combinar los 20 fragmentos ordenados de 2,5 GB en un único resultado ordenado de 50 GB.

Aunque esto requiere una pasada adicional sobre los datos, cada lectura ahora tiene una longitud de 4 MB, por lo que solo se emplea 1/5 del tiempo de búsqueda del disco. La mejora en la eficiencia de la transferencia de datos durante las pasadas de fusión (del 16,6 % al 80 %, lo que supone una mejora de casi 5 veces ) compensa con creces la duplicación del número de pasadas de fusión.

Entre las variantes se incluye el uso de un medio intermedio, como un disco de estado sólido (SSD ), para algunas etapas; el almacenamiento temporal rápido no necesita ser lo suficientemente grande como para contener todo el conjunto de datos, solo sustancialmente mayor que la memoria principal disponible. Repitiendo el ejemplo anterior con 1 GB de almacenamiento SSD temporal, la primera pasada podría fusionar 10 bloques ordenados de 100 MB leídos desde ese espacio temporal para escribir 50 bloques ordenados de 1 GB en el disco duro (HDD). El alto ancho de banda y el rendimiento de lectura aleatoria de los SSD ayudan a acelerar la primera pasada, y las lecturas del HDD para la segunda pasada pueden ser de 2 MB, lo suficientemente grandes como para que las búsquedas no consuman 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 lecturas más grandes y menos frecuentes (lecturas de 20 MB en este ejemplo) desde el almacenamiento del HDD. Dado el menor costo de la capacidad de los SSD en comparación con la RAM, los SSD pueden ser una herramienta económica para ordenar grandes entradas con memoria muy limitada.

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

El tamaño de la memoria principal es importante. Duplicar la memoria dedicada a la ordenación reduce a la mitad el número de bloques y el número de lecturas por bloque, disminuyendo el número de búsquedas necesarias en aproximadamente tres cuartas partes. La relación entre la RAM y el almacenamiento en disco en los servidores suele hacer conveniente realizar ordenaciones de gran tamaño en un clúster de máquinas ^{[ 6 ]} en lugar de en una sola máquina con múltiples pasadas. Los medios con alto rendimiento de lectura aleatoria, como las unidades de estado sólido (SSD), también aumentan la cantidad que se puede ordenar antes de que las pasadas adicionales mejoren el rendimiento.

Clasificació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 ${\tfrac {M}{B}}$ pivota y los usa para dividir los $N$ elementos en submatrices de tamaño aproximadamente igual, cada una de cuyos elementos son todos más pequeños 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 hacer rápidamente porque todas las lecturas y escrituras se hacen en la caché , y en el modelo de memoria externa se requiere $O(1)$ operaciones.

Sin embargo, encontrar exactamente ${\tfrac {M}{B}}$ Los pivotes no serían lo suficientemente rápidos como para hacer que la ordenación de distribución externa sea asintóticamente óptima . En cambio, encontramos un número ligeramente menor de pivotes. Para encontrar estos pivotes, el algoritmo divide los $N$ elementos de entrada en ${\tfrac {N}{M}}$ trozos, y toma cada uno ${\sqrt {\tfrac {M}{16B}}}$ elementos, y utiliza recursivamente el algoritmo de la mediana de medianas para encontrar ${\sqrt {\tfrac {M}{B}}}$ pivotes. ^{[ 7 ]}

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 ordenación externos implementados mediante hardware y software optimizados. Las implementaciones ganadoras utilizan varias técnicas:

Utilizando el paralelismo
- Se pueden usar varias unidades de disco en paralelo para mejorar la velocidad de lectura y escritura secuencial. Esto puede ser una mejora muy rentable: un ganador de Sort Benchmark en la categoría Penny Sort, centrada en el costo, utiliza seis discos duros en una máquina que, por lo demás, es de gama media. ^{[ 9 ]}
- El software de clasificación puede utilizar múltiples hilos para acelerar el proceso en los ordenadores multinúcleo modernos.
- El software puede utilizar E/S asíncrona para que una secuencia de datos pueda ordenarse o fusionarse mientras otras secuencias se leen o se escriben en el disco.
- Varias máquinas conectadas por enlaces de red rápidos pueden ordenar cada una una parte de un conjunto de datos enorme en paralelo. ^{[ 10 ]}
Aumentar la velocidad del hardware
- Utilizar más RAM para la ordenación puede reducir el número de accesos al disco y evitar la necesidad de realizar más pasadas.
- Las memorias externas rápidas, como las unidades de estado sólido (SSD), pueden acelerar las operaciones de clasificación, ya sea si los datos son lo suficientemente pequeños como para caber completamente en las SSD o, más raramente, para acelerar la clasificación de bloques del tamaño de una 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 en el disco, entre otros. Equilibrar el hardware para minimizar los cuellos de botella es fundamental para diseñar un sistema de clasificación eficiente.
- La rentabilidad, así como la velocidad absoluta, pueden ser factores críticos, especialmente en entornos de clúster donde los menores costes de los nodos permiten adquirir más nodos.
Aumentar la velocidad del software
- Algunos participantes del Sort Benchmark utilizan una variación del algoritmo de ordenación por radix para la primera fase: separan los datos en varios "grupos" según el valor inicial. Los datos del Sort Benchmark son aleatorios y, por lo tanto, especialmente adecuados para esta optimización.
- La compactación de los archivos de entrada, intermedios y de salida puede reducir el tiempo dedicado a las operaciones de entrada/salida, pero no está permitida en la prueba de rendimiento Sort Benchmark.
- Debido a que la prueba de rendimiento Sort Benchmark ordena registros largos (de 100 bytes) utilizando claves cortas (de 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: Clasificació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: Clasificación externa, págs. 254 y siguientes.
↑ Una forma de verlo es que, dada una cantidad fija de memoria (por ejemplo, 1 GB) y un tamaño mínimo de lectura (por ejemplo, 2 MB), cada pasada de fusión puede combinar un cierto número de ejecuciones (como 500) en una sola, creando una situación de divide y vencerás similar a la ordenación por fusión en memoria. El tamaño de cada ordenación en memoria principal y el número de formas en cada fusión tienen un límite superior constante, por lo que no contribuyen a la complejidad asintótica (notación Big O).
↑ Por ejemplo, supongamos 500 GB de datos para ordenar, 1 GB de memoria intermedia y un solo disco con una velocidad 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 escribe 500 GB. Esto le llevará 5000 segundos de búsqueda y 5000 s de transferencia. Realizar dos pasadas de fusión como se describió anteriormente prácticamente eliminaría el tiempo de búsqueda, pero añadirí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 pasadas y una de tres pasadas.
↑ Chris Nyberg, Mehul Shah, Página principal de Sort Benchmark (enlaces a ejemplos de ordenación paralela)
↑ Aggarwal, Alok; Vitter, Jeffrey (1988). "La complejidad de entrada/salida de la clasificación y problemas relacionados" (PDF) . Communications of the 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, now Publishers, Hanover, MA, 2008, ISBN 978-1-60198-106-6.
↑ Nikolas Askitis, OzSort 2.0: Ordenando hasta 252 GB por un centavo
^ Rasmussen y otros, TritonSort

Enlaces externos

STXXL, un conjunto de herramientas de algoritmos que incluye ordenación por fusión externa
Un ejemplo de ordenación por fusión externa
Implementación de fusión K-Way
Ordenación de memoria externa en Java
Un ejemplo de implementación del método pennysort utilizando Judy Arrays.
Punto de referencia de ordenación

Ordenación externa en C#

[1] 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: Clasificación externa, págs. 248–379.

[2] Ellis Horowitz y Sartaj Sahni , Fundamentos de estructuras de datos , H. Freeman & Co., ISBN 0-7167-8042-9.

[3] 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: Clasificación externa, págs. 254 y siguientes.

[4] Una forma de verlo es que, dada una cantidad fija de memoria (por ejemplo, 1 GB) y un tamaño mínimo de lectura (por ejemplo, 2 MB), cada pasada de fusión puede combinar un cierto número de ejecuciones (como 500) en una sola, creando una situación de divide y vencerás similar a la ordenación por fusión en memoria. El tamaño de cada ordenación en memoria principal y el número de formas en cada fusión tienen un límite superior constante, por lo que no contribuyen a la complejidad asintótica (notación Big O).

[5] Por ejemplo, supongamos 500 GB de datos para ordenar, 1 GB de memoria intermedia y un solo disco con una velocidad 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 escribe 500 GB. Esto le llevará 5000 segundos de búsqueda y 5000 s de transferencia. Realizar dos pasadas de fusión como se describió anteriormente prácticamente eliminaría el tiempo de búsqueda, pero añadirí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 pasadas y una de tres pasadas.

[6] Chris Nyberg, Mehul Shah, Página principal de Sort Benchmark (enlaces a ejemplos de ordenación paralela)

[Aggarwal88-7] Aggarwal, Alok; Vitter, Jeffrey (1988). "La complejidad de entrada/salida de la clasificación y problemas relacionados" (PDF) . Communications of the ACM . 31 (9): 1116– 1127. doi : 10.1145/48529.48535 .

[8] JS Vitter , Algoritmos y estructuras de datos para memoria externa , Serie sobre fundamentos y tendencias en informática teórica, now Publishers, Hanover, MA, 2008, ISBN 978-1-60198-106-6.

[9] Nikolas Askitis, OzSort 2.0: Ordenando hasta 252 GB por un centavo

[10] Rasmussen y otros, TritonSort

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]