En informática , los algoritmos de combinación de k vías o las combinaciones de múltiples vías son un tipo específico de algoritmos de combinación de secuencias que se especializan en tomar listas ordenadas de k y fusionarlas en una sola lista ordenada. Estos algoritmos de combinación generalmente se refieren a algoritmos de combinación que aceptan un número de listas ordenadas mayor que dos. Las fusiones bidireccionales también se denominan fusiones binarias.
Fusión bidireccional
Una combinación bidireccional, o una combinación binaria, se ha estudiado ampliamente debido a su papel clave en la ordenación por combinación . Un ejemplo de esto es la combinación clásica que aparece con frecuencia en los ejemplos de ordenación de combinación. La combinación clásica genera el elemento de datos con la clave más baja en cada paso; dadas algunas listas ordenadas, produce una lista ordenada que contiene todos los elementos en cualquiera de las listas de entrada, y lo hace en un tiempo proporcional a la suma de las longitudes de las listas de entrada.
Denote por A [1..p] y B [1..q] dos matrices ordenadas en orden creciente. Además, denote por C [1..n] la matriz de salida. El algoritmo canónico de fusión de 2 vías [1] almacena los índices i, j y k en A, B y C respectivamente. Inicialmente, estos índices se refieren al primer elemento, es decir, son 1. Si A [i] De lo contrario, el algoritmo copia B [j] en C [k] y aumenta j y k. Surge un caso especial si i o j han llegado al final de A o B. En este caso, el algoritmo copia los elementos restantes de B o A en C y termina.
fusión de vías k
El problema de fusión de k vías consiste en fusionar k matrices ordenadas para producir una única matriz ordenada con los mismos elementos. Denote con n el número total de elementos. n es igual al tamaño de la matriz de salida y la suma de los tamaños de las k matrices de entrada. Para simplificar, asumimos que ninguna de las matrices de entrada está vacía. Como consecuencia, lo que simplifica los tiempos de ejecución informados. El problema se puede resolver en corriendo tiempo con espacio. Existen varios algoritmos que logran este tiempo de ejecución.
Fusión iterativa de 2 vías
El problema se puede resolver fusionando iterativamente dos de las k matrices utilizando una fusión de 2 vías hasta que solo quede una única matriz. Si las matrices se combinan en un orden arbitrario, el tiempo de ejecución resultante es solo O (kn). Esto es subóptimo.
El tiempo de ejecución se puede mejorar fusionando iterativamente el primero con el segundo, el tercero con el cuarto, y así sucesivamente. Como el número de matrices se reduce a la mitad en cada iteración, solo hay Θ (log k) iteraciones. En cada iteración, cada elemento se mueve exactamente una vez. Por lo tanto, el tiempo de ejecución por iteración está en Θ (n) ya que n es el número de elementos. Por lo tanto, el tiempo de ejecución total está en Θ (n log k).
Podemos mejorar aún más este algoritmo fusionando iterativamente las dos matrices más cortas. Está claro que esto minimiza el tiempo de ejecución y por lo tanto no puede ser peor que la estrategia descrita en el párrafo anterior. Por tanto, el tiempo de ejecución está en O (n log k). Afortunadamente, en los casos fronterizos, el tiempo de ejecución puede ser mejor. Considere, por ejemplo, el caso degenerado, donde todas las matrices menos una contienen solo un elemento. La estrategia explicada en el párrafo anterior necesita Θ (n log k) tiempo de ejecución, mientras que la mejorada solo necesita Θ (n) tiempo de ejecución.
Fusión directa de vías k
En este caso, fusionaríamos simultáneamente k-carreras.
Una implementación sencilla escanearía todas las k matrices para determinar el mínimo. Esta sencilla implementación da como resultado un tiempo de ejecución de Θ (kn). Tenga en cuenta que esto se menciona solo como una posibilidad, en aras de la discusión. Aunque funcionaría, no es eficiente.
Podemos mejorar esto calculando el elemento más pequeño más rápido. Usando montones , árboles de torneo o árboles de splay , el elemento más pequeño se puede determinar en tiempo O (log k). Por tanto, los tiempos de ejecución resultantes están en O (n log k).
El montón se usa más comúnmente, aunque un árbol de torneo es más rápido en la práctica. Un montón usa aproximadamente 2 * comparaciones log (k) en cada paso porque maneja el árbol desde la raíz hasta la parte inferior y necesita comparar ambos elementos secundarios de cada nodo. Mientras tanto, un árbol de torneo solo necesita comparaciones de log (k) porque comienza en la parte inferior del árbol y trabaja hasta la raíz, haciendo solo una comparación única en cada capa. Por lo tanto, el árbol del torneo debería ser la implementación preferida.
Montón
La idea es mantener un montón mínimo de las k listas, cada una codificada por su elemento actual más pequeño. Un algoritmo simple crea un búfer de salida con nodos del montón. Empiece por construir un montón mínimo de nodos, donde cada nodo consta de un elemento principal de la lista y el resto (o cola) de la lista. Debido a que las listas se ordenan inicialmente, el encabezado es el elemento más pequeño de cada lista; la propiedad del montón garantiza que la raíz contiene el elemento mínimo en todas las listas. Extraiga el nodo raíz del montón, agregue el elemento principal al búfer de salida, cree un nuevo nodo a partir de la cola e insértelo en el montón. Repita hasta que solo quede un nodo en el montón, momento en el que simplemente agregue la lista restante (cabeza y cola) al búfer de salida.
Usando punteros, un algoritmo de montón en el lugar [2] asigna un montón mínimo de punteros en las matrices de entrada. Inicialmente, estos punteros apuntan a los elementos más pequeños de la matriz de entrada. Los punteros están ordenados por el valor al que apuntan. En un paso de preprocesamiento de O (k), el montón se crea utilizando el procedimiento estándar de heapify. Posteriormente, el algoritmo transfiere iterativamente el elemento al que apunta el puntero raíz, aumenta este puntero y ejecuta el procedimiento de tecla de disminución estándar en el elemento raíz. El tiempo de ejecución del procedimiento de tecla de aumento está limitado por O (log k). Como hay n elementos, el tiempo total de ejecución es O (n log k).
Tenga en cuenta que muchas bibliotecas Priority Queue como C ++ stl y Java no admiten la operación de reemplazar la clave y hacer de manera iterativa disminuir la clave o filtrar hacia abajo. Hacer una función extract-min e insertar es menos eficiente.
Árbol de torneo
El árbol del torneo [3] se basa en un torneo de eliminación, como se puede encontrar en los deportes. En cada juego, compiten dos de los elementos de entrada. El ganador asciende a la siguiente ronda. Por lo tanto, obtenemos un árbol binario de juegos. La lista está ordenada en orden ascendente, por lo que el ganador de un juego es el más pequeño de ambos elementos.
Para la fusión de K-way, es más eficiente almacenar solo el perdedor de cada juego (ver imagen). Por tanto, la estructura de datos se denomina árbol perdedor. Al construir el árbol o reemplazar un elemento con el siguiente de su lista, seguimos promoviendo al ganador del juego a la cima. El árbol se llena como en un partido deportivo, pero los nodos solo almacenan al perdedor. Por lo general, se agrega un nodo adicional por encima de la raíz que representa al ganador general. Cada hoja almacena un puntero a una de las matrices de entrada. Cada nodo interno almacena un valor y un índice. El índice de un nodo interno indica de qué matriz de entrada proviene el valor. El valor contiene una copia del primer elemento de la matriz de entrada correspondiente.
El algoritmo agrega iterativamente el elemento mínimo al resultado y luego elimina el elemento de la lista de entrada correspondiente. Actualiza los nodos en la ruta desde la hoja actualizada hasta la raíz ( selección de reemplazo ). El elemento eliminado es el ganador general. Por lo tanto, ha ganado todos los juegos en el camino desde la matriz de entrada hasta la raíz. Al seleccionar un nuevo elemento de la matriz de entrada, el elemento debe competir con los perdedores anteriores en el camino hacia la raíz. Cuando se usa un árbol de perdedores, el socio para reproducir los juegos ya está almacenado en los nodos. El perdedor de cada juego repetido se escribe en el nodo y el ganador es ascendido iterativamente a la cima. Cuando se alcanza la raíz, se encontró el nuevo ganador general y se puede usar en la siguiente ronda de fusión.
Las imágenes del árbol de torneos y el árbol de perdedores de esta sección utilizan los mismos datos y se pueden comparar para comprender cómo funciona un árbol de perdedores.
Algoritmo
Un árbol de torneo se puede representar como un árbol binario balanceado agregando centinelas a las listas de entrada y agregando listas hasta que el número de listas sea una potencia de dos. El árbol equilibrado se puede almacenar en una sola matriz. Se puede llegar al elemento padre dividiendo el índice actual por dos.
Cuando se actualiza una de las hojas, se repiten todos los juegos desde la hoja hasta la raíz. En el siguiente pseudocódigo , se usa un árbol orientado a objetos en lugar de una matriz porque es más fácil de entender. Además, se supone que el número de listas para fusionar es una potencia de dos.
combinación de funciones (L1,…, Ln) buildTree (cabezas de L1,…, Ln) mientras que el árbol tiene elementos ganador: = árbol.winner ganador de salida.valor nuevo: = ganador.index.next replayGames (ganador, nuevo) // Selección de reemplazo
función replayGames (nodo, nuevo) perdedor, ganador: = playGame (nodo, nuevo) node.value: = perdedor.value node.index: = perdedor.index si nodo! = raíz replayGames (node.parent, ganador)
función buildTree (elementos) nextLayer: = new Array () mientras que los elementos no están vacíos el1: = elementos.take () el2: = elementos.taque () perdedor, ganador: = playGame (el1, el2) padre: = nuevo nodo (el1, el2, perdedor) nextLayer.add (padre) if nextLayer.size == 1 return nextLayer // solo root else return buildTree (nextLayer)
Tiempo de ejecución
Al principio, el árbol se crea primero en el tiempo Θ (k). En cada paso de la fusión, solo se deben reproducir los juegos en el camino desde el nuevo elemento hasta la raíz. En cada capa, solo se necesita una comparación. A medida que el árbol está equilibrado, la ruta desde una de las matrices de entrada a la raíz contiene solo elementos Θ (log k). En total, hay n elementos que deben transferirse. Por tanto, el tiempo de ejecución total resultante está en Θ (n log k). [3]
Ejemplo
La siguiente sección contiene un ejemplo detallado del paso de selección de reemplazo y un ejemplo de una combinación completa que contiene múltiples selecciones de reemplazo.
Selección de reemplazo
Los juegos se reproducen de abajo hacia arriba. En cada capa del árbol, compiten el elemento almacenado actualmente del nodo y el elemento que se proporcionó desde la capa inferior. El ganador asciende a la cima hasta que encontremos al nuevo ganador general. El perdedor se almacena en el nodo del árbol.
Paso | Acción |
---|---|
1 | La hoja 1 (ganador general) se reemplaza por 9, el siguiente elemento de la lista de entrada. |
2 | Repetición del juego 9 vs 7 (anterior perdedor). 7 gana porque es más pequeño. Por lo tanto, 7 se promueve a la parte superior mientras que 9 se guarda en el nodo. |
3 | Repetición del juego 7 vs 3 (anterior perdedor). 3 gana porque es más pequeño. Por lo tanto, 3 se promueve a la parte superior mientras que 7 se guarda en el nodo. |
4 | Repetición del juego 3 vs 2 (anterior perdedor). 2 gana porque es más pequeño. Por lo tanto, 2 se promueve a la parte superior mientras que 3 se guarda en el nodo. |
5 | El nuevo ganador general 2 se guarda encima de la raíz. |
Unir
Para ejecutar la fusión en sí, el elemento más pequeño general se reemplaza repetidamente con el siguiente elemento de entrada. Después de eso, se vuelven a jugar los juegos a la cima.
Este ejemplo utiliza cuatro matrices ordenadas como entrada.
{2, 7, 16}{5, 10, 20}{3, 6, 21}{4, 8, 9}
El algoritmo se inicia con los encabezados de cada lista de entrada. Usando estos elementos, se construye un árbol binario de perdedores. Para la fusión, el elemento 2 de la lista más bajo se determina observando el elemento mínimo general en la parte superior del árbol. Luego, ese valor se quita y su hoja se rellena con 7, el siguiente valor en la lista de entrada. Los juegos en el camino hacia la cima se repiten como en la sección anterior sobre la selección de reemplazos. El siguiente elemento que se elimina es 3. A partir del siguiente valor de la lista, 6, los juegos se repiten hasta la raíz. Esto se repite hasta que el mínimo del árbol es igual al infinito.
Límite de tiempo de ejecución inferior
Se puede demostrar que no existe ningún algoritmo de fusión de k vías basado en la comparación con un tiempo de ejecución en O (nf (k)) donde f crece asintóticamente más lento que un logaritmo, y n es el número total de elementos. (Excluyendo datos con distribuciones deseables, como rangos disjuntos). La prueba es una reducción directa de la clasificación basada en comparaciones. Supongamos que existía tal algoritmo, entonces podríamos construir un algoritmo basado en la comparación de clasificación con el funcionamiento de tiempo O (nf (n)) de la siguiente manera: Chop la matriz de entrada en n matrices de tamaño 1. Combinar estos n matrices con la k -way fusionar algoritmo. La matriz resultante se ordena y el algoritmo tiene un tiempo de ejecución en O (nf (n)). Esto es una contradicción con el resultado bien conocido de que no existe un algoritmo de clasificación basado en comparación con un tiempo de ejecución en el peor de los casos por debajo de O (n log n).
Clasificación externa
Las combinaciones de vías k se utilizan en procedimientos de clasificación externos. [4] Los algoritmos de clasificación externos son una clase de algoritmos de clasificación que pueden manejar cantidades masivas de datos. La clasificación externa es necesaria cuando los datos que se clasifican no caben en la memoria principal de un dispositivo informático (generalmente RAM) y, en cambio, deben residir en la memoria externa más lenta (generalmente un disco duro). Los algoritmos de combinación de vías k generalmente tienen lugar en la segunda etapa de los algoritmos de clasificación externos, al igual que lo hacen para la clasificación por combinación.
Una combinación de múltiples vías permite que los archivos fuera de la memoria se combinen en menos pasadas que en una combinación binaria. Si hay 6 ejecuciones que deben fusionarse, entonces una combinación binaria necesitaría 3 pases de combinación, a diferencia de una combinación de combinación única de 6 vías. Esta reducción de pases de combinación es especialmente importante considerando la gran cantidad de información que generalmente se ordena en primer lugar, lo que permite mayores aceleraciones y al mismo tiempo reduce la cantidad de accesos a una memoria más lenta.
Referencias
- ^ Thomas H. Cormen ; Charles E. Leiserson; Ronald L. Rivest ; Clifford Stein (2001). Introducción a los algoritmos . Prensa del MIT. págs. 28-29. ISBN 978-0-262-03293-3.
- ^ Bentley, Jon Louis (2000). Perlas de programación (2ª ed.). Addison Wesley. págs. 147-162. ISBN 0201657880.
- ^ a b Knuth, Donald (1998). "Capítulo 5.4.1. Selección de combinación y reemplazo de múltiples vías". Clasificación y búsqueda . El arte de la programación informática . 3 (2ª ed.). Addison-Wesley. págs. 252-255. ISBN 0-201-89685-0.
- ^ Shaffer, Clifford A. (26 de julio de 2012). Estructuras de datos y análisis de algoritmos en C ++, tercera edición . Corporación de mensajería. ISBN 9780486172620.