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.
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 .
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.
Por ejemplo, para ordenar 900 megabytes de datos utilizando solo 100 megabytes de RAM:
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 lugar de eso, 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.
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 transferir 1 MB de datos.
Por lo tanto, para ordenar, por ejemplo, 50 GB en 100 MB de RAM, usar un solo 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. Usar dos pases de combinación resuelve el problema. Entonces, el proceso de ordenamiento podría verse así:
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 a menudo hace 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.
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.
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]
Existe una dualidad , o similitud fundamental, entre los algoritmos basados en fusión y distribución. [8]
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:
