En ciencias de la computación , ordenamiento por mezcla (también escrito comúnmente como mergesort ) es una de propósito general eficiente y basada en la comparación algoritmo de ordenació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 división y conquista que fue inventado por John von Neumann en 1945. [2] 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. [3]
Clase | Algoritmo de clasificación |
---|---|
Estructura de datos | Formación |
Rendimiento en el peor de los casos | |
Rendimiento en el mejor de los casos | típico, variante natural |
Rendimiento medio | |
Complejidad espacial en el peor de los casos | total con auxiliar, auxiliar con listas enlazadas [1] |
Algoritmo
Conceptualmente, una ordenación por combinación funciona de la siguiente manera:
- Divida la lista sin clasificar en n sublistas, cada una de las cuales contiene un elemento (una lista de un elemento se considera ordenada).
- Fusionar repetidamente sublistas para producir nuevas sublistas ordenadas hasta que solo quede una sublista. Esta será la lista ordenada.
Implementación de arriba hacia abajo
Ejemplo de código similar a C que usa índices para el algoritmo de clasificación de combinación de arriba hacia abajo que divide de forma recursiva la lista (denominada ejecuciones en este ejemplo) en sublistas hasta que el tamaño de la sublista es 1, luego fusiona esas sublistas para producir una lista ordenada. El paso de copia hacia atrás se evita alternando la dirección de la fusión con cada nivel de recursividad (excepto para una copia inicial única). Para ayudar a comprender esto, considere una matriz con 2 elementos. Los elementos se copian en B [] y luego se vuelven a fusionar en A []. Si hay 4 elementos, cuando se alcanza la parte inferior del nivel de recursividad, las ejecuciones de un solo elemento de A [] se fusionan con B [], y luego, en el siguiente nivel superior de recursividad, esas 2 ejecuciones de elementos se combinan con A [] . Este patrón continúa con cada nivel de recursividad.
// Array A [] tiene los elementos para ordenar; matriz B [] es una matriz de trabajo. anular TopDownMergeSort ( A [], B [], n ) { CopyArray ( A , 0 , n , B ); // copia única de A [] a B [] TopDownSplitMerge ( B , 0 , n , A ); // ordena los datos de B [] a A [] }// Dividir A [] en 2 ejecuciones, ordenar ambas ejecuciones en B [], fusionar ambas ejecuciones de B [] a A [] // iBegin es inclusivo; iEnd es exclusivo (A [iEnd] no está en el conjunto). void TopDownSplitMerge ( B [], iBegin , iEnd , A []) { if ( iEnd - iBegin <= 1 ) // if run size == 1 return ; // considerarlo ordenado // dividir la ejecución de más de 1 elemento en mitades iMiddle = ( iEnd + iBegin ) / 2 ; // iMiddle = punto medio // ordena de forma recursiva ambas ejecuciones desde la matriz A [] a B [] TopDownSplitMerge ( A , iBegin , iMiddle , B ); // ordena la ejecución de la izquierda TopDownSplitMerge ( A , iMiddle , iEnd , B ); // ordenar la ejecución correcta // fusionar las ejecuciones resultantes de la matriz B [] en A [] TopDownMerge ( B , iBegin , iMiddle , iEnd , A ); }// La mitad izquierda de la fuente es A [iBegin: iMiddle-1]. // La mitad derecha de la fuente es A [iMiddle: iEnd-1]. // El resultado es B [iBegin: iEnd-1]. anular TopDownMerge ( A [], iBegin , iMiddle , iEnd , B []) { i = iBegin , j = iMiddle ; // Si bien hay elementos en las carreras izquierda o derecha ... for ( k = iBegin ; k < iEnd ; k ++ ) { // Si existe la cabeza de carrera izquierda y es <= la cabeza de carrera derecha existente. si ( i < iMiddle && ( j > = iFin || A [ i ] <= A [ j ])) { B [ k ] = A [ i ]; i = i + 1 ; } más { B [ k ] = A [ j ]; j = j + 1 ; } } }void CopyArray ( A [], iBegin , IEND , B []) { para ( k = iBegin ; k < IEND ; k ++ ) B [ k ] = A [ k ]; }
La clasificación de toda la matriz se realiza mediante TopDownMergeSort (A, B, length (A)) .
Implementación de abajo hacia arriba
Ejemplo de código similar a C que usa índices para el algoritmo de clasificación de fusión ascendente que trata la lista como una matriz de n sublistas (llamadas ejecuciones en este ejemplo) de tamaño 1, y fusiona de forma iterativa las sublistas entre dos búferes:
// la matriz A [] tiene los elementos para ordenar; matriz B [] es una matriz de trabajo void BottomUpMergeSort ( A [], B [], n ) { // Cada ejecución de 1 elemento en A ya está "ordenada". // Realice sucesivamente corridas ordenadas más largas de longitud 2, 4, 8, 16 ... hasta que se ordene toda la matriz. for ( ancho = 1 ; ancho < n ; ancho = 2 * ancho ) { // La matriz A está llena de tramos de largo ancho. for ( i = 0 ; i < n ; i = i + 2 * width ) { // Fusionar dos ejecuciones: A [i: i + width-1] y A [i + width: i + 2 * width-1] a B [] // o copia A [i: n-1] a B [] (if (i + width> = n)) BottomUpMerge ( A , i , min ( i + width , n ), min ( i + 2 * ancho , n ), B ); } // Ahora la matriz de trabajo B está llena de corridas de largo 2 * ancho. // Copie la matriz B a la matriz A para la siguiente iteración. // Una implementación más eficiente intercambiaría los roles de A y B. CopyArray ( B , A , n ); // Ahora la matriz A está llena de corridas de largo 2 * ancho. } }// La carrera a la izquierda es A [iLeft: iRight-1]. // La ejecución correcta es A [iRight: iEnd-1]. anular BottomUpMerge ( A [], iLeft , iRight , iEnd , B []) { i = iLeft , j = iRight ; // Si bien hay elementos en las carreras izquierda o derecha ... for ( k = iLeft ; k < iEnd ; k ++ ) { // Si existe la cabeza de carrera izquierda y es <= la cabeza de carrera derecha existente. if ( i < iRight && ( j > = iEnd || A [ i ] <= A [ j ])) { B [ k ] = A [ i ]; i = i + 1 ; } más { B [ k ] = A [ j ]; j = j + 1 ; } } } CopyArray vacío ( 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 fusión de arriba hacia abajo que divide de forma recursiva la lista de entrada en sublistas más pequeñas hasta que las sublistas se ordenan trivialmente, y luego fusiona las sublistas mientras regresa hacia arriba en la cadena de llamadas.
function merge_sort ( list m) es // Caso base. Una lista de cero o un elemento se ordena, por definición. si la longitud de m ≤ 1 entonces devuelve m // Caso recursivo. Primero, divida la lista en sublistas de igual tamaño // que constan de la primera mitad y la segunda mitad de la lista. // Esto supone que las listas comienzan en el índice 0. var left: = lista vacía var right: = lista vacía para cada x con índice i en m do if i <(longitud de m) / 2 entonces agregar x a la izquierda demás agregar x a la derecha // Ordena recursivamente ambas sublistas. left: = merge_sort (izquierda) right: = merge_sort (derecha) // Luego fusiona las sublistas ahora ordenadas. volver fusionar (izquierda, derecha)
En este ejemplo, el La función fusionar fusiona las sublistas izquierda y derecha.
función de combinación (izquierda, derecha) es var resultado: = lista vacía mientras que la izquierda no está vacía y la derecha no está vacía hacer si primero (izquierda) ≤ primero (derecha) luego añadir primero (izquierda) al resultado izquierda: = descanso (izquierda) demás añadir primero (derecha) al resultado derecha: = descanso (derecha) // Tanto la izquierda como la derecha pueden tener elementos left; consumirlos. // (Solo se ingresará uno de los siguientes bucles.) Mientras que la izquierda no está vacía . añadir primero (izquierda) al resultado izquierda: = descanso (izquierda) mientras que la derecha no está vacía, hazlo añadir primero (derecha) al resultado derecha: = descanso (derecha) devolver resultado
Implementación de abajo hacia arriba usando listas
Pseudocódigo para el algoritmo de clasificación de fusión ascendente que utiliza una matriz pequeña de tamaño fijo de referencias a nodos, donde matriz [i] es una referencia a una lista de tamaño 2 i o nil . 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 node para sus parámetros de entrada y valor de retorno.
la función merge_sort ( cabeza de nodo ) es // devuelve si la lista está vacía si = cabeza nulas luego volver nil var nodo array [32]; inicialmente todo nil var nodo resultado var nodo siguiente var int i resultado: = cabeza // fusiona los nodos en una matriz mientras consecuencia ≠ NIL hacer siguiente: = resultado.siguiente; resultado siguiente: = nulo para (i = 0; (i <32) && (matriz [i] ≠ nil); i + = 1) hacer resultado: = fusionar (matriz [i], resultado) matriz [i]: = nulo // no pasa del final de la matriz si i = 32 entonces yo - = 1 matriz [i]: = resultado resultado: = siguiente // fusionar matriz en una sola lista resultado: = nulo para (i = 0; i <32; i + = 1) hacer resultado: = fusionar (matriz [i], resultado) devolver resultado
Orden de fusión natural
Una clasificación de combinación natural es similar a una clasificación de combinación de abajo hacia arriba, excepto que se explotan las ejecuciones naturales (secuencias ordenadas) en la entrada. Se pueden explotar ejecuciones tanto monótonas como bitónicas (alternando arriba / abajo), siendo las listas (o, de manera equivalente, cintas o archivos) estructuras de datos convenientes (utilizadas como colas FIFO o pilas LIFO ). [4] En la clasificació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 ordenan. En el caso típico, es posible que la clasificación de combinación natural no necesite tantas pasadas porque hay menos ejecuciones para combinar. En el mejor de los casos, la entrada ya está ordenada (es decir, es una ejecución), por lo que la clasificación de combinación natural solo necesita hacer una pasada a través de los datos. En muchos casos prácticos, existen largas corridas naturales y, por esa razón, el tipo de fusión natural se explota como el componente clave de Timsort . Ejemplo:
Inicio: 3 4 2 1 7 5 8 9 0 6Seleccionar carreras: (3 4) (2) (1 7) (5 8 9) (0 6)Combinar: (2 3 4) (1 5 7 8 9) (0 6)Fusionar: (1 2 3 4 5 7 8 9) (0 6)Fusionar: (0 1 2 3 4 5 6 7 8 9)
Formalmente, la combinación natural de una especie se dice que ejecuta -optimal, donde es el número de carreras en , menos uno.
Las clasificaciones de selección de reemplazo de torneo se utilizan para recopilar las ejecuciones iniciales para algoritmos de clasificación externos.
Análisis
Al ordenar n objetos, la ordenación por fusió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 ) = 2 T ( n / 2) + n se sigue 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 dados para fusionar las dos listas resultantes). [5] La forma cerrada se deriva del teorema maestro para las recurrencias de divide y vencerás .
El número de comparaciones realizadas por clasificación de combinación en el peor de los casos viene dado por los números de clasificació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 ) ). [6] El mejor caso de Merge sort requiere aproximadamente la mitad de iteraciones que su peor caso. [7]
Para n grandes y una lista de entrada ordenada aleatoriamente, fusionar el número esperado (promedio) de comparaciones de la ordenación α · n menos que en el peor de los casos, donde
En el peor de los casos, la ordenación por fusión usa aproximadamente un 39% menos de comparaciones que la ordenación rápida en su caso promedio , y en términos de movimientos, la complejidad del peor caso de la ordenación por combinación es O ( n log n ), la misma complejidad que el mejor caso de ordenación rápida. [7]
La ordenación por combinación es más eficiente que la ordenación rápida para algunos tipos de listas si los datos que se van a ordenar solo se pueden acceder de manera secuencial y, por lo tanto, es popular en lenguajes como Lisp , donde las estructuras de datos de acceso secuencial 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 Merge sort no ordena en su lugar; [8] por lo tanto, el tamaño de la memoria de la entrada debe asignarse para que se almacene la salida ordenada (ver más abajo las variaciones que necesitan solo n / 2 espacios adicionales).
Variantes
Las variantes del tipo de combinación se preocupan principalmente por reducir la complejidad del espacio y el costo de la copia.
Una alternativa simple para reducir la sobrecarga de espacio a n / 2 es mantener la izquierda y la derecha como una estructura combinada, copiar solo la parte izquierda de m en el espacio temporal y dirigir la rutina de combinación para colocar la salida combinada en m . Con esta versión, es mejor asignar el espacio temporal fuera de la rutina de combinación , de modo que solo se necesite una asignación. La copia excesiva mencionada anteriormente también se mitiga, ya que el último par de líneas antes de la declaración de resultado devuelto ( fusión de funciones en el pseudocódigo anterior) se vuelve superflua.
Un inconveniente de la ordenación por fusión, cuando se implementa en matrices, es su requisito de memoria de trabajo O ( n ) . Se han sugerido varias variantes in situ :
- Katajainen y col. Presentar un algoritmo que requiere una cantidad constante de memoria de trabajo: suficiente espacio de almacenamiento para contener un elemento de la matriz de entrada y espacio adicional para contener O (1) punteros en la matriz de entrada. Alcanzan un límite de tiempo O ( n log n ) con pequeñas constantes, pero su algoritmo no es estable. [9]
- Se han realizado varios intentos para producir un algoritmo de combinación en el lugar que se puede combinar con una clasificación de combinación estándar (de arriba hacia abajo o de abajo hacia arriba) para producir una clasificación de combinación en el lugar. En este caso, la noción de "en el lugar" se puede relajar para que signifique "tomar espacio de pila logarítmico", porque la clasificación de combinación estándar requiere esa cantidad de espacio para su propio uso de pila. Fue demostrado por Geffert et al. que en el lugar, la fusión estable que es posible en O ( n log n ) tiempo utilizando una cantidad constante de espacio cero, pero su algoritmo es complicada y tiene altos factores constantes: la fusión de matrices de longitud n y m puede tomar 5 n + 12 m + o ( m ) se mueve. [10] Este factor de alta constante y el complicado algoritmo in situ se simplificaron y facilitaron la comprensión. Bing-Chao Huang y Michael A. Langston [11] presentaron un sencillo algoritmo de tiempo lineal práctico en el lugar de fusión para fusionar una lista ordenada utilizando una 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 toma un poco más de tiempo promedio que los algoritmos estándar de ordenación por fusión, libres de explotar O (n) celdas de memoria extra temporales, en menos de un factor de dos. Aunque el algoritmo es mucho más rápido en la práctica, también es inestable para algunas listas. Pero utilizando conceptos similares, han podido resolver este problema. Otros algoritmos in situ incluyen SymMerge, que toma O (( n + m ) log ( n + m )) tiempo en total y es estable. [12] Conectar un algoritmo de este tipo en la ordenación por fusión aumenta su complejidad a la no linealidad , pero aún cuasilineal , O ( n (log n ) 2 ) .
- Una combinación moderna y estable lineal e in situ es la clasificación por combinación de bloques .
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 denomina registro). Luego, la fusión de las listas ordenadas procede cambiando los valores del enlace; no es necesario mover ningún registro. Un campo que contiene solo un enlace generalmente será más pequeño que un registro completo, por lo que también se usará menos espacio. Esta es una técnica de clasificación estándar, no restringida a la clasificación por combinación.
Usar con unidades de cinta
Es práctico ejecutar una clasificación de combinación externa utilizando unidades de disco o cinta cuando los datos que se van a clasificar 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. Un tipo de unidad de cinta típico utiliza cuatro unidades de cinta. Todas las E / S son secuenciales (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 matrices en la memoria. El algoritmo básico se puede describir de la siguiente manera:
- Fusionar pares de registros de A; escribir sublistas de dos registros alternativamente en C y D.
- Fusionar sublistas de dos registros de C y D en sublistas de cuatro registros; escribiéndolas alternativamente en A y B.
- Fusionar sublistas de cuatro registros de A y B en sublistas de ocho registros; escribiendo estos alternativamente en C y D
- Repita hasta que tenga una lista que contenga todos los datos, ordenados, en log 2 ( n ) pasadas.
En lugar de comenzar con ejecuciones muy cortas, generalmente se usa un algoritmo híbrido , donde la pasada inicial leerá muchos registros en la memoria, hará una clasificació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, un tipo interno de 1024 registros guardará nueve pases. El tipo interno 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 min-montón binario ), genera ejecuciones dos veces más largas (en promedio) que el tamaño de la memoria utilizada. [13]
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 , o 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 .
Un tipo de combinación más sofisticado que optimiza el uso de la unidad de cinta (y disco) es el tipo de combinación polifásica .
Optimización de la ordenación por combinación
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 memoria caché del algoritmo de clasificación por fusió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, elEl algoritmo de ordenación de combinación en mosaico detiene la partición de subarreglos cuando se alcanzan los subarreglos de tamaño S, donde S es el número de elementos de datos que encajan en la memoria caché de una CPU. Cada uno de estos subarreglos se ordena con un algoritmo de ordenación en el lugar, como elordenamiento por inserción, para desalentar los intercambios de memoria, y el ordenamiento de fusión normal se completa luego de la forma recursiva estándar. Este algoritmo ha demostrado un mejor rendimiento[se necesita un ejemplo ]en máquinas que se benefician de la optimización de la caché. (LaMarca y Ladner 1997)
Kronrod (1969) sugirió una versión alternativa del tipo de combinación que usa espacio adicional constante. Este algoritmo se perfeccionó posteriormente. ( Katajainen, Pasanen y Teuhola 1996 )
Además, muchas aplicaciones de clasificación externa utilizan una forma de clasificación por fusión en la que la entrada se divide en un número mayor de sublistas, idealmente en un número para el que fusionarlas todavía hace que el conjunto de páginas procesadas actualmente quepa en la memoria principal.
Orden de fusión en paralelo
La ordenación combinada se paraleliza bien debido al uso del método divide y vencerás . Se han desarrollado varias variantes paralelas diferentes del algoritmo a lo largo de los años. Algunos algoritmos de clasificación de fusión en paralelo están estrechamente relacionados con el algoritmo de fusión secuencial de arriba hacia abajo, mientras que otros tienen una estructura general diferente y utilizan el método de fusión de K-way .
Combinar ordenación con recursividad paralela
El procedimiento de clasificación de combinación secuencial se puede describir en dos fases, la fase de división y la fase de combinación. La primera consiste en muchas llamadas recursivas que realizan repetidamente el mismo proceso de división hasta que las subsecuencias se ordenan trivialmente (que contienen uno o ningún elemento). Un enfoque intuitivo es la paralelización de esas llamadas recursivas. [14] El siguiente pseudocódigo describe el tipo de combinación con recursividad paralela usando las palabras clave fork y join :
// Ordenar elementos desde lo alto hasta hi (exclusivo) de la matriz A. El algoritmo mergesort (A, lo, hi) es si lo + 1entonces // Dos o más elementos. medio: = ⌊ (lo + hi) / 2⌋ fork mergesort (A, lo, mid) mergesort (A, mid, hola) entrar fusionar (A, lo, mid, hola)
Este algoritmo es la modificación trivial de la versión secuencial y no se paraleliza bien. Por tanto, su aceleración no es muy impresionante. Tiene un lapso de, que es solo una mejora de en comparación con la versión secuencial (consulte 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.
Fusionar ordenación con fusión paralela
Se puede lograr un mejor paralelismo mediante el uso de un algoritmo de fusión en paralelo . Cormen y col. presentan una variante binaria que fusiona dos subsecuencias ordenadas en una secuencia de salida ordenada. [14]
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 fusió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 fusión en paralelo modificado utilizando el algoritmo de fusión en paralelo (adoptado de Cormen et al.).
/ ** * A: matriz de entrada * B: matriz de salida * lo: límite inferior * hola: límite superior * desactivado: desplazamiento * /algoritmo paraleloMergesort (A, lo, hi, B, off) es len: = hola - lo + 1 si len == 1 entonces B [apagado]: = A [lo] de lo contrario, deje que T [1..len] sea una nueva matriz medio: = ⌊ (lo + hi) / 2⌋ mid ': = mid - lo + 1 horquilla paralelaMergesort (A, lo, mid, T, 1) paraleloMergesort (A, mid + 1, hi, T, mid '+ 1) entrar En paraleloMerge (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 paralelMergesort deben incorporarse solo una vez debido a su ejecución en paralelo, obteniendo
Para obtener información detallada sobre la complejidad del procedimiento de fusión en paralelo, consulte el algoritmo de fusión .
La solución de esta recurrencia está dada por
Este algoritmo de fusión en paralelo alcanza un paralelismo de , que es mucho más alto que el paralelismo del algoritmo anterior. Tal clasificación puede funcionar bien en la práctica cuando se combina con una clasificación secuencial estable rápida, como la clasificación por inserción , y una combinación secuencial rápida como caso base para fusionar arreglos pequeños. [15]
Ordenación de combinación de múltiples vías paralela
Parece arbitrario restringir los algoritmos de clasificación de combinación a un método de combinación binario, ya que generalmente hay p> 2 procesadores disponibles. Un mejor enfoque puede ser utilizar un método de fusión de K-way , una generalización de fusión binaria, en la quelas secuencias ordenadas se fusionan. Esta variante de combinación es adecuada para describir un algoritmo de clasificación en un PRAM . [16] [17]
Idea básica
Dada una secuencia desordenada de elementos, el objetivo es ordenar la secuencia con procesadores disponibles . Estos elementos se distribuyen por igual entre todos los procesadores y se clasifican localmente mediante un algoritmo de clasificación secuencial . Por tanto, la secuencia consta de secuencias ordenadas de longitud . Para simplificar, deje ser un múltiplo de , así que eso por .
Estas secuencias se utilizarán para realizar una selección de secuencia múltiple / selección de divisor. Para, el algoritmo determina los elementos divisores con rango global . Entonces las posiciones correspondientes de en cada secuencia se determinan con búsqueda binaria y, por lo tanto, el se dividen aún más en subsecuencias con .
Además, los elementos de están asignados al procesador , significa todos los elementos entre rango y rango , que se distribuyen por todos . Por tanto, cada procesador recibe una secuencia de secuencias ordenadas. El hecho de que el rango de los elementos divisores fue elegido globalmente, ofrece dos propiedades importantes: Por un lado, se eligió para que cada procesador pueda seguir funcionando en elementos después de la asignación. El algoritmo tiene una carga perfectamente equilibrada . Por otro lado, todos los elementos del procesador son menores o iguales que todos los elementos del procesador . Por tanto, cada procesador realiza la combinación de vías p localmente y, por tanto, obtiene una secuencia ordenada a partir de sus subsecuencias. Debido a la segunda propiedad, no es necesario realizar más combinaciones de p -way-merge, los resultados solo deben agruparse en el orden del número de procesador.
Selección de secuencia múltiple
En su forma más simple, dada secuencias ordenadas distribuido uniformemente en procesadores y un rango , la tarea es encontrar un elemento con un rango global en la unión de las secuencias. Por lo tanto, esto se puede utilizar para dividir cada en dos partes en un índice divisor , donde la parte inferior contiene solo elementos que son más pequeños que , mientras que los elementos más grandes que se encuentran en la parte superior.
El algoritmo secuencial presentado devuelve los índices de las divisiones en cada secuencia, por ejemplo, los índices en secuencias tal que tiene un rango global menor que y . [18]
algoritmo msSelect (S: Array of sorted Sequences [S_1, .., S_p], k: int) es para i = 1 to p do (l_i, r_i) = (0, | S_i | -1) mientras exista i: l_ido// elige Pivot Element en S_j [l_j], .., S_j [r_j], elige aleatorio j uniformementev: = pickPivot (S, l, r)para i = 1 a p do m_i = binarySearch (v, S_i [l_i, r_i]) // secuencialmentesi m_1 + ... + m_p> = k entonces // m_1 + ... + m_p es el rango global de v r: = m // asignación de vectordemás l: = m volver l
Para el análisis de complejidad se elige el modelo PRAM . Si los datos se distribuyen uniformemente en todos, la ejecución p-fold del método binarySearch tiene un tiempo de ejecución de. La profundidad de recursividad esperada escomo en el Quickselect ordinario . Por lo tanto, el tiempo de ejecución total esperado es.
Aplicado en la clasificación de combinación de múltiples vías paralelas, este algoritmo debe invocarse en paralelo de manera que todos los elementos divisores de rango por se encuentran simultáneamente. Estos elementos divisores se pueden utilizar para dividir cada secuencia en partes, con el mismo tiempo de ejecución total de .
Pseudocódigo
A continuación, se proporciona el pseudocódigo completo del algoritmo de clasificación de fusión de múltiples vías en paralelo. Suponemos que hay una sincronización de barrera antes y después de la selección de secuencia múltiple, de modo que cada procesador puede determinar los elementos de división y la partición de secuencia correctamente.
/ ** * d: Matriz de elementos sin clasificar * n: Número de elementos * p: Número de procesadores * devolver Matriz ordenada * /algoritmo parallelMultiwayMergesort (d: Array, n: int, p: int) es o: = nuevo Array [0, n] // la matriz 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 / psort (S_i) // ordenar localmente sincronizarv_i: = msSelect ([S_1, ..., S_p], i * n / p) // elemento con rango global i * n / p sincronizar(S_i, 1, ..., S_i, p): = secuencia_particionamiento (si, v_1, ..., v_p) // dividir s_i en subsecuencias o [(i-1) * n / p, i * n / p]: = kWayMerge (s_1, i, ..., s_p, i) // fusionar y asignar a la matriz de salida volver o
Análisis
En primer lugar, cada procesador clasifica los elementos localmente usando un algoritmo de clasificación con complejidad . Después de eso, los elementos divisores deben calcularse a tiempo. Finalmente, cada grupo de Las divisiones deben fusionarse en paralelo por cada procesador con un tiempo de ejecución de utilizando un algoritmo de combinación secuencial de p-way . Por lo tanto, el tiempo de ejecución total viene dado por
.
Adaptación y aplicación prácticas
El algoritmo de clasificación de combinación de múltiples vías es muy escalable gracias a su alta capacidad de paralelización, que permite el uso de muchos procesadores. Esto hace que el algoritmo sea un candidato viable para clasificar grandes cantidades de datos, como los procesados en grupos de computadoras . Además, dado que en tales sistemas la memoria no suele ser un recurso limitante, la desventaja de la complejidad del espacio del tipo de combinación es insignificante. Sin embargo, otros factores se vuelven importantes en dichos sistemas, que no se tienen en cuenta al modelar en un PRAM . Aquí, se deben considerar los siguientes aspectos: la jerarquía de la memoria , cuando los datos no encajan en la caché del procesador, 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 del memoria.
Sanders y col. han presentado en su artículo un algoritmo paralelo síncrono masivo para el agrupamiento de combinaciones multinivel y de múltiples vías, que divide procesadores en grupos de tamaño . Todos los procesadores se clasifican primero localmente. A diferencia del mergesort de múltiples vías de un solo nivel, estas secuencias se dividen enpartes y asignados a los grupos de procesadores apropiados. Estos pasos se repiten de forma recursiva en esos grupos. Esto reduce la comunicación y especialmente evita 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 , clústeres , ...). [17]
Más variantes
La clasificación por combinación fue uno de los primeros algoritmos de clasificación en los que se logró una velocidad óptima, con Richard Cole utilizando un algoritmo de submuestreo inteligente para garantizar la combinación O (1). [19] Otros algoritmos sofisticados de ordenació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 de base relacionada ) que puede operar en tiempo O (log n ) en una máquina CRCW de acceso aleatorio paralelo (PRAM) con n procesadores realizando particiones implícitamente. [20] Powers muestra además que una versión pipeline de la Dosificadores bitónica por fusión en O ((log n ) 2 ) el tiempo en una mariposa de clasificación de la red es en la práctica realmente más rápido que su O (log n ) tipo en un cochecito de niño, y proporciona información detallada discusión de los gastos generales ocultos en comparación, ordenación en base y en paralelo. [21]
Comparación con otros algoritmos de ordenación
Aunque heapsort tiene los mismos límites de tiempo que la ordenación por combinación, solo requiere espacio auxiliar Θ (1) en lugar de Θ ( n ) de la ordenación por combinación . En las arquitecturas modernas típicas, las implementaciones eficientes de ordenación rápida generalmente superan a la ordenación por fusión para ordenar matrices basadas en RAM. [ cita requerida ] Por otro lado, la clasificación por fusión es una clasificación estable y es más eficiente en el manejo de medios secuenciales de acceso lento. La ordenación por combinación es a menudo 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 requiere Θ (1) espacio adicional y el rendimiento lento de acceso aleatorio de una lista vinculada. list hace que algunos otros algoritmos (como quicksort) funcionen mal y otros (como heapsort) completamente imposibles.
A partir de Perl 5.8, la ordenación por combinación es su algoritmo de ordenación predeterminado (era una ordenación rápida en versiones anteriores de Perl). [22] En Java , los métodos Arrays.sort () utilizan una ordenación por fusión o una ordenación rápida ajustada según los tipos de datos y, para la eficiencia de la implementación, cambian a la ordenación por inserción cuando se ordenan menos de siete elementos de la matriz. [23] El kernel de Linux utiliza la clasificación por combinación para sus listas enlazadas. [24] Python usa Timsort , otro híbrido afinado de ordenación por fusión y ordenación por inserción, que se ha convertido en el algoritmo de ordenación estándar en Java SE 7 (para matrices de tipos no primitivos), [25] en la plataforma Android , [26] y en GNU Octave . [27]
Notas
- ↑ Skiena (2008 , p. 122)
- ^ Knuth (1998 , p. 158)
- ^ Katajainen, Jyrki; Träff, Jesper Larsson (marzo de 1997). "Un análisis meticuloso de los programas mergesort" (PDF) . Actas de la 3ª Conferencia Italiana sobre Algoritmos y Complejidad . Conferencia italiana sobre algoritmos y complejidad. Roma. págs. 217–228. CiteSeerX 10.1.1.86.3154 . doi : 10.1007 / 3-540-62592-5_74 .
- ^ Powers, David MW; McMahon, Graham B. (1983). "Un compendio de interesantes programas de prolog". Informe técnico DCS 8313 (Informe). Departamento de Ciencias de la Computación, Universidad de Nueva Gales del Sur.
- ^ Cormen y col. (2009 , pág.36)
- ^ El número del peor de los casos que se da aquí no concuerda con el que se da enEl arte de la programación informática de Knuth , Vol 3 . La discrepancia se debe a que Knuth analiza una implementación variante del tipo de combinación que es ligeramente subóptima
- ^ a b Jayalakshmi, N. (2007). Estructura de datos usando C ++ . ISBN 978-81-318-0020-1. OCLC 849900742 .
- ^ Cormen y col. (2009 , pág.151)
- ^ Katajainen, Pasanen y Teuhola (1996)
- ^ Geffert, Viliam; Katajainen, Jyrki; Pasanen, Tomi (2000). "Fusión in situ asintóticamente eficiente". Informática Teórica . 237 (1–2): 159–181. doi : 10.1016 / S0304-3975 (98) 00162-5 .
- ^ Huang, Bing-Chao; Langston, Michael A. (marzo de 1988). "Fusión práctica en el lugar". Comunicaciones de la ACM . 31 (3): 348–352. doi : 10.1145 / 42392.42403 . S2CID 4841909 .
- ^ 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.
- ^ Ferragina, Paolo (2009-2019), "5. Clasificación de elementos atómicos" (PDF) , ¡ La magia de los algoritmos! , pag. 5-4, archivado (PDF) desde el original el 2021-05-12
- ^ a b Cormen y col. (2009 , págs. 797–805)
- ^ Victor J. Duvanenko "Orden de fusión en paralelo" Diario y blog del Dr. Dobb [1] e implementación de C ++ en el repositorio de GitHub [2]
- ^ Peter Sanders; Johannes Singler (2008). "Lectura de algoritmos paralelos " (PDF) . Consultado el 2 de mayo de 2020 .
- ^ a b Axtmann, Michael; Bingmann, Timo; Sanders, Peter; Schulz, Christian (2015). "Práctica clasificación masiva paralela" . Actas del 27º Simposio de ACM sobre paralelismo en algoritmos y arquitecturas : 13-23. doi : 10.1145 / 2755573.2755595 . ISBN 9781450335881. S2CID 18249978 .
- ^ Peter Sanders (2019). "Lectura de algoritmos paralelos " (PDF) . Consultado el 2 de mayo de 2020 .
- ^ Cole, Richard (agosto de 1988). "Orden de fusión en paralelo". SIAM J. Comput . 17 (4): 770–785. CiteSeerX 10.1.1.464.7118 . doi : 10.1137 / 0217049 . S2CID 2416667 .
- ^ Powers, David MW (1991). "Quicksort paralelo y Radixsort con Optimal Speedup" . Actas de la Conferencia Internacional sobre Tecnologías de Computación Paralela, Novosibirsk . Archivado desde el original el 25 de mayo de 2007.
- ^ Powers, David MW (enero de 1995). Unificación paralela: complejidad práctica (PDF) . Taller de Arquitectura de Computadoras de Australasia de la Universidad Flinders.
- ^ "Ordenar - Documentación de la versión 8.8 de Perl 5" . Consultado el 23 de agosto de 2020 .
- ^ coleenp (22 de febrero de 2019). "src / java.base / share / classes / java / util / Arrays.java @ 53904: 9c3fe09f69bc" . OpenJDK .
- ^ núcleo de Linux /lib/list_sort.c
- ^ jjb (29 de julio de 2009). "Confirmar 6804124: Reemplazar" mergesort modificado "en java.util.Arrays.sort con timsort" . Repositorio de 7 Hg de Java Development Kit . Archivado desde el original el 26 de enero de 2018 . Consultado el 24 de febrero de 2011 .
- ^ "Clase: java.util.TimSort " . Documentación de Android JDK . Archivado desde el original el 20 de enero de 2015 . Consultado el 19 de enero de 2015 .
- ^ "liboctave / util / oct-sort.cc" . Repositorio Mercurial del código fuente de Octave . Líneas 23-25 del bloque de comentarios inicial . Consultado el 18 de febrero de 2013 .
Código robado en gran parte de listobject.c de Python, que en sí mismo no tenía encabezado de licencia. Sin embargo, gracias a Tim Peters por las partes del código que estafé.
Referencias
- 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.
- Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). "Mergesort práctico en el lugar" . Revista Nórdica de Computación . 3 (1): 27–40. CiteSeerX 10.1.1.22.8523 . ISSN 1236-6064 . Archivado desde el original el 7 de agosto de 2011 . Consultado el 4 de abril de 2009 .. También es práctico Mergesort in situ . También [3]
- Knuth, Donald (1998). "Sección 5.2.4: Clasificación por fusión". Clasificación y búsqueda . El arte de la programación informática . 3 (2ª ed.). Addison-Wesley. págs. 158-168. ISBN 0-201-89685-0.
- Kronrod, MA (1969). "Algoritmo de pedido óptimo sin campo operativo". Matemáticas soviéticas - Doklady . 10 : 744.
- LaMarca, A .; Ladner, RE (1997). "La influencia de los cachés en el rendimiento de la clasificación". Proc. 8th Ann. ACM-SIAM Symp. Sobre algoritmos discretos (SODA97) : 370–379. CiteSeerX 10.1.1.31.1153 .
- Skiena, Steven S. (2008). "4.5: Mergesort: ordenar por divide y vencerás". El Manual de diseño de algoritmos (2ª ed.). Saltador. págs. 120-125. ISBN 978-1-84800-069-8.
- Sun Microsystems. "Arrays API (Java SE 6)" . Consultado el 19 de noviembre de 2007 .
- Oracle Corp. "Arrays (Java SE 10 y JDK 10)" . Consultado el 23 de julio de 2018 .
enlaces externos
- Algoritmos de clasificación animados: clasificación combinada en la Wayback Machine (archivado el 6 de marzo de 2015) - demostración gráfica
- Estructuras de datos abiertas - Sección 11.1.1 - Combinar ordenación , Pat Morin