Una ordenación por fusión polifásica es una variación de una ordenación por fusión ascendente que ordena una lista utilizando una distribución desigual inicial de sublistas (ejecuciones), utilizada principalmente para la ordenación externa , y es más eficiente que una ordenación por fusión normal cuando hay menos de ocho archivos de trabajo externos (como una unidad de cinta o un archivo en un disco duro). Una ordenación por fusión polifásica no es una ordenación estable .
Una ordenación por combinación divide los registros de un conjunto de datos en ejecuciones ordenadas de registros y luego fusiona repetidamente las ejecuciones ordenadas en ejecuciones ordenadas más grandes hasta que solo quede una ejecución, el conjunto de datos ordenado.
Una ordenación por fusión "equilibrada" que utiliza cuatro archivos de trabajo los organiza como un par de archivos de entrada y un par de archivos de salida. El conjunto de datos se distribuye de manera uniforme entre dos de los archivos de trabajo, ya sea como ejecuciones ordenadas o, en el caso más simple, como registros individuales, que pueden considerarse ejecuciones ordenadas de tamaño 1. Una vez que todo el conjunto de datos se transfiere a los dos archivos de trabajo, esos dos archivos de trabajo se convierten en los archivos de entrada para la primera iteración de fusión. Cada iteración de fusión fusiona ejecuciones de los dos archivos de trabajo de entrada, alternando la salida fusionada entre los dos archivos de salida, distribuyendo nuevamente las ejecuciones fusionadas de manera uniforme entre los dos archivos de salida (hasta la iteración de fusión final). Una vez que todas las ejecuciones de los dos archivos de entrada se fusionan y generan como salida, los archivos de salida se convierten en los archivos de entrada y viceversa para la siguiente iteración de fusión. La cantidad de ejecuciones disminuye en un factor de 2 en cada iteración, como 64, 32, 16, 8, 4, 2, 1. Para la iteración de fusión final, los dos archivos de entrada solo tienen una ejecución ordenada (1/2 del conjunto de datos) cada uno, y el resultado fusionado es una única ejecución ordenada (el conjunto de datos ordenado) en uno de los archivos de salida. Esto también se describe en Ordenación por fusión § Uso con unidades de cinta .
Si solo hay tres archivos de trabajo, entonces una ordenación por combinación equilibrada combina las ejecuciones ordenadas de dos archivos de trabajo en un solo archivo de trabajo y luego distribuye las ejecuciones de manera uniforme entre los dos archivos de salida. La iteración de combinación reduce el recuento de ejecuciones en un factor de 2, la iteración de redistribución no reduce el recuento de ejecuciones (el factor es 1). Se podría considerar que cada iteración reduce el recuento de ejecuciones en un factor promedio de √ 2 ≈ 1,41. Si hay 5 archivos de trabajo, entonces el patrón alterna entre una combinación de 3 vías y una combinación de 2 vías, para un factor promedio de √ 6 ≈ 2,45.
En general, para un número par N de archivos de trabajo, cada iteración de una ordenación por combinación equilibrada reduce el recuento de ejecuciones en un factor de N /2, mientras que para un número impar N de archivos de trabajo, cada iteración reduce el recuento de ejecuciones en un factor promedio de √ ( N 2 −1)/4 = √ N 2 −1 /2.
Para N < 8 archivos de trabajo, una ordenación por fusión polifásica logra un factor de reducción de recuento de ejecuciones efectivo más alto al distribuir de manera desigual las ejecuciones ordenadas entre N −1 archivos de trabajo (explicado en la siguiente sección). Cada iteración fusiona ejecuciones de N −1 archivos de trabajo en un solo archivo de trabajo de salida. Cuando se llega al final de uno de los N −1 archivos de trabajo, entonces se convierte en el nuevo archivo de salida y lo que era el archivo de salida se convierte en uno de los N −1 archivos de entrada de trabajo, comenzando una nueva iteración de ordenación por fusión polifásica. Cada iteración fusiona solo una fracción del conjunto de datos (aproximadamente 1/2 a 3/4), excepto por la última iteración que fusiona todo el conjunto de datos en una sola ejecución ordenada. La distribución inicial está configurada de modo que solo se vacía un archivo de trabajo de entrada a la vez, excepto en la iteración de fusión final que fusiona N -1 ejecuciones individuales (de tamaño variable, esto se explica a continuación) de los N -1 archivos de trabajo de entrada al archivo de salida único, lo que da como resultado una única ejecución ordenada, el conjunto de datos ordenado.
Para cada iteración polifásica, el número total de ejecuciones sigue un patrón similar a una secuencia de números de Fibonacci invertidos de orden superior . Con 4 archivos y un conjunto de datos que consta de 57 ejecuciones, el recuento total de ejecuciones en cada iteración sería 57, 31, 17, 9, 5, 3, 1. [1] [2] Tenga en cuenta que, excepto por la última iteración, el factor de reducción del recuento de ejecuciones es un poco menor que 2, 57/31, 31/17, 17/9, 9/5, 5/3, 3/1, aproximadamente 1,84 para un caso de 4 archivos, pero cada iteración excepto la última redujo el recuento de ejecuciones mientras procesaba aproximadamente el 65% del conjunto de datos, por lo que el factor de reducción del recuento de ejecuciones por conjunto de datos procesado durante las iteraciones intermedias es aproximadamente 1,84 / 0,65 = 2,83. Para un conjunto de datos que consta de 57 ejecuciones de 1 registro cada una, luego de la distribución inicial, la ordenación por fusión polifásica mueve 232 registros durante las 6 iteraciones que se necesitan para ordenar el conjunto de datos, para un factor de reducción general de 2,70 (esto se explica con más detalle más adelante).
Después de la primera iteración polifásica, lo que era el archivo de salida ahora contiene los resultados de fusionar N −1 ejecuciones originales, pero los N −2 archivos de trabajo de entrada restantes aún contienen las ejecuciones originales restantes, por lo que la segunda iteración de fusión produce ejecuciones de tamaño ( N −1) + ( N −2) = (2 N − 3) ejecuciones originales. La tercera iteración produce ejecuciones de tamaño (4 N − 7) ejecuciones originales. Con 4 archivos, la primera iteración crea ejecuciones de tamaño 3 ejecuciones originales, la segunda iteración 5 ejecuciones originales, la tercera iteración 9 ejecuciones originales y así sucesivamente, siguiendo el patrón similar a Fibonacci, 1, 3, 5, 9, 17, 31, 57, ..., por lo que el aumento en el tamaño de la ejecución sigue el mismo patrón que la disminución en el recuento de ejecuciones en reversa. En el caso de ejemplo de 4 archivos y 57 ejecuciones de 1 registro cada una, la última iteración fusiona 3 ejecuciones de tamaño 31, 17, 9, lo que da como resultado una única ejecución ordenada de tamaño 31+17+9 = 57 registros, el conjunto de datos ordenado. En la tabla 4.3 de [3] se puede encontrar un ejemplo de los recuentos de ejecuciones y los tamaños de ejecución para 4 archivos y 31 registros.
Es más fácil observar la fusión polifásica comenzando desde sus condiciones finales y trabajando hacia atrás. Al comienzo de cada iteración, habrá dos archivos de entrada y un archivo de salida. Al final de la iteración, un archivo de entrada se habrá consumido por completo y se convertirá en el archivo de salida para la siguiente iteración. El archivo de salida actual se convertirá en un archivo de entrada para la siguiente iteración. Los archivos restantes (solo uno en el caso de 3 archivos) solo se han consumido parcialmente y sus ejecuciones restantes se ingresarán para la siguiente iteración.
El archivo 1 se acaba de vaciar y se convirtió en el nuevo archivo de salida. Queda una ejecución en cada cinta de entrada y, al combinarlas, se obtendrá el archivo ordenado.
Archivo 1 (salida): <1 ejecución> * (el archivo ordenado)Archivo 2 (en ): ... | <1 ejecución> * --> ... <1 ejecución> | * (consumido)Archivo 3 (en ): | <1 ejecución> * <1 ejecución> | * (consumido)... posibles ejecuciones que ya han sido leídas| marca el puntero de lectura del archivo* marca el final del archivo
Volviendo a la iteración anterior, estábamos leyendo de 1 y 2. Se fusiona una ejecución de 1 y 2 antes de que el archivo 1 se vacíe. Observe que el archivo 2 no se consume por completo: le queda una ejecución para que coincida con la fusión final (arriba).
Archivo 1 (en ): ... | <1 ejecución> * ... <1 ejecución> | *Archivo 2 (en ): | <2 ejecución> * --> <1 ejecución> | <1 ejecución> *Archivo 3 (salida): <1 ejecución> *
Retrocediendo otra iteración, se fusionan 2 ejecuciones de 1 y 3 antes de que el archivo 3 quede vacío.
Archivo 1 (en ): | <3 ejecución> ... <2 ejecución> | <1 ejecución> *Archivo 2 (salida): --> <2 run> *Archivo 3 (en ): ... | <2 ejecución> * <2 ejecución> | *
Retrocediendo otra iteración, se fusionan 3 ejecuciones de 2 y 3 antes de que el archivo 2 quede vacío.
Archivo 1 (salida): <3 ejecución> *Archivo 2 (en ): ... | <3 run> * --> ... <3 run> | *Archivo 3 (en ): | <5 ejecución> * <3 ejecución> | <2 ejecución> *
Retrocediendo otra iteración, se fusionan 5 ejecuciones de 1 y 2 antes de que el archivo 1 quede vacío.
Archivo 1 (en ): ... | <5 ejecución> * ... <5 ejecución> | *Archivo 2 (en ): | <8 ejecución> * --> <5 ejecución> | <3 ejecución> *Archivo 3 (salida): <5 ejecución> *
Si analizamos el caso perfecto de 3 archivos, la cantidad de ejecuciones para el trabajo combinado en sentido inverso: 1, 1, 2, 3, 5, ... revela una secuencia de Fibonacci. La secuencia para más de 3 archivos es un poco más complicada; para 4 archivos, comenzando en el estado final y trabajando en sentido inverso, el patrón de conteo de ejecuciones es {1,0,0,0}, {0,1,1,1}, {1,0,2,2}, {3,2,0,4}, {7,6,4,0}, {0,13,11,7}, {13,0,24,20}, ... .
Para que todo funcione de manera óptima, la última fase de fusión debe tener exactamente una ejecución en cada archivo de entrada. Si algún archivo de entrada tiene más de una ejecución, se requerirá otra fase. En consecuencia, la ordenación por fusión polifásica debe ser inteligente en cuanto a la distribución inicial de las ejecuciones de los datos de entrada en los archivos de salida iniciales. Por ejemplo, un archivo de entrada con 13 ejecuciones escribiría 5 ejecuciones en el archivo 1 y 8 ejecuciones en el archivo 2.
En la práctica, el archivo de entrada no tendrá la cantidad exacta de ejecuciones necesarias para una distribución perfecta. Una forma de solucionar este problema es rellenar la distribución real con "ejecuciones ficticias" imaginarias para simular una distribución de ejecuciones ideal. [1] Una ejecución ficticia se comporta como una ejecución sin registros en ella. La fusión de una o más ejecuciones ficticias con una o más ejecuciones reales solo fusiona las ejecuciones reales, y la fusión de una o más ejecuciones ficticias sin ejecuciones reales da como resultado una única ejecución ficticia. Otro enfoque es emular ejecuciones ficticias según sea necesario durante las operaciones de fusión. [4]
Los algoritmos de distribución "óptimos" requieren conocer el número de ejecuciones de antemano. De lo contrario, en el caso más común donde el número de ejecuciones no se conoce de antemano, se utilizan algoritmos de distribución "casi óptimos". Algunos algoritmos de distribución incluyen la reorganización de las ejecuciones. [5] Si el número de ejecuciones se conoce de antemano, solo se necesita una distribución parcial antes de comenzar las fases de fusión. Por ejemplo, considere el caso de 3 archivos, comenzando con n ejecuciones en File_1. Defina F i = F i −1 + F i −2 como el i ésimo número de Fibonacci . Si n = F i , entonces mueva F i −2 ejecuciones a File_2, dejando F i −1 ejecuciones restantes en File_1, una distribución de ejecuciones perfecta. Si F i < n < F i +1 , mueva n − F i ejecuciones a File_2 y F i +1 − n ejecuciones a File_3. La primera iteración de fusión fusiona n − F i ejecuciones de File_1 y File_2, agregando las n − F i ejecuciones fusionadas a las F i +1 − n ejecuciones ya movidas a File_3. File_1 termina con F i −2 ejecuciones restantes, File_2 se vacía y File_3 termina con F i −1 ejecuciones, nuevamente una distribución de ejecuciones perfecta. Para 4 o más archivos, las matemáticas son más complicadas, pero el concepto es el mismo.
Después de la distribución inicial, una ordenación por combinación equilibrada que utilice 4 archivos ordenará 16 ejecuciones de un solo registro en 4 iteraciones de todo el conjunto de datos, moviendo un total de 64 registros para ordenar el conjunto de datos después de la distribución inicial. Una ordenación por combinación polifásica que utilice 4 archivos ordenará 17 ejecuciones de un solo registro en 4 iteraciones, pero como cada iteración, excepto la última, solo mueve una fracción del conjunto de datos, solo mueve un total de 48 registros para ordenar el conjunto de datos después de la distribución inicial. En este caso, el factor de ordenación por combinación equilibrada es 2,0, mientras que el factor general polifásico es ≈2,73.
Para explicar cómo se relaciona el factor de reducción con el rendimiento de clasificación, las ecuaciones del factor de reducción son:
factor_de_reducción = exp(número_de_ejecuciones*log(número_de_ejecuciones)/número_de_movimientos_de_ejecuciones)recuento_de_ejecuciones = número_de_ejecuciones * log(número_de_ejecuciones)/log(factor_de_reducción)recuento_de_movimientos_de_ejecuciones = número_de_ejecuciones * factor_de_reducción_logarítmica(número_de_ejecuciones)
Usando la ecuación de conteo de movimientos de carrera para los ejemplos anteriores:
A continuación se muestra una tabla de factores de reducción efectivos para la ordenación por combinación equilibrada y polifásica, ordenados por número de archivos, en función de ordenaciones reales de unos pocos millones de registros. Esta tabla corresponde aproximadamente al factor de reducción por conjunto de datos movido que se muestra en las figuras 3 y 4 de la ordenación por combinación equilibrada y polifásica.pdf
# archivos| fracción media de datos por iteración| | factor de reducción polifásico en datos de tamaño ideal| | | Factor de reducción equilibrado en datos de tamaño ideal| | | |3 .73 1.94 1.41 (raíz cuadrada 2)4.63 2.68 2.005 .58 3.20 2.45 (raíz cuadrada 6)6.56 3.56 3.007 .55 3.80 3.46 (raíz cuadrada 12)8.54 3.95 4.009 .53 4.07 4.47 (raíz cuadrada de 20)10 .53 4.15 5.0011 .53 4.22 5.48 (raíz cuadrada 30)12 .53 4.28 6.0032 .53 4.87 16.00
En general, la ordenación por fusión polifásica es mejor que la ordenación por fusión equilibrada cuando hay menos de 8 archivos, mientras que la ordenación por fusión equilibrada comienza a ser mejor cuando hay alrededor de 8 archivos o más. [6] [7]
