Los algoritmos de fusió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 el tipo de combinación .
Solicitud
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 . [1] [2] : 104 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.
fusión de algoritmos (A, B) son las entradas A, B: lista devuelve la lista C: = nueva lista vacía mientras que A no está vacío y B no está vacío, haga si cabeza (A) ≤ cabeza (B) entonces añadir encabezado (A) a C dejar caer la cabeza de A demás añadir encabezado (B) a C dejar caer la cabeza de B // A estas alturas, A o B están vacíos. Queda por vaciar la otra lista de entrada. mientras que A no está vacío, haz añadir encabezado (A) a C dejar caer la cabeza de A mientras que B no está vacío, haz añadir encabezado (B) a C dejar caer la cabeza de B volver 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 ordenación por fusión, esta subrutina se utiliza normalmente para fusionar dos submatrices A [lo..mid] , A [mid..hi] de una sola matriz Una . 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 expensas 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] 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 [5] y un algoritmo de clasificación externo que divide su entrada en k =1/METRO- 1 bloques que quepan 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:
- 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. [6] 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 ⌋ [6] ), y el problema completo puede ser 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:
- Si k = 1 , genera la lista de entrada única.
- Si k = 2 , realice una combinación binaria.
- De lo contrario, fusiona de forma recursiva las primeras listas ⌊ k / 2⌋ y las listas ⌈ k / 2 , finales , luego binaria fusiona 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. [6]
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. [7] : 800 ). 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 , exclusivo.
fusión de algoritmos (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, n = ℓ - k si mentonces intercambia A y B // asegúrate de que A es la matriz más grande: i, j todavía pertenecen a A; k, ℓ a B intercambiar my n si m ≤ 0 entonces devuelve // caso base, nada para 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 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 [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 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áximoya que la matriz con más elementos está perfectamente dividida por la mitad. Añadiendo el costo de la búsqueda binaria, obtenemos esta recurrencia como un límite superior:
La solucion es , lo que significa que lleva tanto tiempo en una máquina ideal con un número ilimitado de procesadores. [7] : 801–802
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 Standard Template Library tiene la función std :: merge , que fusiona dos rangos ordenados de iteradores , y std :: inplace_merge , que fusiona dos rangos ordenados consecutivos en el lugar . además, el La clase std :: list ( lista vinculada) tiene su propia método de fusión que fusiona otra lista en sí mismo. El tipo de elementos fusionados debe admitir el menor que ( < ), o se le debe proporcionar un comparador personalizado.
C ++ 17 permite diferentes políticas de ejecución, a saber, secuencial, paralela y paralela sin secuencia. [9]
Pitón
La biblioteca estándar de Python (desde 2.6) también tiene una fusionar función en el módulo heapq , que toma varios iterables ordenados y los fusiona en un solo iterador. [10]
Ver también
- Fusionar (control de revisión)
- Join (álgebra relacional)
- Unirse (SQL)
- Unirse (Unix)
Referencias
- ↑ a b Skiena, Steven (2010). El Manual de diseño de algoritmos (2ª ed.). Springer Science + Business Media . pag. 123. ISBN 978-1-849-96720-4.
- ^ a b c Kurt Mehlhorn ; Peter Sanders (2008). Algoritmos y estructuras de datos: la caja de herramientas básica . Saltador. ISBN 978-3-540-77978-0.
- ^ Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). "Mergesort práctico en el lugar". Nordic J. Computing . 3 (1): 27–40. CiteSeerX 10.1.1.22.8523 .
- ^ Kim, Pok-Son; Kutzner, Arne (2004). Almacenamiento mínimo estable que se fusiona mediante comparaciones simétricas . Symp europeo. Algoritmos. Apuntes de conferencias en Ciencias de la Computación. 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: revisando la fusión y la clasificación en los procesadores modernos . SIGMOD / PODS.
- ^ a b c d Greene, William A. (1993). Fusión k-way y Clasificaciones k-ary (PDF) . Proc. 31ª Conferencia Anual del Sureste de ACM. págs. 127-135.
- ^ a b 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), "Parallel Merge" , Diario del Dr. Dobb
- ^ "std: fusionar" . cppreference.com. 2018-01-08 . Consultado el 28 de abril de 2018 .
- ^ https://docs.python.org/library/heapq.html#heapq.merge
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