Ordenar por fusión

ImprimirCitar

Divide y algoritmo de clasificación basado en conquistas

En informática, merge sort (también comúnmente escrito como mergesort) es un algoritmo de clasificación eficiente, de propósito general y basado en la comparación. La mayoría de las implementaciones producen una clasificación estable, lo que significa que el orden de los elementos iguales es el mismo en la entrada y la salida. La ordenación por combinación es un algoritmo de divide y vencerás que fue inventado por John von Neumann en 1945. Una descripción detallada y un análisis de la ordenación por combinación de abajo hacia arriba apareció en un informe de Goldstine y von Neumann ya en 1948.

Algoritmo

Conceptualmente, una ordenación por combinación funciona de la siguiente manera:

Divide la lista sin surtidos en n sublistas, cada uno que contiene un elemento (se considera una lista de un elemento).
Repetidamente fusionar sublistas para producir nuevas sublistas clasificadas hasta que sólo queda una sublista. Esta será la lista ordenada.

Implementación de arriba hacia abajo

Ejemplo de código similar a C que usa índices para un algoritmo de clasificación de combinación de arriba hacia abajo que divide recursivamente la lista (llamada ejecuciones en este ejemplo) en sublistas hasta que el tamaño de la sublista es 1, luego combina esas sublistas para producir una lista ordenada. El paso de copiar hacia atrás se evita alternando la dirección de la fusión con cada nivel de recursividad (excepto para una copia inicial única, que también se puede evitar). Para ayudar a entender esto, considere una matriz con dos elementos. Los elementos se copian en B[] y luego se vuelven a fusionar en A[]. Si hay cuatro elementos, cuando se alcanza la parte inferior del nivel de recurrencia, las ejecuciones de un solo elemento desde A[] se fusionan con B[], y luego, en el siguiente nivel superior de recursión, esas ejecuciones de dos elementos se fusionan con A[ ]. Este patrón continúa con cada nivel de recursividad.

// Array A[] tiene los elementos para ordenar; array B[] es un array de trabajo.vacío TopDownMergeSort()A[], B[], n){} CopyArray()A, 0, n, B); // una vez copia de A[] a B[] TopDownSplitMerge()B, 0, n, A); // clasificar los datos de B[] en A[]}// Dividir A[] en 2 carreras, clasificar ambos se ejecuta en B[], fusionar ambas carreras de B[] a A[]// iBegin es inclusivo; iEnd es exclusivo (A[iEnd] no está en el set).vacío TopDownSplitMerge()B[], iBegin, iEnd, A[]){} si ()iEnd - iBegin . 1) // si el tamaño de la carrera == 1 retorno; // considerarlo ordenados // dividir la carrera más de 1 artículo en mitades iMiddle = ()iEnd + iBegin) / 2; // iMiddle = punto medio // repetitivamente clasificar ambos va desde el array A[] hasta B[] TopDownSplitMerge()A, iBegin, iMiddle, B); // ordenar la carrera izquierda TopDownSplitMerge()A, iMiddle, iEnd, B); / / / ordenar la carrera correcta // fusionar las carreras resultantes del array B[] en A[] TopDownMerge()B, iBegin, iMiddle, iEnd, A);}// Fuente izquierda la mitad es A[ iBegin:iMiddle-1].// La mitad de la fuente derecha es A[iMiddle:iEnd-1 ].// Resultado es B[ iBegin:iEnd-1 ].vacío TopDownMerge()A[], iBegin, iMiddle, iEnd, B[]){} i = iBegin, j = iMiddle;  // Mientras hay elementos en las carreras izquierda o derecha... para ()k = iBegin; k . iEnd; k++) {} // Si la cabeza de carrera izquierda existe y es la cabeza de carrera derecha existente. si ()i . iMiddle " ()j >= iEnd Silencio A[i] . A[j]) {} B[k] = A[i]; i = i + 1; } más {} B[k] = A[j]; j = j + 1; } }}vacío CopyArray()A[], iBegin, iEnd, B[]){} para ()k = iBegin; k . iEnd; k++) B[k] = A[k];}

La clasificación de toda la matriz se logra mediante TopDownMergeSort(A, B, length(A)).

Implementación ascendente

Ejemplo de código similar a C que usa índices para un algoritmo de clasificación de combinación ascendente que trata la lista como una matriz de n sublistas (llamadas ejecuciones en este ejemplo) de tamaño 1, y fusiona iterativamente sublistas de ida y vuelta entre dos búferes:

