Algoritmo de fusión

Los algoritmos de combinación son una familia de algoritmos que toman múltiples listas ordenadas como entrada y producen una única lista como salida, que contiene todos los elementos de las listas de entrada en orden ordenado. Estos algoritmos se utilizan como subrutinas en varios algoritmos de ordenación , el más famoso de los cuales es el algoritmo de combinación .

Solicitud

El algoritmo de combinación desempeña un papel fundamental en el algoritmo de ordenación por combinación , un algoritmo de ordenación basado en la comparación . Conceptualmente, el algoritmo de ordenación por combinación consta de dos pasos:

Divida recursivamente la lista en sublistas de longitud (aproximadamente) igual, hasta que cada sublista contenga solo un elemento, o en el caso de una ordenación por fusión iterativa (de abajo hacia arriba), considere una lista de n elementos como n sublistas de tamaño 1. Una lista que contiene un solo elemento está, por definición, ordenada.
Fusionar sublistas repetidamente para crear una nueva sublista ordenada hasta que la lista única contenga todos los elementos. La lista única es la lista ordenada.

El algoritmo de fusión se utiliza repetidamente en el algoritmo de ordenación por fusión.

En la ilustración se muestra un ejemplo de ordenación por fusión. Comienza con una matriz desordenada de 7 números enteros. La matriz se divide en 7 particiones; cada partición contiene 1 elemento y se ordena. Las particiones ordenadas se fusionan para producir particiones más grandes y ordenadas, hasta que solo queda una partición, la matriz ordenada.

Fusionar dos listas

La fusión de dos listas ordenadas en una se puede realizar en tiempo lineal y en espacio lineal o constante (según el modelo de acceso a datos). El siguiente pseudocódigo demuestra un algoritmo que fusiona las listas de entrada (ya sean listas enlazadas o matrices ) $A$ y $B$ en una nueva lista $C.$ ^[1]^[2]^{: 104} La función head produce el primer elemento de una lista; " eliminar " un elemento significa quitarlo de su lista, normalmente incrementando un puntero o índice.

algoritmo merge(A, B) es  entradas A, B: lista devuelve lista C := nueva lista vacía mientras A no esté vacío y B no esté vacío, si  cabeza (A) ≤ cabeza(B) entonces añadir encabezado(A) a C dejar caer la cabeza de A demás añadir encabezado(B) a C dejar caer la cabeza de B // En este momento, A o B están vacíos. Queda por vaciar la otra lista de entrada.  mientras A no esté vacía, hazlo añadir encabezado(A) a C dejar caer la cabeza de A mientras B no esté vacío, hazlo añadir encabezado(B) a C dejar caer la cabeza de B devolver C

Cuando las entradas son listas enlazadas, este algoritmo se puede implementar para utilizar sólo una cantidad constante de espacio de trabajo; los punteros en los nodos de las listas se pueden reutilizar para la contabilidad y para construir la lista fusionada final.

En el algoritmo de ordenamiento por fusión, esta subrutina se utiliza normalmente para fusionar dos submatrices A[lo..mid] , A[mid+1..hi] de una única matriz A . Esto se puede hacer copiando las submatrices en una matriz temporal y aplicando después el algoritmo de fusión anterior. ^[1] Se puede evitar la asignación de una matriz temporal, pero a expensas de la velocidad y la facilidad de programación. Se han ideado varios algoritmos de fusión in situ, ^[3] a veces sacrificando el límite de tiempo lineal para producir un algoritmo $O$ $($ $n$ $log$ $n$ $) ;$ ^[4] consulte Ordenamiento por fusión § Variantes para obtener más información.

Fusión de K-way

$La fusión de k$ vías generaliza la fusión binaria a un número arbitrario $k$ de listas de entrada ordenadas. Las aplicaciones de la fusión de $k$ vías surgen en varios algoritmos de ordenamiento, incluyendo el ordenamiento por paciencia ^[5] y un algoritmo de ordenamiento externo que divide su entrada en $k = .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠1/METRO⁠ − 1$ bloques que caben en la memoria, los ordena uno por uno y luego fusiona estos bloques.^[2]^{: 119–120}

Existen varias soluciones para este problema. Una solución simple es hacer un bucle sobre las $k$ listas para seleccionar el elemento mínimo cada vez y repetir este bucle hasta que todas las listas estén vacías:

Entrada: una lista de $k$ listas.
Mientras alguna de las listas no esté vacía:
- Recorra las listas para encontrar aquella que tenga el primer elemento mínimo.
- Genera el elemento mínimo y lo elimina de su lista.

En el peor de los casos , este algoritmo realiza $(k -1)(n - ⁠ a / 2)$ comparaciones de elementos para realizar su trabajo si hay un total de $n elementos en$ $las$ listas.^[6] Se puede mejorar almacenando las listas en una cola de prioridad ( min-heap ) codificada por su primer elemento:

Construya un min-heap $h$ de las $k$ listas, utilizando el primer elemento como clave.
Mientras alguna de las listas no esté vacía:
- Sea $i = find-min(h)$ .
- Imprime el primer elemento de la lista $i$ y elimínalo de su lista.
- Reapilar $h$ .

Ahora es posible buscar el siguiente elemento más pequeño que se va a generar (find-min) y restaurar el orden del montón en un tiempo $de$ $O (log k)$ (más específicamente, $2⌊log k ⌋$ comparaciones ^[6] ), y el problema completo se puede resolver en un tiempo de $O (n log k)$ (aproximadamente $2n ⌊log k ⌋$ comparaciones). ^[6]^[2]^{: 119–120}

Un tercer algoritmo para el problema es una solución de divide y vencerás que se basa en el algoritmo de fusión binaria:

Si $k = 1$ , genere la lista de entrada única.
Si $k = 2$ , realice una fusión binaria.
De lo contrario, fusione recursivamente las primeras $⌊ k /2⌋$ listas y las $⌈ k /2⌉$ listas finales, luego fusione binariamente estas.

Cuando las listas de entrada de este algoritmo se ordenan por longitud, la más corta primero, requiere menos de $n ⌈log k ⌉$ comparaciones, es decir, menos de la mitad del número utilizado por el algoritmo basado en montón; en la práctica, puede ser tan rápido o lento como el algoritmo basado en montón. ^[6]

Fusión paralela

Una versión paralela del algoritmo de fusión binaria puede servir como un bloque de construcción de una ordenación por fusión paralela . El siguiente pseudocódigo demuestra este algoritmo en un estilo de divide y vencerás paralelo (adaptado de Cormen et al. ^[7]^{: 800} ). Opera en dos matrices ordenadas $A$ y $B$ y escribe la salida ordenada en la matriz $C$ . La notación A[i...j] denota la parte de $A$ desde el índice $i$ hasta $el j$ , excluyente.

El algoritmo merge(A[i...j], B[k...ℓ], C[p...q]) son  entradas A, B, C: matriz i, j, k, ℓ, p, q: índices sea m = j - i, n = ℓ - k si m < n entonces intercambia A y B // asegúrate de que A sea la matriz más grande: i, j todavía pertenecen a A; k, ℓ a B intercambiar m y n si m ≤ 0 entonces  retorna  // caso base, nada que fusionar sea r = ⌊(i + j)/2⌋ sea s = búsqueda binaria(A[r], B[k...ℓ]) sea t = p + (r - i) + (s - k) C[t] = A[r] en paralelo hacer fusionar(A[i...r], B[k...s], C[p...t]) fusionar(A[r+1...j], B[s...ℓ], C[t+1...q])

El algoritmo opera dividiendo $A$ o $B$ , el que sea mayor, en mitades (casi) iguales. Luego divide la otra matriz en una parte con valores menores que el punto medio de la primera y una parte con valores mayores o iguales. (La subrutina de búsqueda binaria devuelve el índice en $B$ donde $A [r]$ estaría, si estuviera en $B$ ; que siempre es un número entre $k$ y $ℓ$ .) Finalmente, cada par de mitades se fusiona recursivamente y, dado que las llamadas recursivas son independientes entre sí, se pueden realizar en paralelo. Se ha demostrado que el enfoque híbrido, donde se utiliza un algoritmo serial para el caso base de recursión, funciona bien en la práctica ^[8].

El trabajo realizado por el algoritmo para dos matrices que contienen un total de $n$ elementos, es decir, el tiempo de ejecución de una versión serial de la misma, es $O (n)$ . Esto es óptimo ya que se deben copiar $n elementos en$ $C.$ Para calcular el lapso del algoritmo, es necesario derivar una relación de recurrencia . Como las dos llamadas recursivas de merge son en paralelo, solo se debe considerar la más costosa de las dos llamadas. En el peor de los casos, el número máximo de elementos en una de las llamadas recursivas es como máximo ya que la matriz con más elementos está perfectamente dividida a la mitad. Sumando el costo de la Búsqueda Binaria, obtenemos esta recurrencia como límite superior: ${\textstyle {\frac {3}{4}}n}$ $\Theta \left(\log(n)\right)$

$T_{\infty }^{\text{fusión}}(n)=T_{\infty }^{\text{fusión}}\left({\frac {3}{4}}n\right)+\Theta \left(\log(n)\right)$

La solución es , lo que significa que lleva ese tiempo en una máquina ideal con un número ilimitado de procesadores. ^[7]^{: 801–802} $T_{\infty }^{\text{fusión}}(n)=\Theta \left(\log(n)^{2}\right)$

Nota: La rutina no es estable : si se separan elementos iguales dividiendo $A$ y $B$ , se intercalarán en $C$ ; además, intercambiar $A$ y $B$ destruirá el orden si los elementos iguales se distribuyen entre ambas matrices de entrada. Como resultado, cuando se utiliza para ordenar, este algoritmo produce una clasificación que no es estable.

