Combinar ordenación

Un algoritmo de clasificación para dividir y combinar

Este artículo posiblemente contenga una investigación original . Por favor, mejorarlo mediante la verificación de las afirmaciones hechas y la adición de citas en línea . Deben eliminarse las declaraciones que solo contengan investigaciones originales. ( Mayo de 2016 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla )

Combinar ordenación

Un ejemplo de ordenación por combinación. Primero divida la lista en la unidad más pequeña (1 elemento), luego compare cada elemento con la lista adyacente para ordenar y fusionar las dos listas adyacentes. Finalmente, todos los elementos se ordenan y combinan.
Clase	Algoritmo de clasificación
Estructura de datos	Formación
Rendimiento en el peor de los casos	${\displaystyle O(n\log n)}$
Rendimiento en el mejor de los casos	${\displaystyle \Omega (n\log n)}$variante típica, natural${\displaystyle \Omega (n)}$
Rendimiento medio	${\displaystyle \Theta (n\log n)}$
Complejidad espacial en el peor de los casos	${\displaystyle O(n)}$total con auxiliares, auxiliares con listas enlazadas [1]${\displaystyle O(n)}$${\displaystyle O(1)}$

En ciencias de la computación , la ordenación por combinación (también deletreada comúnmente mergesort ) es un algoritmo de ordenación eficiente, de uso general y basado en 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 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]

Algoritmo

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

1. Divida la lista sin clasificar en n sublistas, cada una de las cuales contiene un elemento (una lista de un elemento se considera ordenada).
2. 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 de 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 ];  yo  =  yo  +  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.  para  ( i  =  0 ;  i  <  n;  i  =  i  +  2  *  width )  {  // Fusionar dos ejecuciones: A [i: i + width-1] y A [i + width: i + 2 * width-1] en B []  // o copiar A [ i: n-1] a B [] (si (i + ancho> = n))  BottomUpMerge ( A ,  i ,  min ( i + ancho ,  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.  si  ( yo  < 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, la función de combinación 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 ⁱ 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)

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

Análisis

Un algoritmo de clasificación de combinación recursiva que se utiliza para clasificar una matriz de 7 valores enteros. Estos son los pasos que tomaría un humano para emular la ordenación por fusión (de arriba hacia abajo).

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). La forma cerrada se sigue de lateorema 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 ) ). ^[5] El mejor caso de Merge sort requiere aproximadamente la mitad de iteraciones que el peor de los casos. ^{[ cita requerida ]}

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${\displaystyle \alpha =-1+\sum _{k=0}^{\infty }{\frac {1}{2^{k}+1}}\approx 0.2645.}$

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. ^{[ cita requerida ]}

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; ^[6] por lo tanto, el tamaño de 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. ^[7]
• 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 + 12m + o ( m ) se mueve. ^[8] Este alto factor constante y el complicado algoritmo in situ se simplificaron y facilitaron la comprensión. Bing-Chao Huang y Michael A. Langston ^[9] presentaron un algoritmo de tiempo lineal sencillo de fusión práctica en el lugarpara 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. ^[10]Conectar un algoritmo de este tipo en una ordenación por fusión aumenta su complejidad al no linealítmico , pero aún cuasilineal , O ( n (log n ) ² ) .
• 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

Los algoritmos de tipo de clasificación por fusión permitieron clasificar grandes conjuntos de datos en las primeras computadoras que tenían pequeñas memorias de acceso aleatorio según los estándares modernos. Los registros se almacenaron en cinta magnética y se procesaron en bancos de unidades de cinta magnética, como estos IBM 729 .

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:

1. Fusionar pares de registros de A; escribir sublistas de dos registros alternativamente en C y D.
2. Fusionar sublistas de dos registros de C y D en sublistas de cuatro registros; escribiéndolas alternativamente en A y B.
3. Fusionar sublistas de cuatro registros de A y B en sublistas de ocho registros; escribiendo estos alternativamente en C y D
4. Repita hasta que tenga una lista que contenga todos los datos, ordenados, en log ₂ ( 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. ^[11]

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 combinada

Clasificación de combinación en mosaico aplicada a una matriz de números enteros aleatorios. El eje horizontal es el índice de la matriz y el eje vertical es el número 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 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, el algoritmo de ordenación por fusión en mosaico 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 encajan en la memoria caché de una CPU. Cada uno de estos subarreglos se ordena con un algoritmo de ordenación in situ, como el ordenamiento por inserción, para desalentar los intercambios de memoria y, a continuación, se completa la clasificación de fusión normal 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. ^{[12] El} siguiente pseudocódigo describe la ordenación por fusió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 + 1 <hi entonces // Dos o más elementos. medio: = ⌊ (lo + hi) / 2⌋ fork mergesort (A, lo, mid) mergesort (A, mid, hola) unirse 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 intervalo de , que es solo una mejora en comparación 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.${\displaystyle \Theta (n)}$${\displaystyle \Theta (\log n)}$

Combinar ordenación con combinación paralela

Artículo principal: algoritmo de fusión § fusión en paralelo

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. ^[12]

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)  unirse  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