// array A[] tiene los elementos para ordenar; array B[] es un array de trabajovacío BottomUpMergeSort()A[], B[], n){} // Cada 1-element run en A ya está " surtido". // Hacer carreras sucesivamente más largas clasificadas de la longitud 2, 4, 8, 16... hasta que toda la matriz esté ordenada. para ()ancho = 1; ancho . n; ancho = 2 * ancho) {} // Array A está lleno de tiradas de ancho de longitud. para ()i = 0; i . n; i = i + 2 * ancho) {} // Combina dos carreras: A[i:i+width-1] y A[i+width:i+2*width-1] a B[] // o copiar A[i:n-1] a B[] (si (i+width ю= n)) BottomUpMerge()A, i, min()i+ancho, n), min()i+2*ancho, n), B); } // Ahora el array de trabajo B está lleno de carreras de longitud 2* ancho. // Copiar el array B para array A para la próxima iteración. // Una aplicación más eficiente cambiaría los roles de A y B. CopyArray()B, A, n); // Ahora array A está lleno de carreras de longitud 2* ancho. }}// La carrera izquierda es A[iLeft:iRight-1].// Correr derecho es A[iRight:iEnd-1 ].vacío BottomUpMerge()A[], iLeft, IRight, iEnd, B[]){} i = iLeft, j = IRight; // Mientras hay elementos en las carreras izquierda o derecha... para ()k = iLeft; k . iEnd; k++) {} // Si la cabeza de carrera izquierda existe y es la cabeza de carrera derecha existente. si ()i . IRight " ()j >= iEnd Silencio A[i] . A[j]) {} B[k] = A[i]; i = i + 1; } más {} B[k] = A[j]; j = j + 1;  } } }vacío CopyArray()B[], A[], n){} para ()i = 0; i . n; i++) A[i] = B[i];}

Implementación de arriba hacia abajo usando listas

Pseudocódigo para el algoritmo de clasificación de combinación de arriba hacia abajo que divide recursivamente la lista de entrada en sublistas más pequeñas hasta que las sublistas se ordenan de manera trivial y luego fusiona las sublistas mientras regresa la cadena de llamadas.

función merge_sort(lista m) es// Caso básico. Una lista de cero o uno elementos se clasifica, por definición. si longitud de m ≤ 1 entonces retorno m

// Caso Recursivo. En primer lugar, dividir la lista en sublistas de tamaño igual// que consiste en la primera mitad y segunda mitad de la lista.// Esto supone que las listas comienzan en el índice 0. Var izquierda:= lista vacía
 Var derecho:= lista vacía
 para cada uno x con índice i dentro m do si i (longitud de m)/2 entoncesañadir x a la izquierda
 másañadir x a la derecha

// Recursivamente ordenar ambas sublistas.izquierda:= merge_sort(left)
derecha:= merge_sort(right)

// Luego fusionar las sublistas ahora surgidas.
 retorno (izquierda, derecha)

En este ejemplo, la función merge combina las sublistas izquierda y derecha.

función (izquierda, derecha) es Var resultado:= lista vacía

 mientras izquierda no está vacía y derecho no está vacío do si primer(izquierda) ≤ primero(derecha) entoncesappend first(left) to result
izquierda:= resto(izquierda)
 másappend first(right) to result
derecho:= descanso(derecha)

// O izquierda o derecha pueden tener elementos que quedan; consumirlos.// (Sólo uno de los siguientes lazos se introducirá en realidad). mientras izquierda no está vacía doappend first(left) to result
izquierda:= resto(izquierda)
 mientras derecho no está vacío doappend first(right) to result
derecho:= descanso(derecha)
 retorno resultado

Implementación de abajo hacia arriba usando listas

Pseudocódigo para el algoritmo de clasificación de combinación de abajo hacia arriba que utiliza una pequeña matriz de tamaño fijo de referencias a nodos, donde matriz[i] es una referencia a una lista de tamaño 2ⁱ o cero. nodo es una referencia o puntero a un nodo. La función merge() sería similar a la que se muestra en el ejemplo de listas de combinación de arriba hacia abajo, combina dos listas ya ordenadas y maneja listas vacías. En este caso, merge() usaría nodo para sus parámetros de entrada y valor de retorno.

función merge_sort(nodos cabeza) es// devolver si lista vacía
 si cabeza = cero entonces retorno Nil
 Var nodos array[32]; inicialmente todo nil
 Var nodos resultado
 Var nodos siguiente
 Var int i
resultado:= cabeza
// fusionar los nodos en array
 mientras Resultado neto dosiguiente:= resultado.next;
resultado.next:= Nil
 para (i = 0; (i < 32) " (array[i] ل nil); i += 1) doresultado:= merge(array[i], resultado)
array[i]:= Nil
// no pasar el extremo de la matriz
 si i = 32 entoncesI -= 1
array[i]:= resultado
resultado:= siguiente
// fusionar el array en una lista única
resultado:= Nil
 para (i = 0; i) 1) doresultado:= merge(array[i], resultado)
 retorno resultado

Análisis

Un algoritmo de fusión recurrente utilizado para ordenar un conjunto de 7 valores enteros. Estos son los pasos que un humano tomaría para emular la fusión (top-down).

Al ordenar n objetos, la ordenación por combinación tiene un rendimiento promedio y en el peor de los casos de O(n log n). Si el tiempo de ejecución de la ordenación por fusión para una lista de longitud n es T(n), entonces la relación de recurrencia T(n) = 2T(n/2) + n se deduce de la definición del algoritmo (aplique el algoritmo a dos listas de la mitad del tamaño de la lista original y agregue los n pasos tomados para fusionar las dos listas resultantes). La forma cerrada se deriva del teorema maestro para las recurrencias de divide y vencerás.

