Clasificación externa

Clase de algoritmos de clasificación que pueden manejar cantidades masivas de datos.

La clasificación externa es una clase de algoritmos de clasificación que pueden manejar cantidades masivas de datos . La clasificación externa es necesaria cuando los datos que se clasifican no caben en la memoria principal de un dispositivo informático (generalmente RAM ) y, en cambio, deben residir en la memoria externa más lenta , generalmente una unidad de disco duro . Por lo tanto, los algoritmos de clasificación externos son algoritmos de memoria externa y, por lo tanto, aplicables en el modelo de cálculo de memoria externa .

Los algoritmos de clasificación externa generalmente se dividen en dos tipos, clasificación de distribución, que se parece a la clasificación rápida , y clasificación de combinación externa, que se parece a la clasificación de combinación . Este último suele utilizar una estrategia híbrida de clasificación y combinación. En la fase de clasificación, se leen, clasifican 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 solo archivo más grande.

Modelo

Ver también: modelo de memoria externa

Los algoritmos de clasificación externos se pueden analizar 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 homólogos ajenos a la memoria caché , los algoritmos de ordenación externa asintóticamente óptimos logran un tiempo de ejecución (en notación Big O ) de .${\displaystyle O\left({\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}\right)}$

Orden de combinación externa

Un ejemplo de clasificación externa es el algoritmo de clasificación de combinación externa , que es un algoritmo de combinación de K-way . Ordena los 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. A continuación , se fusiona de forma recursiva en esas listas ordenadas. Para hacer esta combinación, los elementos B de cada lista ordenada se cargan en la memoria interna y el mínimo se envía repetidamente.${\displaystyle {\tfrac {M}{B}}}$

Por ejemplo, para clasificar 900 megabytes de datos usando solo 100 megabytes de RAM:

1. Lea 100 MB de datos en la memoria principal y ordene por algún método convencional, como quicksort .
2. Escribe los datos ordenados en el disco.
3. Repita los pasos 1 y 2 hasta que todos los datos estén ordenados en fragmentos de 100 MB (hay 900 MB / 100 MB = 9 fragmentos), que ahora deben fusionarse en un solo archivo de salida.
4. Lea los primeros 10 MB (= 100 MB / (9 fragmentos + 1)) de cada fragmento ordenado en los búferes de entrada de la memoria principal y asigne los 10 MB restantes para un búfer de salida. (En la práctica, podría proporcionar un mejor rendimiento para hacer que el búfer de salida sea más grande y los búferes de entrada un poco más pequeños).
5. Realice una combinación de 9 vías y almacene el resultado en el búfer de salida. Siempre que se llene el búfer de salida, escríbalo en el archivo ordenado final y vacíelo. Siempre que alguno de los 9 búferes de entrada se vacíe, llénelo con los siguientes 10 MB de su fragmento ordenado de 100 MB asociado hasta que no haya más datos disponibles del fragmento. Este es el paso clave que hace que la clasificación de combinación externa funcione externamente, debido a que el algoritmo de combinación solo hace una pasada secuencialmente a través de cada uno de los fragmentos, no es necesario que cada fragmento se cargue por completo; más bien, las partes secuenciales del fragmento se pueden cargar según sea necesario.

Históricamente, en lugar de una ordenación, a veces se usaba un algoritmo de selección de reemplazo ^[3] para realizar la distribución inicial, para producir en promedio la mitad de los trozos de salida del doble de longitud.

Pases adicionales

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

La limitación de la fusión de un solo paso es que a medida que aumenta el número 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 transferir 1 MB de datos.

Por lo tanto, para clasificar, digamos, 50 GB en 100 MB de RAM, usar un solo paso de combinación de 500 vías no es eficiente: solo podemos leer 100 MB / 501 ≈ 200 KB de cada fragmento a la vez, por lo que 5/6 de el tiempo del disco se dedica a buscar. El uso de dos pases combinados resuelve el problema. Entonces, el proceso de clasificación podría verse así:

1. Ejecute la pasada inicial de clasificación de fragmentos como antes para crear fragmentos ordenados de 500 × 100 MB.
2. Ejecute una primera pasada de combinación combinando fragmentos de 25 × 100 MB a la vez, lo que da como resultado fragmentos ordenados de 20 × 2,5 GB.
3. Ejecute una segunda pasada de combinación para fusionar los fragmentos ordenados de 20 × 2,5 GB en un solo resultado ordenado de 50 GB

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

