Hispanopedia Wiki
Articulo de referencia

Merge algorithm

Merge algorithms are a family of algorithms that take multiple sorted lists as input and produce a single list as output, containing all the elements of the inputs lists in sort...

Hispanopedia WikiContenido en espanolLectura gratuita

Merge algorithms are a family of algorithms that take multiple sorted lists as input and produce a single list as output, containing all the elements of the inputs lists in sorted order. These algorithms are used as subroutines in various sorting algorithms, most famously merge sort.

Application

A graph exemplifying merge sort. Two red arrows starting from the same node indicate a split, while two green arrows ending at the same node correspond to an execution of the merge algorithm.

The merge algorithm plays a critical role in the merge sort algorithm, a comparison-based sorting algorithm. Conceptually, the merge sort algorithm consists of two steps:

  1. Recursively divide the list into sublists of (roughly) equal length, until each sublist contains only one element, or in the case of iterative (bottom up) merge sort, consider a list of n elements as n sub-lists of size 1. A list containing a single element is, by definition, sorted.
  2. Repeatedly merge sublists to create a new sorted sublist until the single list contains all elements. The single list is the sorted list.

The merge algorithm is used repeatedly in the merge sort algorithm.

An example merge sort is given in the illustration. It starts with an unsorted array of 7 integers. The array is divided into 7 partitions; each partition contains 1 element and is sorted. The sorted partitions are then merged to produce larger, sorted, partitions, until 1 partition, the sorted array, is left.

Merging two lists

Merging two sorted lists into one can be done in linear time and linear or constant space (depending on the data access model). The following pseudocode demonstrates an algorithm that merges input lists (either linked lists or arrays) A and B into a new list C.[1][2]:104 The function head yields the first element of a list; "dropping" an element means removing it from its list, typically by incrementing a pointer or index.

algorithm merge(A, B) isinputs A, B : list returns list C := new empty list while A is not empty and B is not empty doif head(A) ≤ head(B) then append head(A) to C drop the head of A else append head(B) to C drop the head of 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. [ 1 ] 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, [ 3 ] a veces sacrificando el límite de tiempo lineal para producir un algoritmo O ( n log n ) ; [ 4 ] 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]) tiene 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áximo34norte{\textstyle {\frac {3}{4}}n}ya que el array con más elementos se divide perfectamente por la mitad. Añadiendo elΘ(registro⁡(norte)){\displaystyle \Theta \left(\log(n)\right)}Costo de la búsqueda binaria, obtenemos esta recurrencia como una cota superior:

T∞unir(norte)=T∞unir(34norte)+Θ(registro⁡(norte)){\displaystyle T_{\infty }^{\text{merge}}(n)=T_{\infty }^{\text{merge}}\left({\frac {3}{4}}n\right)+\Theta \left(\log(n)\right)}

La solución esT∞unir(norte)=Θ(registro⁡(norte)2){\displaystyle 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 únicamenteregistro2⁡(PAG)+1{\displaystyle \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. [ 12 ]

Véase también

Referencias

  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.
  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 clasificació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.
  5. ↑ Chandramouli, Badrish; Goldstein, Jonathan (2014). La paciencia es una virtud: una revisión de Merge y Sort en procesadores modernos . SIGMOD/PODS.
  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 . 
  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.
  8. ^ Victor J. Duvanenko (2011), "Fusión paralela" , Diario del Dr. Dobb
  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" .

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.
  • Implementación de alto rendimiento de fusión paralela y serial en C# con código fuente en GitHub y en C++ en GitHub.