La cantidad de comparaciones realizadas por ordenación combinada en el peor de los casos viene dada por los números de ordenación. Estos números son iguales o ligeramente menores que (n ⌈lg n⌉ − 2^{⌈lg n⌉} + 1), que está entre (n lg n − n + 1) y (n lg n + n + O(lg n)). El mejor de los casos de Merge sort requiere aproximadamente la mitad de iteraciones que el peor de los casos.

Para grandes n y una lista de entrada ordenada al azar, fusionar el número esperado (promedio) de comparación acerca α·n menos que el peor caso, donde $alpha =-1+sum _{k=0}^{infty }{frac {1}{2^{k}+1}}approx 0.2645.$

En el caso peor, la ordenación por combinación utiliza aproximadamente un 39 % menos de comparaciones que la ordenación rápida en su caso promedio y, en términos de movimientos, la ordenación por combinación La complejidad del peor de los casos es O(n log n), la misma complejidad que el mejor caso de ordenación rápida.

La ordenación combinada es más eficiente que la ordenación rápida para algunos tipos de listas si solo se puede acceder secuencialmente a los datos que se van a ordenar y, por lo tanto, es popular en lenguajes como Lisp, donde las estructuras de datos a las que se accede secuencialmente son muy comunes. A diferencia de algunas implementaciones (eficientes) de ordenación rápida, la ordenación por fusión es una ordenación estable.

La implementación más común de ordenación por combinación no ordena en su lugar; por lo tanto, se debe asignar el tamaño de memoria de la entrada para que se almacene la salida ordenada (consulte a continuación las variaciones que solo necesitan n/2 espacios adicionales).

Ordenación por fusión natural

Una ordenación de combinación natural es similar a una ordenación de combinación de abajo hacia arriba, excepto que se aprovechan las ejecuciones naturales (secuencias ordenadas) en la entrada. Se pueden aprovechar las ejecuciones monotónicas y bitónicas (alternando arriba/abajo), con listas (o cintas o archivos equivalentes) que son estructuras de datos convenientes (usadas como colas FIFO o pilas LIFO). En la ordenación de combinación de abajo hacia arriba, el punto de partida asume que cada ejecución tiene una longitud de un elemento. En la práctica, los datos de entrada aleatorios tendrán muchas ejecuciones cortas que simplemente se ordenarán. En el caso típico, es posible que la ordenación por fusión natural no necesite tantas pasadas porque hay menos ejecuciones para fusionar. En el mejor de los casos, la entrada ya está ordenada (es decir, es una ejecución), por lo que la ordenación por combinación natural solo necesita hacer una pasada a través de los datos. En muchos casos prácticos, están presentes corridas naturales largas y, por esa razón, la ordenación por fusión natural se explota como el componente clave de Timsort. Ejemplo:

Inicio: 3 4 2 1 7 5 8 9 0 6
Select runs: (3 4)(2)(1 7)(5 8 9)(0 6)
Medida: (2 3 4)(1 5 7 8 9)(0 6)
Combinación: (1 2 3 4 5 7 8 9)(0 6)
Combinación: (0 1 2 3 4 5 6 7 8 9)

Formally, el tipo de fusión natural se dice que es Runs-optimal, donde ${displaystyle {mathtt {Runs}}(L)}$ es el número de carreras en $L$ , menos uno.

Las clasificaciones de selección de reemplazo de torneo se utilizan para recopilar las carreras iniciales para algoritmos de clasificación externos.

Ordenación por fusión tipo ping-pong

En lugar de fusionar dos bloques a la vez, una combinación de ping-pong fusiona cuatro bloques a la vez. Los cuatro bloques ordenados se fusionan simultáneamente en el espacio auxiliar en dos bloques ordenados, luego los dos bloques ordenados se fusionan nuevamente en la memoria principal. Al hacerlo, se omite la operación de copia y se reduce a la mitad el número total de movimientos. Una implementación temprana de dominio público de una combinación de cuatro a la vez fue realizada por WikiSort en 2014, el método se describió más tarde ese año como una optimización para la clasificación paciente y se denominó combinación de ping-pong. Quadsort implementó el método en 2020 y lo denominó fusión cuádruple.

Ordenación por combinación in situ

Un inconveniente del tipo de combinación, cuando se implementa en arreglos, es su requisito de memoria de trabajo $O (n)$ . Se han sugerido varios métodos para reducir la memoria o hacer que la ordenación por fusión esté completamente en el lugar:

Kronrod (1969) sugirió una versión alternativa de tipo fusión que utiliza espacio adicional constante.
Katajainen et al. presentar un algoritmo que requiere una cantidad constante de memoria de trabajo: suficiente espacio de almacenamiento para mantener un elemento de la matriz de entrada, y espacio adicional para mantener $O 1)$ punteros en el array de entrada. Ellos consiguen un $O () n log n)$ tiempo ligado con pequeñas constantes, pero su algoritmo no es estable.
Se han hecho varios intentos de producir un in-place merge algoritmo que se puede combinar con un estándar (de arriba abajo o abajo) fusionar tipo para producir un tipo de fusión en el lugar. En este caso, la noción de "en el lugar" se puede relajar para significar "tomar espacio de pila logarítmica", porque el tipo de fusión estándar requiere esa cantidad de espacio para su propio uso de pilas. Fue mostrado por Geffert et al. que en el lugar, la fusión estable es posible $O () n log n)$ tiempo utilizando una cantidad constante de espacio de rasguños, pero su algoritmo es complicado y tiene altos factores constantes: fusionar arrays de longitud $n$ y $m$ puede tomar $5 n + 12 m + o () m)$ Se mueve. Este factor de alta constante y complicado algoritmo en el lugar se hizo más simple y fácil de entender. Bing-Chao Huang y Michael A. Langston presentaron un algoritmo lineal de tiempo directo práctico en el lugar de fusión para combinar una lista ordenada utilizando la cantidad fija de espacio adicional. Ambos han utilizado el trabajo de Kronrod y otros. Se fusiona en tiempo lineal y espacio extra constante. El algoritmo tarda poco más tiempo promedio que algoritmos estándar de fusión, libre de explotar las células temporales de memoria extra, por menos de un factor de dos. Aunque el algoritmo es mucho más rápido de una manera práctica, pero es inestable también para algunas listas. Pero usando conceptos similares, han podido resolver este problema. Otros algoritmos en el lugar incluyen SymMerge, que toma $O () n + m) log (n + m)$ tiempo en total y es estable. Conectar un algoritmo así en fusión aumenta su complejidad a la no linearitmica, pero todavía cuasilinear, $O () n (log n) 2)$ .
Muchas aplicaciones de clasificación externa utilizan una forma de fusión de clasificación donde la entrada se divide hasta un número mayor de sublistas, idealmente a un número para el cual fusionarlos todavía hace que el conjunto de páginas actualmente procesado encaja en la memoria principal.
Una variante moderna de fusión lineal y en el lugar es la combinación de bloques que crea una sección de valores únicos para usar como espacio de intercambio.
El espacio arriba se puede reducir a sqrt(n) utilizando búsquedas binarias y rotaciones. Este método es utilizado por la biblioteca y el surtido de C++ STL.
Una alternativa para reducir la copia en múltiples listas es asociar un nuevo campo de información con cada clave (los elementos en m se llaman claves). Este campo se utilizará para vincular las claves y cualquier información asociada en una lista ordenada (una clave y su información relacionada se llama un registro). Luego la fusión de las listas ordenadas procede cambiando los valores de enlace; no es necesario mover ningún registro en absoluto. Un campo que contiene sólo un enlace será generalmente más pequeño que un registro entero así que también se utilizará menos espacio. Esta es una técnica de clasificación estándar, no restringida a fusionarse.
Una manera sencilla de reducir la sobrecarga del espacio n/2 es mantener izquierda y derecho como estructura combinada, copiar sólo la izquierda parte de m y dirigir el espacio temporal merge rutina para colocar la salida fusionada en m. Con esta versión es mejor asignar el espacio temporal fuera del merge rutina, para que sólo se necesite una asignación. La copia excesiva mencionada anteriormente también es mitigada, ya que el último par de líneas antes del Resultado de retorno declaración (función merge en el código pseudo arriba) se vuelven superfluos.

Utilizar con unidades de cinta

Los algoritmos de tipo de fusión permitieron que grandes conjuntos de datos se clasificaran en computadoras tempranas que tenían pequeños recuerdos de acceso aleatorio por estándares modernos. Los registros fueron almacenados en cinta magnética y procesados a orillas de unidades de cinta magnética, como estos IBM 729s.

Una ordenación por combinación externa es práctica para ejecutar usando unidades de disco o cinta cuando los datos que se van a ordenar son demasiado grandes para caber en la memoria. La clasificación externa explica cómo se implementa la clasificación por combinación con las unidades de disco. Una clasificación típica de unidad de cinta utiliza cuatro unidades de cinta. Toda la E/S es secuencial (excepto los rebobinados al final de cada pasada). Una implementación mínima puede funcionar con solo dos búferes de registro y algunas variables de programa.

Nombrando las cuatro unidades de cinta como A, B, C, D, con los datos originales en A y usando solo dos búferes de registro, el algoritmo es similar a la implementación ascendente, usando pares de unidades de cinta en lugar de arreglos. en memoria. El algoritmo básico se puede describir de la siguiente manera:

Combina pares de registros de A; escribiendo sublistas de dos discos alternativamente a C y D.
Incorpore sublistas de dos discos de C y D en sublistas de cuatro discos; escribiendo éstos alternativamente a A y B.
Incorpore sublistas de cuatro discos de A y B en sublistas de ocho discos; escribiendo éstos alternativamente a C y D
Repita hasta que tenga una lista que contenga todos los datos, ordenados—en el registro₂()nPasa.

