Algoritmo de fusión

Los algoritmos de fusión son una familia de algoritmos que toman como entrada varias listas ordenadas y producen como salida una única lista que contiene todos los elementos de las listas de entrada en orden ascendente. Estos algoritmos se utilizan como subrutinas en diversos algoritmos de ordenación , siendo el más conocido el de fusión .

Solicitud

El algoritmo de fusión juega un papel fundamental en el algoritmo de ordenación por fusión , un algoritmo de ordenación basado en comparaciones . Conceptualmente, el algoritmo de ordenación por fusió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 la 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.
Combina repetidamente las sublistas para crear una nueva sublista ordenada hasta que la lista resultante contenga todos los elementos. Esta 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 un arreglo desordenado de 7 enteros. El arreglo se divide en 7 particiones; cada partición contiene 1 elemento y se ordena. Luego, las particiones ordenadas se fusionan para producir particiones ordenadas más grandes, hasta que solo queda una partición: el arreglo ordenado.

Combinar dos listas

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

El algoritmo merge(A, B) recibe como entrada A, B: lista y devuelve una lista. C := nueva lista vacía Mientras A no esté vacío y B no esté vacío , si cabeza(A) ≤ cabeza(B) entonces agregar cabeza(A) a C dejar caer la cabeza de A demás agregar cabeza(B) a C deja caer la cabeza de B // A estas alturas, A o B están vacías. Solo queda vaciar la otra lista de entrada. Mientras A no esté vacía, haz agregar cabeza(A) a C dejar caer la cabeza de A mientras B no esté vacío, haga lo siguiente: agregar cabeza(B) a C deja caer la cabeza de B devolver C

Cuando las entradas son listas enlazadas, este algoritmo puede implementarse para utilizar solo una cantidad constante de espacio de trabajo; los punteros en los nodos de las listas pueden reutilizarse para la contabilidad y para construir la lista combinada final.

En el algoritmo de ordenación por fusión, esta subrutina se usa típicamente para fusionar dos submatrices A[lo..mid] y A[mid+1..hi] de una sola matriz A. Esto se puede hacer copiando las submatrices en una matriz temporal y luego aplicando el algoritmo de fusión anterior. ^[¹^] Se puede evitar la asignación de una matriz temporal, pero a costa de la velocidad y la facilidad de programación. Se han ideado varios algoritmos de fusión in situ, ^[³^] a veces sacrificando el límite de tiempo lineal para producir un algoritmo $O$ $($ $n$ $log$ $n$ $) ;$ ^[⁴^] véase Ordenación por fusión § Variantes para más información.

Fusión de vías K

$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 ordenación, incluyendo$ la ordenación por paciencia ^{[ 5 ]} y un algoritmo de ordenación externa que divide su entrada en $k = 1 / M - 1$ bloques que caben en la memoria, los ordena uno por uno y luego fusiona estos bloques. ^{[ 2 ]}^{: 119–120}

Existen varias soluciones a este problema. Una solución ingenua consiste en recorrer las $k$ listas para seleccionar el elemento mínimo en cada iteración 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:
- Recorre las listas para encontrar la que tenga el primer elemento mínimo.
- Muestra el elemento mínimo y elimínalo de su lista.

En el peor de los casos $,$ este algoritmo realiza $(k - 1)(n - k / 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 ) indexada por su primer elemento:

Construye 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 = encontrar-mínimo(h)$ .
- Muestra el primer elemento de la lista $i$ y elimínalo de dicha lista.
- Reorganizar $h$ en montículo .

$La$ búsqueda del siguiente elemento más pequeño a generar (find-min) y la restauración del orden del montón ahora se pueden realizar en tiempo $O (log k) ($ $más$ específicamente, $2⌊log k⌋$ comparaciones ^{[ 6 ]} ), y el problema completo se puede resolver en ^tiempo $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$ , imprime 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 últimas $⌈ k /2⌉$ listas, y luego fusione binariamente estas.

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

Fusión paralela

Una versión paralela del algoritmo de fusión binaria puede servir como componente básico de un algoritmo de ordenación por fusión paralelo . El siguiente pseudocódigo ilustra este algoritmo en un estilo de divide y vencerás paralelo (adaptado de Cormen et al. ^{[ 7 ]}^{: 800} ). Opera sobre dos arreglos ordenados $A$ y $B$ y escribe el resultado ordenado en el arreglo $C.$ La notación A[i...j] denota la parte de $A$ desde el índice $i$ hasta $el j$ , excluyendo ambos.

El algoritmo merge(A[i...j], B[k...ℓ], C[p...q]) recibe como entradas A, B, C: array i, j, k, ℓ, p, q: índices sea m = j - i, n = ℓ - k Si m < n, entonces intercambie A y B // asegúrese de que A sea el arreglo más grande: i, j todavía pertenecen a A; k, ℓ a B Intercambiar m y n Si m ≤ 0, entonces regresa // caso base, nada que fusionarsea 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$ , la que sea mayor, en dos mitades (casi) iguales. Luego divide la otra matriz en una parte con valores menores que el punto medio de la primera y otra con valores mayores o iguales. (La subrutina de búsqueda binaria devuelve el índice en $B$ donde estaría $A [r]$ si estuviera en $B$ ; este 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 la recursión, funciona bien en la práctica ^{[ 8 ].}