$${\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 el algoritmo de fusión .

La solución de esta recurrencia está dada por

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

Este algoritmo de fusión en paralelo alcanza un paralelismo de , que es mucho mayor 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. ^[13]${\textstyle \Theta \left({\frac {n}{(\log n)^{2}}}\right)}$

Orden 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 que las secuencias ordenadas se fusionan. Esta variante de combinación es adecuada para describir un algoritmo de clasificación en un PRAM . ^{[14] [15]}${\displaystyle k}$

Idea básica

El proceso de fusión múltiple paralelo en cuatro procesadores para .${\displaystyle t_{0}}$${\displaystyle t_{3}}$

Dada una secuencia de elementos sin clasificar , el objetivo es ordenar la secuencia con los 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, sea ​​un múltiplo de , de modo que para .${\displaystyle n}$${\displaystyle p}$${\displaystyle S_{1},...,S_{p}}$${\textstyle \lceil {\frac {n}{p}}\rceil }$${\displaystyle n}$${\displaystyle p}$${\textstyle \left\vert S_{i}\right\vert ={\frac {n}{p}}}$${\displaystyle i=1,...,p}$

Estas secuencias se utilizarán para realizar una selección de secuencia múltiple / selección de divisor. Porque , el algoritmo determina elementos divisores con rango global . Luego, las posiciones correspondientes de en cada secuencia se determinan con búsqueda binaria y, por lo tanto, se dividen en subsecuencias con .${\displaystyle j=1,...,p}$${\displaystyle v_{j}}$${\textstyle k=j{\frac {n}{p}}}$${\displaystyle v_{1},...,v_{p}}$${\displaystyle S_{i}}$${\displaystyle S_{i}}$${\displaystyle p}$${\displaystyle S_{i,1},...,S_{i,p}}$${\textstyle S_{i,j}:=\{x\in S_{i}|rank(v_{j-1})<rank(x)\leq rank(v_{j})\}}$

Además, los elementos de están asignados al procesador , es decir, todos los elementos entre rango y rango , que se distribuyen entre todos . Por tanto, cada procesador recibe una secuencia de secuencias ordenadas. El hecho de que el rango de los elementos divisores se eligió globalmente, proporciona dos propiedades importantes: Por un lado, se eligió para que cada procesador aún pueda operar sobre los 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 lo tanto, cada procesador realiza la combinación de vías p${\displaystyle S_{1,i},...,S_{p,i}}$${\displaystyle i}$${\textstyle (i-1){\frac {n}{p}}}$${\textstyle i{\frac {n}{p}}}$${\displaystyle S_{i}}$${\displaystyle k}$${\displaystyle v_{i}}$${\displaystyle k}$${\textstyle n/p}$${\displaystyle i}$${\displaystyle i+1}$localmente y así obtiene una secuencia clasificada 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, dadas secuencias ordenadas distribuidas 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 puede usarse para dividir cada uno en dos partes en un índice de división , 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.${\displaystyle p}$${\displaystyle S_{1},...,S_{p}}$${\displaystyle p}$${\displaystyle k}$${\displaystyle x}$${\displaystyle k}$${\displaystyle S_{i}}$${\displaystyle l_{i}}$${\displaystyle x}$${\displaystyle x}$

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

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_i <r_i do// 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 entre todos , la ejecución p-fold del método binarySearch tiene un tiempo de ejecución de . La profundidad de recursividad esperada es como en la selección rápida ordinaria . Por lo tanto, el tiempo de ejecución total esperado es .${\displaystyle p}$${\displaystyle {\mathcal {O}}\left(p\log \left(n/p\right)\right)}$${\displaystyle {\mathcal {O}}\left(\log \left(\textstyle \sum _{i}|S_{i}|\right)\right)={\mathcal {O}}(\log(n))}$${\displaystyle {\mathcal {O}}\left(p\log(n/p)\log(n)\right)}$

Aplicado en la clasificación de fusión de múltiples vías en paralelo, este algoritmo debe invocarse en paralelo de manera que todos los elementos divisores de rango para se encuentren simultáneamente. Estos elementos divisores se pueden usar para dividir cada secuencia en partes, con el mismo tiempo de ejecución total de .${\textstyle i{\frac {n}{p}}}$${\displaystyle i=1,..,p}$${\displaystyle p}$${\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 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 asignados localmente utilizando un algoritmo de clasificación con complejidad . Después de eso, los elementos divisores deben calcularse a tiempo . Por último, cada grupo de divisiones debe fusionarse en paralelo por cada procesador con un tiempo de ejecución mediante el uso de un algoritmo secuencial de combinación de vías p . Por lo tanto, el tiempo de ejecución total viene dado por${\displaystyle n/p}$${\displaystyle {\mathcal {O}}\left(n/p\;\log(n/p)\right)}$${\displaystyle {\mathcal {O}}\left(p\,\log(n/p)\log(n)\right)}$${\displaystyle p}$${\displaystyle {\mathcal {O}}(\log(p)\;n/p)}$

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

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: Jerarquía de la memoria, cuando los datos no caben en la caché de los procesadores, o la sobrecarga de comunicación del intercambio de datos entre procesadores, lo que podría convertirse en un cuello de botella cuando ya no se pueda acceder a los datos a través de la memoria compartida.

Sanders y col. han presentado en su artículo un algoritmo paralelo síncrono masivo para la ordenación por combinación de múltiples niveles y múltiples vías, que divide los procesadores en grupos de tamaño . Todos los procesadores primero se ordenan localmente. A diferencia del mergesort de múltiples vías de un solo nivel, estas secuencias se dividen en partes y se asignan 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 , ...). ^[15]${\displaystyle p}$${\displaystyle r}$${\displaystyle p'}$${\displaystyle r}$

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). ^[17] Otros algoritmos sofisticados de ordenación paralela 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. ^[18] Powers muestra además que una versión canalizada de BatcherBitonic Mergesort en el tiempo O ((log n ) ² ) en una red de clasificación de mariposas es en la práctica más rápido que sus clasificaciones O (log n ) en un PRAM, y proporciona una discusión detallada de los gastos generales ocultos en comparación, ordenación por base y paralela . ^[19]

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. El ordenamiento combinado es a menudo la mejor opción para ordenar una lista vinculada: en esta situación, es relativamente fácil implementar una ordenación combinada de tal manera que solo requiera Θ (1) espacio adicional, y el rendimiento de acceso aleatorio lento de una lista vinculada hace que algunos otros algoritmos (como la ordenación rápida) funcionen mal , y otros (como heapsort) completamente imposible.

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). ^[20] 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 ordenación por inserción cuando se ordenan menos de siete elementos de la matriz. ^[21] El kernel de Linux utiliza la clasificación por fusión para sus listas enlazadas. ^[22] 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), ^[23]en la plataforma Android , ^[24] y en GNU Octave . ^[25]