Fusión paralela de dos listas

También existen algoritmos que introducen paralelismo en una única instancia de fusión de dos listas ordenadas. Estos pueden utilizarse en matrices de puertas programables en campo ( FPGA ), circuitos de ordenación especializados, así como en procesadores modernos con instrucciones SIMD (instrucción única y múltiples datos ).

Los algoritmos paralelos existentes se basan en modificaciones de la parte de fusión del clasificador bitónico o del mergesort impar-par . ^[9] En 2018, Saitoh M. et al. presentó MMS ^[10] para FPGAs, que se centró en eliminar una ruta de datos de retroalimentación de múltiples ciclos que impedía una canalización eficiente en hardware. También en 2018, Papaphilippou P. et al. presentó FLiMS ^[9] que mejoró la utilización y el rendimiento del hardware al requerir solo etapas de canalización de unidades de comparación e intercambio $P/2$ para fusionarse con un paralelismo de $P$ elementos por ciclo de FPGA. $Estilo de visualización: log _{2}(P)+1$

Soporte de idiomas

Algunos lenguajes de computadora proporcionan soporte integrado o de biblioteca para fusionar colecciones ordenadas .

C++

La biblioteca de plantillas estándar de C++ tiene la función std::merge , que fusiona dos rangos ordenados de iteradores , y std::inplace_merge , que fusiona dos rangos ordenados consecutivos en el lugar . Además, la clase std::list (lista enlazada) tiene su propio método de fusión que fusiona otra lista en sí misma. El tipo de los elementos fusionados debe admitir el operador menor que ( < ), o debe proporcionarse con un comparador personalizado.

C++17 permite diferentes políticas de ejecución, a saber, secuencial, paralela y paralela-no secuencial. ^[11]

Pitón

La biblioteca estándar de Python (desde 2.6) también tiene una función de fusión en el módulo heapq , que toma múltiples iterables ordenados y los fusiona en un solo iterador. ^[12]

Véase también

Referencias

^ ab Skiena, Steven (2010). Manual de diseño de algoritmos (2.ª ed.). Springer Science+Business Media . pág. 123. ISBN 978-1-849-96720-4.
^ abc Kurt Mehlhorn ; Peter Sanders (2008). Algoritmos y estructuras de datos: la caja de herramientas básica. Springer. ISBN 978-3-540-77978-0.
^ Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). "Práctica ordenación por combinación in situ". Nórdico J. Computación . 3 (1): 27–40. CiteSeerX 10.1.1.22.8523 .
^ Kim, Pok-Son; Kutzner, Arne (2004). Fusión de almacenamiento mínimo estable mediante comparaciones simétricas . European Symp. Algorithms. Lecture Notes in Computer Science. Vol. 3221. págs. 714–723. CiteSeerX 10.1.1.102.4612 . doi :10.1007/978-3-540-30140-0_63. ISBN . 978-3-540-23025-0.
^ Chandramouli, Badrish; Goldstein, Jonathan (2014). La paciencia es una virtud: reconsiderando la combinación y la clasificación en los procesadores modernos . SIGMOD/PODS.
^ abcd Greene, William A. (1993). Fusión de k-vías y ordenamientos k-arios (PDF) . Actas de la 31.ª Conferencia Anual del Sudeste de la ACM, págs. 127-135.
^ ab Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009) [1990]. Introducción a los algoritmos (3.ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03384-4.
^ Victor J. Duvanenko (2011), "Fusión paralela", Diario del Dr. Dobb
^ ab Papaphilippou, Philippos; Luk, Wayne; Brooks, Chris (2022). "FLiMS: una fusión rápida y ligera de dos vías para ordenar". IEEE Transactions on Computers : 1–12. doi :10.1109/TC.2022.3146509. hdl : 10044/1/95271 . S2CID 245669103.
^ Saitoh, Makoto; Elsayed, Elsayed A.; Chu, Thiem Van; Mashimo, Susumu; Kise, Kenji (abril de 2018). "Un clasificador de fusión de hardware de alto rendimiento y rentable sin ruta de datos de retroalimentación". 2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM) . págs. 197–204. doi :10.1109/FCCM.2018.00038. ISBN 978-1-5386-5522-1.S2CID52195866 .
^ "std:merge". cppreference.com. 8 de enero de 2018. Consultado el 28 de abril de 2018 .
^ "heapq — Algoritmo de cola de montón — Documentación de Python 3.10.1".

Lectura adicional

Donald Knuth . The Art of Computer Programming , Volumen 3: Ordenación y búsqueda , Tercera edición. Addison-Wesley, 1997. ISBN 0-201-89685-0 . Páginas 158-160 de la sección 5.2.4: Ordenación por fusión. Sección 5.3.2: Fusión por comparación mínima, págs. 197-207.

Enlaces externos

Implementación de alto rendimiento de la combinación de secuencias paralelas y seriales en C# con código fuente en GitHub y en C++ GitHub