El trabajo realizado por el algoritmo para dos arreglos que contienen un total de $n$ elementos, es decir, el tiempo de ejecución de una versión serial del mismo, es $O (n)$ . Esto es óptimo ya que $n$ elementos deben copiarse en $C.$ Para calcular el alcance del algoritmo, es necesario derivar una relación de recurrencia . Dado que las dos llamadas recursivas de fusión son paralelas, solo es necesario 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 ${\textstyle {\frac {3}{4}}n}$ ya que el array con más elementos se divide perfectamente por la mitad. Añadiendo el $\Theta \left(\log(n)\right)$ Costo de la búsqueda binaria, obtenemos esta recurrencia como una cota superior:

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

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

Nota: La rutina no es estable : si se separan elementos iguales dividiendo $A$ y $B$ , se intercalarán en $C$ ; asimismo, intercambiar $A$ y $B$ destruirá el orden si los elementos iguales se distribuyen entre ambos arreglos de entrada. Por lo tanto, cuando se utiliza para ordenar, este algoritmo produce una ordenación inestable.

Fusión paralela de dos listas

También existen algoritmos que introducen paralelismo dentro de una misma operación de fusión de dos listas ordenadas. Estos se pueden utilizar en matrices de puertas programables en campo ( FPGA ), circuitos de ordenación especializados, así como en procesadores modernos con instrucciones SIMD (Single Instruction Multiple Data ).

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

Soporte de idiomas

Algunos lenguajes de programación proporcionan soporte integrado o mediante bibliotecas para fusionar colecciones ordenadas .

C++

La biblioteca de plantillas estándar de C++ incluye la función `std::merge` , que combina dos rangos ordenados de iteradores , y `std::inplace_merge` , que combina dos rangos ordenados consecutivos in situ . Además, la clase `std::list` (lista enlazada) tiene su propio método `merge` , que combina otra lista consigo misma. El tipo de los elementos combinados debe admitir el operador ` < ` o bien debe proporcionarse un comparador personalizado.

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

Pitón

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

Véase también

Referencias

1 2 Skiena, Steven (2010). Manual de diseño de algoritmos (2.ª ed.). Springer Science+Business Media . pág. 123. ISBN 978-1-849-96720-4.
1 2 3 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 estable de almacenamiento mínimo mediante comparaciones simétricas . Simposio Europeo de Algoritmos. Notas de clase en Ciencias de la Computación. 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: una revisión de Merge y Sort en procesadores modernos . SIGMOD/PODS.
1 2 3 4 Greene, William A. (1993). Fusión k-way y ordenaciones k-arias (PDF) . Actas de la 31.ª Conferencia Anual ACM del Sureste. págs. 127–135 .
^ 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
1 2 Papaphilippou, Philippos; Luk, Wayne; Brooks, Chris (2022). "FLiMS: un fusionador bidireccional rápido y ligero para la ordenación". IEEE Transactions on Computers : 1–12 . arXiv : 2112.05607 . 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) . pp. 197–204 . doi : 10.1109/FCCM.2018.00038 . ISBN 978-1-5386-5522-1. S2CID 52195866 .
↑ "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" .

Lecturas adicionales

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

Enlaces externos

Implementación de alto rendimiento de fusión paralela y serial en C# con código fuente en GitHub y en C++ en GitHub.

[skiena-1] 1 2 Skiena, Steven (2010). Manual de diseño de algoritmos (2.ª ed.). Springer Science+Business Media . pág. 123. ISBN 978-1-849-96720-4.

[toolbox-2] 1 2 3 Kurt Mehlhorn ; Peter Sanders (2008). Algoritmos y estructuras de datos: La caja de herramientas básica . Springer. ISBN 978-3-540-77978-0.

[3] 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 .

[4] Kim, Pok-Son; Kutzner, Arne (2004). Fusión estable de almacenamiento mínimo mediante comparaciones simétricas . Simposio Europeo de Algoritmos. Notas de clase en Ciencias de la Computación. 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-5] Chandramouli, Badrish; Goldstein, Jonathan (2014). La paciencia es una virtud: una revisión de Merge y Sort en procesadores modernos . SIGMOD/PODS.

[greene-6] 1 2 3 4 Greene, William A. (1993). Fusión k-way y ordenaciones k-arias (PDF) . Actas de la 31.ª Conferencia Anual ACM del Sureste. págs. 127–135 .

[clrs-7] 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.

[vjd-8] Victor J. Duvanenko (2011), "Fusión paralela" , Diario del Dr. Dobb

[flimsj-9] 1 2 Papaphilippou, Philippos; Luk, Wayne; Brooks, Chris (2022). "FLiMS: un fusionador bidireccional rápido y ligero para la ordenación". IEEE Transactions on Computers : 1–12 . arXiv : 2112.05607 . doi : 10.1109/TC.2022.3146509 . hdl : 10044/1/95271 . S2CID 245669103 .

[10] 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) . pp. 197–204 . doi : 10.1109/FCCM.2018.00038 . ISBN 978-1-5386-5522-1. S2CID 52195866 .

[11] "std:merge" . cppreference.com. 8 de enero de 2018. Consultado el 28 de abril de 2018 .

[12] "heapq — Algoritmo de cola de montón — Documentación de Python 3.10.1" .

[ 1 ]

[ 2 ]

[

[

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ].

[ 9 ]

[ 10 ]

[ 11 ]

[