Los algoritmos de fusió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 entradas en orden ordenado. Estos algoritmos se utilizan como subrutinas en varios algoritmos de clasificación , el más famoso es el de clasificación por fusión .
El algoritmo de combinación juega un papel fundamental en el algoritmo de clasificación por combinación , un algoritmo de clasificación basado en comparaciones . Conceptualmente, el algoritmo de clasificación por fusión consta de dos pasos:
El algoritmo de combinación se utiliza repetidamente en el algoritmo de clasificación por combinación.
En la ilustración se muestra un ejemplo de clasificación por combinació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 está ordenada. Las particiones ordenadas luego se fusionan para producir particiones ordenadas más grandes, hasta que queda 1 partición, la matriz ordenada.
La combinació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 listas de entrada (ya sean listas enlazadas o matrices ) A y B en una nueva lista C. [1] [2] : 104 El encabezado de función produce el primer elemento de una lista; "soltar" un elemento significa eliminarlo de su lista, generalmente incrementando un puntero o índice.
la combinación del algoritmo (A, B) son las entradas A, B: la lista devuelve la lista C := nueva lista vacía mientras A no está vacío y B no está vacío, hazlo si cabeza (A) ≤ cabeza (B) entonces añadir la cabeza (A) a C dejar caer la cabeza de A demás añadir la cabeza (B) a C dejar caer la cabeza de B // Por ahora, A o B están vacíos. Queda por vaciar la otra lista de entrada. mientras A no esté vacío hazlo añadir la cabeza (A) a C dejar caer la cabeza de A mientras B no esté vacío hazlo añadir la cabeza (B) a C dejar caer la cabeza de B regresar 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 ordenación por combinación, esta subrutina se usa típicamente 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 luego aplicando el algoritmo de combinació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] sacrificando a veces el límite de tiempo lineal para producir un algoritmo O ( n log n ) ; [4] consulte Ordenación por fusión § Variantes para discusión.
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 clasificación, incluida la clasificación con paciencia [5] y un algoritmo de clasificación externo que divide su entrada en k =1/METRO− 1 bloques que caben en la memoria, los clasifica uno por uno y luego los fusiona. [2] : 119-120
Existen varias soluciones a este problema. Una solución ingenua 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:
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 ) codificada por su primer elemento:
La búsqueda del siguiente elemento más pequeño que se 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 resuelto en tiempo O ( n log k ) (aproximadamente 2 n ⌊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:
Cuando las listas de entrada de este algoritmo se ordenan por longitud, la más corta primero, se requieren 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 tan lento como el algoritmo basado en montón. [6]
Una versión paralela del algoritmo de combinación binaria puede servir como componente básico de una clasificación de combinación paralela . El siguiente pseudocódigo demuestra este algoritmo en un estilo paralelo de divide y vencerás (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 del índice i al j , exclusivo.
fusión del algoritmo (A[i...j], B[k...ℓ], C[p...q]) son las entradas A, B, C: matriz i, j, k, ℓ, p, q: índices sea m = j - i, norte = ℓ - k si m < n entonces intercambie A y B // asegúrese 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 regresa // 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 estaría A [ r ] , si estuviera en B ; que este siempre es un número entre k y ℓ .) Finalmente, cada par de mitades se fusiona recursivamente , y desde las llamadas recursivas son independientes entre sí, se pueden realizar en paralelo. Se ha demostrado que el enfoque híbrido, en el que se utiliza un algoritmo en serie para el caso base de recursividad, 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 en serie del mismo, es O ( n ) . Esto es óptimo ya que es necesario copiar n elementos en C. Para calcular la duración del algoritmo, es necesario derivar una relación de recurrencia . Dado que las dos llamadas recursivas de fusión están en paralelo, 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 ya que el array con más elementos se divide perfectamente por la mitad. Sumando el coste de la Búsqueda Binaria, obtenemos esta recurrencia como límite superior:
La solución es , lo que significa que lleva esa misma cantidad de tiempo en una máquina ideal con una cantidad ilimitada de procesadores. [7] : 801–802
Nota: La rutina no es estable : si elementos iguales se separan dividiendo A y B , se entrelazarán en C ; Además, intercambiar A y B destruirá el orden, si se distribuyen elementos iguales entre ambas matrices de entrada. Como resultado, cuando se utiliza para ordenar, este algoritmo produce una ordenación que no es estable.
También hay algoritmos que introducen paralelismo dentro de una única instancia de fusión de dos listas ordenadas. Estos se pueden utilizar en matrices de puertas programables en campo ( FPGA ), circuitos de clasificación especializados, así como en procesadores modernos con instrucciones de una sola instrucción y datos múltiples ( SIMD ).
Los algoritmos paralelos existentes se basan en modificaciones de la parte de fusión del clasificador bitónico o del mergesort par-impar . [9] En 2018, Saitoh M. et al. introdujo MMS [10] para FPGA, que se centró en eliminar una ruta de datos de retroalimentación de ciclos múltiples que impedía una canalización eficiente en el hardware. También en 2018, Papaphilippou P. et al. introdujo FLiMS [9] que mejoró la utilización y el rendimiento del hardware al requerir solo que las etapas de canalización de las unidades de comparación e intercambio P/2 se fusionen con un paralelismo de elementos P por ciclo FPGA.
Algunos lenguajes informáticos proporcionan soporte integrado o de biblioteca para fusionar colecciones ordenadas .
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 in situ . Además, la clase std::list (lista vinculada) tiene su propio método de combinación que fusiona otra lista en sí misma. El tipo de 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]
La biblioteca estándar de Python (desde 2.6) también tiene una función de combinación en el módulo heapq , que toma múltiples iterables ordenados y los combina en un solo iterador. [12]