Al igual que los ordenamientos en memoria, los ordenamientos externos eficientes requieren un tiempo O ( n log n ): los aumentos lineales en el tamaño de los datos requieren aumentos logarítmicos en el número de pasadas, y cada pasada requiere un número lineal de lecturas y escrituras. Utilizando los grandes tamaños de memoria proporcionados por las computadoras modernas, el factor logarítmico crece muy lentamente. Bajo suposiciones razonables, se pueden clasificar al menos 500 GB de datos utilizando 1 GB de memoria principal antes de que una tercera pasada sea ventajosa, y muchas veces esa cantidad de datos se puede clasificar antes de que una cuarta pasada sea útil. ^[4] Los medios con poco tiempo de búsqueda, 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.

El tamaño de la memoria principal es importante. Duplicar la memoria dedicada a clasificar reduce a la mitad el número de fragmentos y el número de lecturas por fragmento, reduciendo el número de búsquedas requeridas en aproximadamente tres cuartos. La relación entre la RAM y el almacenamiento en disco en los servidores a menudo hace que sea conveniente realizar clasificaciones enormes en un grupo de máquinas ^{[5] en} lugar de hacerlo en una sola máquina con varias pasadas.

Tipo de distribución externa

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

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

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

Rendimiento

El Ordenar Benchmark , creado por el informático Jim Gray , compara algoritmos de ordenación externas implementadas mediante hardware y software finamente sintonizado. Las implementaciones ganadoras utilizan varias técnicas:

• Usando paralelismo
  • Se pueden utilizar varias unidades de disco en paralelo para mejorar la velocidad de escritura y lectura secuencial. Esta puede ser una mejora muy rentable: un ganador de Sort Benchmark en la categoría de Penny Sort centrada en los costos usa seis discos duros en una máquina de rango medio. ^[8]
  • El software de clasificación puede utilizar varios subprocesos para acelerar el proceso en las computadoras multinúcleo modernas.
  • El software puede utilizar E / S asincrónicas para que una ejecución de datos se pueda clasificar o fusionar mientras se leen o escriben otras ejecuciones en el disco.
  • Varias máquinas conectadas por enlaces de red rápidos pueden clasificar parte de un enorme conjunto de datos en paralelo. ^[9]
• Aumento de la velocidad del hardware
  • El uso de más RAM para clasificar puede reducir la cantidad de búsquedas de disco y evitar la necesidad de más pases.
  • La memoria externa rápida, como las unidades de estado sólido, puede acelerar las clasificaciones, ya sea si los datos son lo suficientemente pequeños como para caber completamente en SSD o, más raramente, para acelerar la clasificación de fragmentos del tamaño de 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 rentabilidad y la velocidad absoluta pueden ser críticas, especialmente en entornos de clúster donde los costos de los nodos más bajos permiten comprar más nodos.
• Aumento de la velocidad del software
  • Algunos participantes de Sort Benchmark utilizan una variación de la ordenación por base para la primera fase de la clasificación: separan los datos en uno de los muchos "contenedores" según el 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 dedicado a la E / S, pero no está permitido en la clasificación comparativa.
  • Debido a que Sort Benchmark clasifica registros largos (100 bytes) utilizando claves cortas (10 bytes), el software de clasificación a veces reordena las claves por separado de los valores para reducir el volumen de E / S de la memoria.

Ver también

• Combinación de ordenación de mainframe
• Algoritmo de memoria externa
• Funnelsort
• Clasificación de distribución ajena a la caché

Referencias

1. Donald Knuth , El arte de la programación informática , volumen 3: clasificació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: clasificació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. Para otro ejemplo, suponga 500 GB de datos para ordenar, 1 GB de memoria intermedia y un solo disco con una velocidad de transferencia de 200 MB / sy un tiempo de búsqueda de 20 ms. Una sola 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á 5.000 segundos buscando y 5.000 s transfiriendo. Hacer dos pasadas de combinación como se describió anteriormente casi eliminaría el tiempo de búsqueda, pero agregaría 5,000 s adicionales de tiempo de transferencia de datos, por lo que este es aproximadamente el punto de equilibrio entre una clasificación de dos y tres pasadas.
5. Chris Nyberg, Mehul Shah, página de inicio de Sort Benchmark (enlaces a ejemplos de clases paralelas)
6. 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 .
7. JS Vitter , Algoritmos y estructuras de datos para memoria externa , serie sobre fundamentos y tendencias en informática teórica, ahora editores, Hannover, MA, 2008, ISBN 978-1-60198-106-6 . 
8. Nikolas Askitis, OzSort 2.0: Clasificación de hasta 252 GB por un centavo
9. Rasmussen y col., TritonSort

enlaces externos

• STXXL, un conjunto de herramientas de algoritmos que incluye mergesort externo
• Un ejemplo de mergesort externo
• Una implementación de fusión de K-Way
• Clasificación de memoria externa en Java
• Una implementación de muestra de pennysort usando Judy Arrays
• Ordenar comparativa