Notas

1. Skiena (2008 , p. 122)
2. Knuth (1998 , p. 158)
3. 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 .
4. Poderes, David MW; McMahon, Graham B. (1983). "Un compendio de interesantes programas de prólogo". Informe técnico DCS 8313 (Informe). Departamento de Ciencias de la Computación, Universidad de Nueva Gales del Sur.
5. 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
6. Cormen y col. (2009 , pág.151) harvtxt error: no target: CITEREFCormenLeisersonRivestStein2009 (help)
7. Katajainen, Pasanen y Teuhola (1996)
8. 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 .
9. 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 . 
10. Kim, Pok-Son; Kutzner, Arne (2004). Almacenamiento mínimo estable que se fusiona mediante comparaciones simétricas . Symp europeo. Algoritmos. Apuntes de conferencias en informática. 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.
11. selección. Quitanieves de Knuth. Fusión natural.
12. Cormen y col. (2009 , págs. 797–805) harvtxt error: no target: CITEREFCormenLeisersonRivestStein2009 (help)
13. 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]
14. Peter Sanders; Johannes Singler (2008). "Lectura de algoritmos paralelos " (PDF) . Consultado el 2 de mayo de 2020 .
15. 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 .
16. Peter Sanders (2019). "Lectura de algoritmos paralelos " (PDF) . Consultado el 2 de mayo de 2020 .
17. 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 .  
18. Poderes, 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.
19. Powers, David MW (enero de 1995). Unificación paralela: complejidad práctica (PDF) . Taller de Arquitectura de Computadoras de Australasia de la Universidad Flinders.
20. "Ordenar - Documentación de la versión 8.8 de Perl 5" . Consultado el 23 de agosto de 2020 .
21. coleenp (22 de febrero de 2019). "src / java.base / share / classes / java / util / Arrays.java @ 53904: 9c3fe09f69bc" . OpenJDK .
22. núcleo de Linux /lib/list_sort.c
23. 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 .
24. "Clase: java.util.TimSort <T>" . Documentación de Android JDK . Archivado desde el original el 20 de enero de 2015 . Consultado el 19 de enero de 2015 .
25. "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

La implementación del algoritmo de Wikibook tiene una página sobre el tema: Combinar ordenación

• 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