En lugar de comenzar con ejecuciones muy cortas, generalmente se utiliza un algoritmo híbrido, en el que el paso inicial leerá muchos registros en la memoria, realizará una ordenación interna para crear una ejecución larga y luego distribuirá esas ejecuciones largas en el conjunto de salida. El paso evita muchos pases tempranos. Por ejemplo, una ordenación interna de 1024 registros ahorrará nueve pasadas. La ordenación interna suele ser grande porque tiene ese beneficio. De hecho, existen técnicas que pueden hacer que las ejecuciones iniciales sean más largas que la memoria interna disponible. Uno de ellos, el 'quitanieves' de Knuth. (basado en un montón mínimo binario), genera ejecuciones dos veces más largas (en promedio) que el tamaño de la memoria utilizada.

Con algo de sobrecarga, el algoritmo anterior se puede modificar para usar tres cintas. El tiempo de ejecución O(n log n) también se puede lograr utilizando dos colas, una pila y una cola, o tres pilas. En la otra dirección, usando k > dos cintas (y elementos O(k) en la memoria), podemos reducir el número de operaciones de cinta en O(log k ) veces usando una combinación de k/2 vías.

Una clasificación por combinación más sofisticada que optimiza el uso de la unidad de cinta (y disco) es la clasificación por combinación polifásica.

Optimización del ordenamiento por fusión

Mezcla de azulejos aplicada a una serie de enteros aleatorios. El eje horizontal es el índice de matriz y el eje vertical es el entero.

En las computadoras modernas, la localidad de referencia puede ser de suma importancia en la optimización del software, porque se utilizan jerarquías de memoria multinivel. Se han propuesto versiones con reconocimiento de caché del algoritmo de ordenación por combinación, cuyas operaciones se han elegido específicamente para minimizar el movimiento de páginas dentro y fuera de la memoria caché de una máquina. Por ejemplo, clasificación de combinación en mosaico el algoritmo deja de particionar los subarreglos cuando se alcanzan los subarreglos de tamaño S, donde S es el número de elementos de datos que caben en la memoria caché de la CPU. Cada uno de estos subarreglos se ordena con un algoritmo de ordenación en el lugar, como la ordenación por inserción, para desalentar los intercambios de memoria, y luego se completa la ordenación por combinación normal de la manera recursiva estándar. Este algoritmo ha demostrado un mejor rendimiento en máquinas que se benefician de la optimización de caché. (LaMarca y Ladner 1997)

Orden combinado en paralelo

La ordenación por combinación se paraleliza bien debido al uso del método divide y vencerás. A lo largo de los años se han desarrollado varias variantes paralelas diferentes del algoritmo. Algunos algoritmos de ordenación de combinación paralelos están fuertemente relacionados con el algoritmo de combinación secuencial de arriba hacia abajo, mientras que otros tienen una estructura general diferente y utilizan el método de combinación K-way.

Combinar ordenación con recursividad paralela

El procedimiento de ordenación de combinación secuencial se puede describir en dos fases, la fase de división y la fase de combinación. El primero consiste en muchas llamadas recursivas que realizan repetidamente el mismo proceso de división hasta que las subsecuencias se ordenan de forma trivial (contienen un elemento o ningún elemento). Un enfoque intuitivo es la paralelización de esas llamadas recursivas. El siguiente pseudocódigo describe la ordenación por fusión con recursividad paralela utilizando las palabras clave fork y join:

// Ordenar elementos lo a través de hi (exclusivo) de array A.algoritmo mergesort(A, lo, hola) es si lo+1 entonces // Dos o más elementos.media:= ⌊(lo + hola) / 2⌋
 tenedor mergesort(A, lo, mid)
mergesort(A, mid, hi)
 Únasemerge(A, lo, mid, hi)

Este algoritmo es la modificación trivial de la versión secuencial y no se paralela bien. Por lo tanto, su velocidad no es muy impresionante. Tiene un lazo $Theta (n)$ , que es sólo una mejora de $Theta (log n)$ comparado con la versión secuencial (ver Introducción a los Algoritmos). Esto se debe principalmente al método de fusión secuencial, ya que es el cuello de botella de las ejecuciones paralelas.

Ordenación por combinación con combinación en paralelo

Se puede lograr un mejor paralelismo mediante el uso de un algoritmo de combinación paralela. Cornen et al. presentar una variante binaria que combina dos subsecuencias ordenadas en una secuencia de salida ordenada.

En una de las secuencias (la más larga si la longitud es desigual), se selecciona el elemento del índice medio. Su posición en la otra secuencia se determina de tal manera que esta secuencia permanecería ordenada si este elemento se insertara en esta posición. Por lo tanto, se sabe cuántos otros elementos de ambas secuencias son más pequeños y se puede calcular la posición del elemento seleccionado en la secuencia de salida. Para las secuencias parciales de los elementos más pequeños y más grandes creados de esta manera, el algoritmo de combinación se ejecuta nuevamente en paralelo hasta que se alcanza el caso base de la recursividad.

