Fusionar algoritmo - Merge algorithm

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 entrada en orden ordenado. Estos algoritmos se utilizan como subrutinas en varios algoritmos de clasificación , el más famoso es el tipo de combinación .

Solicitud

Un ejemplo de ordenación por combinación

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 ordenación por fusión consta de dos pasos:

Divida recursivamente la lista en sublistas de (aproximadamente) la misma longitud, hasta que cada sublista contenga solo un elemento, o en el caso del ordenamiento por fusión iterativo (de abajo hacia arriba), considere una lista de n elementos como n sublistas de tamaño 1. A La 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 combinación se utiliza repetidamente en el algoritmo de clasificación de combinación.

En la ilustración se ofrece un ejemplo de ordenación por combinación. Comienza con una matriz sin clasificar de 7 enteros. La matriz está dividida en 7 particiones; cada partición contiene 1 elemento y está ordenada. Las particiones ordenadas se fusionan para producir particiones ordenadas más grandes, hasta que quede 1 partición, la matriz ordenada.

Fusionando dos listas

La fusión de dos listas ordenadas en una se puede hacer en tiempo lineal y espacio lineal o constante (según el modelo de acceso a datos). El siguiente pseudocódigo demuestra un algoritmo que listas de entrada fusiones (ya sea listas enlazadas o arrays ) $A$ y $B$ en una nueva lista $C$ . El encabezado de función produce el primer elemento de una lista; "Eliminar" un elemento significa eliminarlo de su lista, normalmente incrementando un puntero o índice.

algorithm merge(A, B) is
    inputs A, B : list
    returns list

    C := new empty list
    while A is not empty and B is not empty do
        if 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

    // By now, either A or B is empty. It remains to empty the other input list.
    while A is not empty do
        append head(A) to C
        drop the head of A
    while B is not empty do
        append head(B) to C
        drop the head of B

    return C

Cuando las entradas son listas enlazadas, este algoritmo se puede implementar para usar solo 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 combinada final.

En el algoritmo de combinación de tipo, esta subrutina se utiliza típicamente para fusionar dos sub-series A [lo..mid] , A [mediados + 1..hi] de una única 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 expensas de la velocidad y la facilidad de programación. Se han ideado varios algoritmos de fusión en el lugar, a veces sacrificando el límite de tiempo lineal para producir un algoritmo $O (n log n)$ ; ver Fusionar ordenación § Variantes para discusión.

Fusión de vías K

$k$ -way merging generaliza la fusión binaria a un número arbitrario $k$ de listas de entrada ordenadas. Las aplicaciones de la combinación de $k$ vías surgen en varios algoritmos de clasificación, incluida la clasificación por paciencia y un algoritmo de clasificación 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,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px} 1/METRO- 1$ bloques que quepan en la memoria, los clasifica uno por uno y luego los fusiona.

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:

Entrada: una lista de $k$ listas.
Si bien alguna de las listas no está vacía:
- Recorra las listas para encontrar la que tiene el primer elemento mínimo.
- Genere el elemento mínimo y elimínelo 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. 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, usando el primer elemento como clave.
Si bien alguna de las listas no está vacía:
- Sea $i = encontrar-min (h)$ .
- Genere el primer elemento de la lista $i$ y elimínelo de su lista.
- Vuelva a apilar $h$ .

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 hacer en tiempo $O (log k)$ (más específicamente, comparaciones $2⌊log k ⌋$ ), y el problema completo se puede resolver en $O (n log k)$ tiempo (aproximadamente $2 n ⌊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 fusión binaria:

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

Cuando las listas de entrada de este algoritmo están ordenadas 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 montones; 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 fusión binaria puede servir como un bloque de construcción de un tipo de fusión en paralelo . El siguiente pseudocódigo demuestra este algoritmo en un estilo paralelo de divide y vencerás (adaptado de Cormen et al. ). Se opera en dos matrices clasificadas $A$ y $B$ y escribe la salida ordenada a la matriz $C$ . La notación A [i ... j] denota la parte de $A$ desde el índice $i$ hasta $j$ , exclusiva.

algorithm merge(A[i...j], B[k...ℓ], C[p...q]) is
    inputs A, B, C : array
           i, j, k, ℓ, p, q : indices

    let m = j - i,
        n = ℓ - k

    if m < n then
        swap A and B  // ensure that A is the larger array: i, j still belong to A; k, ℓ to B
        swap m and n

    if m ≤ 0 then
        return  // base case, nothing to merge

    let r = ⌊(i + j)/2⌋
    let s = binary-search(A[r], B[k...ℓ])
    let t = p + (r - i) + (s - k)
    C[t] = A[r]

    in parallel do
        merge(A[i...r], B[k...s], C[p...t])
        merge(A[r+1...j], B[s...ℓ], C[t+1...q])

El algoritmo funciona dividiendo $A$ o $B$ , el que sea mayor, en mitades (casi) iguales. Luego divide la otra matriz en una parte con valores más pequeños que el punto medio de la primera y una parte con valores mayores o iguales. (Los binarios de búsqueda rendimientos de subrutina el índice en $B$ donde $A [r]$ serían, si estuviera en $B$ ; que esto siempre un número entre $k$ y $ℓ$ ). Finalmente, cada par de mitades se fusiona de forma recursiva , y puesto 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 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 desde $n$ elementos necesitan ser copiado en $C$ . Para calcular el intervalo del algoritmo, es necesario derivar una relación de recurrencia . Dado que las dos llamadas recursivas de fusión están 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 por la mitad. Sumando el costo de la búsqueda binaria, obtenemos esta recurrencia como límite superior: ${\ textstyle {\ frac {3} {4}} n}$ ${\ Displaystyle \ Theta \ left (\ log (n) \ right)}$

${\ Displaystyle T _ {\ infty} ^ {\ text {fusionar}} (n) = T _ {\ infty} ^ {\ text {fusionar}} \ left ({\ frac {3} {4}} n \ right) + \ Theta \ left (\ log (n) \ right)}$

La solución es , lo que significa que lleva tanto tiempo en una máquina ideal con un número ilimitado de procesadores. ${\ Displaystyle T _ {\ infty} ^ {\ text {fusionar}} (n) = \ Theta \ left (\ log (n) ^ {2} \ right)}$

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

Ayuda de idioma

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

C ++

El C ++ 's Biblioteca de plantillas estándar tiene la función std :: fusión , que combina dos gamas de ordenadas iteradores , y std :: inplace_merge , que se fusiona dos rangos ordenados consecutivos en el lugar . Además, la clase std :: list ( lista vinculada) tiene su propio método de fusión que fusiona otra lista en sí misma. El tipo de los elementos combinados debe admitir el operador menor que ( < ) o se debe proporcionar un comparador personalizado.

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

Pitón

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.

Ver también

Referencias

Otras lecturas

Donald Knuth . El arte de la programación informática , volumen 3: clasificació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: Clasificació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 en serie y en paralelo en C # con código fuente en GitHub y en C ++ GitHub

Languages

In other projects