Algoritmo de fusión

Algoritmos de combinación son una familia de algoritmos que toman múltiples listas ordenadas como entrada y producen una sola 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 clasificación, el más famoso es la clasificación por fusión.

Solicitud

Un ejemplo para combinar tipo

El algoritmo de combinación juega un papel fundamental en el algoritmo de clasificación de combinación, un algoritmo de clasificación basado en la comparación. Conceptualmente, el algoritmo de clasificación por fusión consta de dos pasos:

1. Dividir Recursivamente la lista en sublistas de (aproximadamente) igual longitud, hasta que cada sublista contenga sólo un elemento, o en el caso de iterante (abajo) fusionar tipo, considerar una lista de n elementos n sub-listas de tamaño 1. Una lista que contiene un único elemento es, por definición, ordenada.
2. Repetidamente fusionar sublistas para crear una nueva sublista clasificada hasta que la lista única contenga todos los elementos. La lista única es la lista ordenada.

El algoritmo de combinación se usa repetidamente en el algoritmo de ordenación de combinación.

En la ilustración se proporciona un ejemplo de clasificación por combinación. Comienza con una matriz desordenada de 7 enteros. La matriz se divide en 7 particiones; cada partición contiene 1 elemento y está ordenada. Luego, las particiones ordenadas se fusionan para producir particiones ordenadas más grandes, hasta que queda 1 partición, la matriz ordenada.

Fusión de dos listas

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 combina listas de entrada (ya sean listas enlazadas o matrices) A y B en una nueva lista C. La función head produce el primer elemento de una lista; "dejar caer" un elemento significa eliminarlo de su lista, generalmente incrementando un puntero o índice.

algoritmo (A, B) es insumos A, B: lista
 retornos lista

C:= nueva lista vacía
 mientras A no está vacío y B no está vacío do si cabeza(A) ≤ cabeza(B) entoncesdel apéndice (A) a C
soltar la cabeza de A
 másdel apéndice (B) a C
soltar la cabeza de B

 // Ya sea A o B está vacío. Queda por vaciar la otra lista de entrada. mientras A no está vacío dodel apéndice (A) a C
soltar la cabeza de A
 mientras B no está vacío dodel apéndice (B) a C
soltar la cabeza de B

 retorno C

Cuando las entradas son listas vinculadas, este algoritmo se puede implementar para usar solo una cantidad constante de espacio de trabajo; los punteros en las listas' los nodos se pueden reutilizar para la contabilidad y para construir la lista fusionada final.

En el algoritmo de clasificación por fusión, esta subrutina se usa normalmente para fusionar dos submatrices A[lo..mid], A[ mid+1..hi] de una sola matriz A. Esto se puede hacer copiando los subconjuntos en un conjunto temporal y luego aplicando el algoritmo de combinación anterior. Se puede evitar la asignación de una matriz temporal, pero a expensas de la velocidad y la facilidad de programación. Se han diseñado varios algoritmos de combinación en el lugar, a veces sacrificando el límite de tiempo lineal para producir un O(n log n ) algoritmo; ver Merge sort § Variantes para la discusión.

Fusión de vías K

k-way generaliza la combinación binaria a un número arbitrario k de listas de entrada ordenadas. Las aplicaciones de fusión de k-vías surgen en varios algoritmos de clasificación, incluida la clasificación paciente y un algoritmo de clasificación externo 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.

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

En el peor de los casos, este algoritmo realiza (k−1)(n−k/2< /span>) comparaciones de elementos para realizar su trabajo si hay un total de n elementos en las listas Se puede mejorar almacenando las listas en una cola de prioridad (min-heap) codificada por su primer elemento:

Ahora se puede buscar el siguiente elemento más pequeño para la salida (find-min) y restaurar el orden del montón en O(log k) tiempo (más específicamente, 2⌊log k⌋ comparaciones), y el problema completo se puede resolver en O(n log k) tiempo (aproximadamente 2n⌊log k⌋ comparaciones).

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

Cuando las listas de entrada de este algoritmo se ordenan por longitud, primero la más corta, requiere menos de n⌈log k⌉< /span> 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.

Fusión paralela

Una versión paralela del algoritmo de combinación binaria puede servir como elemento 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.). 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 j, exclusivo.

algoritmo merge(A[i...j], B[k...l], C[p...q]) es insumos A, B, C: array
i, j, k, l, p, q: índices

 Deja m = j - i,
n = l - k

 si m entoncesintercambio A y B // asegurar que A es la matriz más grande: i, j todavía pertenecen a A; k, l a Bswap m y n

 si ≤ 0 entonces retorno // caso base, nada que fusionar Deja r = ⌊(i + j)/2⌋
 Deja s = búsqueda binaria (A[r], B[k...l])
 Deja t = p + (r - i) + (s - k)
C[t] = A[r]

 en paralelomerge(A[i...r], B[k...s], C[p...t]
merge(A[r+1...j], B[s...l], C[t+1...q])

El algoritmo funciona dividiendo A o B, lo 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] sería, si estuviera en B; que este siempre 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, en el que se utiliza un algoritmo en serie para el caso base de recursividad, funciona bien en la práctica

El trabajo realizado por el algoritmo para dos arrays con un total de n elementos, es decir, el tiempo de ejecución de una versión en serie de ella, es O()n). Esto es óptimo ya que n los elementos deben ser copiados C. Para calcular la extensión del algoritmo, es necesario derivar una relación de Recurrencia. Desde las dos llamadas recurrentes merge son en paralelo, sólo es necesario considerar el costo de las dos llamadas. En el peor de los casos, el número máximo de elementos en una de las llamadas recursivas es en la mayoría ${textstyle {frac {3} {4}n}$ ya que el array con más elementos está perfectamente dividido en la mitad. Añadiendo el ${displaystyle Theta left(log(n)right)}$ costo de la búsqueda binaria, obtenemos esta recurrencia como un límite superior:

${displaystyle T_{infty } {text{merge} {n]=T_{infty }{text{merge}}left({frac] {3} {4}nright)+ Theta left(log(n)right)}$

La solución es ${displaystyle T_{infty }{text{merge}(n)=Theta left(log(n)^{2}right)}$, lo que significa que toma tanto tiempo en una máquina ideal con un número ilimitado de procesadores.

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

Fusión paralela de dos listas

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

Los algoritmos paralelos existentes se basan en modificaciones de la parte de fusión de la clasificadora bitónica o de la combinación extraña. En 2018, Saitoh M. et al. introdujeron MMS para FPGAs, que se centró en eliminar un datapath de retroalimentación multiciclo que impidió una tubería eficiente en hardware. También en 2018, Papaphilippou P. et al. presentó FLiMS que mejoró la utilización y el rendimiento del hardware sólo requiriendo ${displaystyle log _{2}(P)+1}$ etapas de tuberías P/2 unidades de comparación y cambio para combinar con un paralelismo P elementos por ciclo FPGA.

Soporte de idiomas

Algunos lenguajes informáticos brindan compatibilidad integrada o de biblioteca para fusionar colecciones ordenadas.

C++

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

C++17 permite diferentes políticas de ejecución, a saber, secuencial, paralela y paralela no secuenciada.

Pitón

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