El siguiente pseudocódigo muestra el método de clasificación de combinación paralela modificado utilizando el algoritmo de combinación paralela (adoptado de Cormen et al.).

*
* A: matriz de entrada
* B: array de salida
* lo: límite inferior
* hola:
* off: offset
*/
algoritmo paralelo Mergesort(A, lo, hola, B, off) esLen:= hola - lo + 1
 si len == 1 entoncesB[off]:= A[lo]
 más [1..len] ser un nuevo array
media:= ⌊(lo + hola) / 2⌋
mid':= mid - lo + 1
 tenedor paralelo Mergesort(A, lo, mid, T, 1)
paraleloMergesort(A, mid + 1, hola, T, mid' + 1)
 Únase paralelo Merge(T, 1, mid', mid' + 1, len, B, off)

Para analizar una relación de recurrencia para el peor de los casos, las llamadas recursivas de ParallelMergesort deben incorporarse solo una vez debido a su ejecución en paralelo, obteniendo

{displaystyle T_{infty }^{text{sort}}(n)=T_{infty }^{text{sort}}left({frac {n}{2}}right)+T_{infty }^{text{merge}}(n)=T_{infty }^{text{sort}}left({frac {n}{2}}right)+Theta left(log(n)^{2}right).}

Para obtener información detallada sobre la complejidad del procedimiento de fusión en paralelo, consulte Algoritmo de fusión.

La solución de esta recurrencia viene dada por

{displaystyle T_{infty }^{text{sort}}=Theta left(log(n)^{3}right).}

Este algoritmo de fusión paralela alcanza un paralelismo ${textstyle Theta left({frac {n}{(log n)^{2}}}right)}$ , que es mucho más alto que el paralelismo del algoritmo anterior. Tal tipo puede funcionar bien en la práctica cuando se combina con un tipo secuencial estable rápido, como el tipo de inserción, y una fusión secuencial rápida como un caso base para fusionar pequeños arrays.

Ordenación por fusión multivía en paralelo

Parece arbitrario restringir los algoritmos de tipo fusión a un método de fusión binaria, ya que generalmente hay p > 2 procesadores disponibles. Un mejor enfoque puede ser utilizar un método de fusión K-way, una generalización de la fusión binaria, en la que $k$ secuencias ordenadas se fusionan. Esta variante de fusión es muy adecuada para describir un algoritmo de clasificación en un PRAM.

Idea básica

El proceso paralelo de fusión multiway en cuatro procesadores

t_{0}

t_{3}

Dada una secuencia sin surtir $n$ elementos, el objetivo es ordenar la secuencia con $p$ procesadores disponibles. Estos elementos se distribuyen por igual entre todos los procesadores y se clasifican localmente utilizando un algoritmo de clasificación secuencial. Por lo tanto, la secuencia consiste en secuencias ordenadas ${displaystyle S_{1},...,S_{p}}$ de longitud ${textstyle lceil {frac {n}{p}}rceil }$ . Para simplificación permite $n$ ser un múltiple de $p$ Así que ${textstyle leftvert S_{i}rightvert ={frac {n}{p}}}$ para ${displaystyle i=1,...,p}$ .

Estas secuencias se utilizarán para realizar una selección multisequence/splitter. Para ${displaystyle j=1,...,p}$ , el algoritmo determina elementos splitter ${displaystyle v_{j}}$ con rango global ${textstyle k=j{frac {n}{p}}}$ . Luego las posiciones correspondientes ${displaystyle v_{1},...,v_{p}}$ en cada secuencia $S_{i}$ se determinan con búsqueda binaria y por lo tanto el $S_{i}$ se dividen más $p$ subsecuencias ${displaystyle S_{i,1},...,S_{i,p}}$ con $<math alttext="{textstyle S_{i,j}:={xin S_{i}|rank(v_{j-1})Si,j:={}x▪ ▪ SiSilenciorank()vj− − 1).rank()x)≤ ≤ rank()vj)}{textstyle S_{i,j}:={xin S_{i}Sobrevivrank(v_{j-1})<img alt="{textstyle S_{i,j}:={xin S_{i}|rank(v_{j-1})$ .

Además, los elementos de ${displaystyle S_{1,i},...,S_{p,i}}$ se asignan al procesador $i$ , significa todos los elementos entre rango ${textstyle (i-1){frac {n}{p}}}$ y rango ${textstyle i{frac {n}{p}}}$ , que se distribuyen en todas partes $S_{i}$ . Así, cada procesador recibe una secuencia de secuencias ordenadas. El hecho de que el rango $k$ de los elementos de división $v_{i}$ fue elegido mundialmente, proporciona dos propiedades importantes: Por un lado, $k$ fue elegido para que cada procesador todavía pueda funcionar ${textstyle n/p}$ elementos después de la asignación. El algoritmo está perfectamente balanceado. Por otro lado, todos los elementos del procesador $i$ son inferiores o iguales a todos los elementos del procesador $i+1$ . Por lo tanto, cada procesador realiza el p-way fusionarse localmente y así obtiene una secuencia ordenada de sus sub-sequences. Debido a la segunda propiedad, no más p-way-merge tiene que ser realizado, los resultados sólo tienen que ser reunidos en el orden del número del procesador.

Selección multisecuencia

En su forma más simple, dada $p$ secuencias ordenadas ${displaystyle S_{1},...,S_{p}}$ distribuidos equitativamente $p$ procesadores y rango $k$ , la tarea es encontrar un elemento $x$ con un rango global $k$ en la unión de las secuencias. Por lo tanto, esto se puede utilizar para dividir cada uno $S_{i}$ en dos partes en un índice de separación $l_{i}$ , donde la parte inferior contiene sólo elementos que son más pequeños que $x$ , mientras que los elementos más grandes que $x$ se encuentran en la parte superior.

El algoritmo secuencial presentado devuelve los índices de las divisiones en cada secuencia, por ejemplo los índices $l_{i}$ en secuencias $S_{i}$ tales que ${displaystyle S_{i}[l_{i}]}$ tiene un rango global inferior a $k$ y ${displaystyle mathrm {rank} left(S_{i}[l_{i}+1]right)geq k}$ .

algoritmo msSelect(S: Array of classified Sequences [S_1,..,S_p], k: int) es para i = 1 a p do (l_i, r_i) = (0, ←S_i

 mientras existe i: l_i do// Elija Pivot Element en S_j[l_j],.., S_j[r_j], eligiendo al azar j uniformemente
v:= pickPivot(S, l, r)
para i = 1 a p do m_i = binarioSearch(v, S_i[l_i, r_i]) // sequencialmente
si m_1 +... + m_p k entonces // m_1+... + m_p es el rango global de v
r:= m // asignación vectorial
másl:= m

 retorno l

Para el análisis de complejidad se elige el modelo PRAM. Si los datos se distribuyen uniformemente en todas partes $p$ , la ejecución p-fold de la binarioSearch método tiene un tiempo de funcionamiento ${displaystyle {mathcal {O}}left(plog left(n/pright)right)}$ . La profundidad de recursión prevista es ${displaystyle {mathcal {O}}left(log left(textstyle sum _{i}|S_{i}|right)right)={mathcal {O}}(log(n))}$ como en el Quickselect ordinario. Por lo tanto, el tiempo de funcionamiento esperado en general ${displaystyle {mathcal {O}}left(plog(n/p)log(n)right)}$ .

Aplicado en el tipo de fusión multiway paralelo, este algoritmo tiene que ser invocado en paralelo tal que todos los elementos de división de rango ${textstyle i{frac {n}{p}}}$ para ${displaystyle i=1,..,p}$ se encuentran simultáneamente. Estos elementos de splitter se pueden utilizar para dividir cada secuencia en $p$ partes, con el mismo tiempo total de funcionamiento ${displaystyle {mathcal {O}}left(p,log(n/p)log(n)right)}$ .

Pseudocódigo

A continuación, se proporciona el pseudocódigo completo del algoritmo de ordenación de combinación de múltiples vías en paralelo. Suponemos que hay una barrera de sincronización antes y después de la selección de secuencias múltiples, de modo que cada procesador puede determinar los elementos de división y la partición de secuencias correctamente.

*
* d: Array sin surtido de elementos
* n: Número de elementos
* p: Número de procesadores
* Volver Array Clasificado
*/
algoritmo paraleloMultiwayMergesort(d: Array, n: int, p: int) eso:= nuevo Array[0, n] // el array de salida
 para i = 1 a p hacer en paralelo // cada procesador en paralelo
S_i:= d(i-1) * n/p, i * n/p] // Secuencia de longitud n/p
(S_i) // ordenar localmente
 Sinchv_i:= msSelect([S_1,...,S_p], i * n/p) // elemento con rango global i * n/p
 Sinch(S_i,1,..., S_i,p):= sequence_partitioning(si, v_1,..., v_p) // split s_i en subsequences

o[(i-1) * n/p, i * n/p]:= kWayMerge(s_1,i,..., s_p,i) // combinar y asignar a la matriz de salida

 retorno o

Análisis

En primer lugar, cada procesador clasifica el asignado $n/p$ elementos localmente usando un algoritmo de clasificación con complejidad ${displaystyle {mathcal {O}}left(n/p;log(n/p)right)}$ . Después de eso, los elementos de splitter deben ser calculados a tiempo ${displaystyle {mathcal {O}}left(p,log(n/p)log(n)right)}$ . Finalmente, cada grupo de $p$ las divisiones deben ser fusionadas en paralelo por cada procesador con un tiempo de funcionamiento ${displaystyle {mathcal {O}}(log(p);n/p)}$ usando un algoritmo de fusión secuencial. Por lo tanto, el tiempo de funcionamiento general es dado por

${displaystyle {mathcal {O}}left({frac {n}{p}}log left({frac {n}{p}}right)+plog left({frac {n}{p}}right)log(n)+{frac {n}{p}}log(p)right)}$ .

Adaptación práctica y aplicación

El algoritmo de ordenación por fusión multivía es muy escalable a través de su alta capacidad de paralelización, lo que permite el uso de muchos procesadores. Esto hace que el algoritmo sea un candidato viable para clasificar grandes cantidades de datos, como los que se procesan en grupos de computadoras. Además, dado que en tales sistemas la memoria no suele ser un recurso limitante, la desventaja de la complejidad espacial del tipo de fusión es insignificante. Sin embargo, otros factores adquieren importancia en tales sistemas, que no se tienen en cuenta al modelar en un PRAM. Aquí, se deben considerar los siguientes aspectos: Jerarquía de memoria, cuando los datos no caben en la memoria caché de los procesadores, o la sobrecarga de comunicación del intercambio de datos entre procesadores, que podría convertirse en un cuello de botella cuando ya no se puede acceder a los datos a través de la memoria compartida. memoria.

Sanders et al. han presentado en su papel un algoritmo paralelo sincrónico a granel para multinivel, que divide $p$ procesadores en $r$ grupos de tamaño $p'$ . Todos los procesadores ordenan localmente primero. A diferencia de un solo nivel de fusión multiway, estas secuencias se dividen en $r$ partes y asignadas a los grupos de procesadores apropiados. Estos pasos se repiten recursivamente en esos grupos. Esto reduce la comunicación y evita especialmente problemas con muchos mensajes pequeños. La estructura jerárquica de la red real subyacente se puede utilizar para definir los grupos de procesadores (por ejemplo, racks, clusters,...).

Otras variantes

Merge sort fue uno de los primeros algoritmos de clasificación en los que se logró una velocidad óptima, con Richard Cole usando un inteligente algoritmo de submuestreo para garantizar la combinación O(1). Otros algoritmos sofisticados de clasificación en paralelo pueden lograr los mismos o mejores límites de tiempo con una constante más baja. Por ejemplo, en 1991, David Powers describió una ordenación rápida paralelizada (y una ordenación radix relacionada) que puede operar en tiempo O(log n) en una máquina de acceso aleatorio paralelo CRCW. (PRAM) con n procesadores mediante la realización de particiones implícitamente. Powers muestra además que una versión canalizada de Bitonic Mergesort de Batcher en O((log n)²) tiempo en una clasificación de mariposa en la práctica, la red es realmente más rápida que sus clasificaciones O(log n) en una PRAM, y proporciona una discusión detallada de los gastos generales ocultos en comparación, radix y clasificación paralela.

Comparación con otros algoritmos de clasificación

Aunque heapsort tiene los mismos límites de tiempo que merge sort, solo requiere Θ(1) espacio auxiliar en lugar de merge sort's Θ(n). En las arquitecturas modernas típicas, las implementaciones eficientes de clasificación rápida generalmente superan la clasificación por fusión para clasificar matrices basadas en RAM. Por otro lado, la ordenación por combinación es una ordenación estable y es más eficiente en el manejo de medios secuenciales de acceso lento. La ordenación por combinación suele ser la mejor opción para ordenar una lista vinculada: en esta situación, es relativamente fácil implementar una ordenación por combinación de tal manera que solo requiera Θ(1) espacio adicional y el lento rendimiento de acceso aleatorio de una lista vinculada. list hace que algunos otros algoritmos (como quicksort) funcionen mal, y otros (como heapsort) sean completamente imposibles.

A partir de Perl 5.8, la ordenación por fusión es su algoritmo de ordenación predeterminado (era una ordenación rápida en versiones anteriores de Perl). En Java, los métodos Arrays.sort() utilizan la ordenación por combinación o una ordenación rápida ajustada en función de los tipos de datos y, para mejorar la eficiencia de la implementación, cambie a la ordenación por inserción cuando se ordenan menos de siete elementos de la matriz. El kernel de Linux usa el ordenamiento por fusión para sus listas enlazadas. Python usa Timsort, otro híbrido optimizado de clasificación por fusión y clasificación por inserción, que se ha convertido en el algoritmo de clasificación estándar en Java SE 7 (para arreglos de tipos no primitivos), en la plataforma Android y en GNU Octave.

Contenido relacionado

Más resultados...

Ordenar por fusión

Algoritmo

Implementación de arriba hacia abajo

Implementación ascendente

Implementación de arriba hacia abajo usando listas

Implementación de abajo hacia arriba usando listas

Análisis

Ordenación por fusión natural

Ordenación por fusión tipo ping-pong

Ordenación por combinación in situ

Utilizar con unidades de cinta

Optimización del ordenamiento por fusión

Orden combinado en paralelo

Combinar ordenación con recursividad paralela

Ordenación por combinación con combinación en paralelo

Ordenación por fusión multivía en paralelo

Idea básica

Selección multisecuencia

Pseudocódigo

Análisis

Adaptación práctica y aplicación

Otras variantes

Comparación con otros algoritmos de clasificación

Contenido relacionado

Teoría de colas

Entorno de escritorio

Código espagueti