Mesclar classificação - Merge sort

Mesclar classificação

Um exemplo de classificação por mesclagem. Primeiro divida a lista na menor unidade (1 elemento), depois compare cada elemento com a lista adjacente para classificar e mesclar as duas listas adjacentes. Finalmente, todos os elementos são classificados e mesclados.
Classe	Algoritmo de classificação
Estrutura de dados	Variedade
Desempenho de pior caso	${\ displaystyle O (n \ log n)}$
Melhor caso de desempenho	${\ displaystyle \ Omega (n \ log n)}$variante natural típica ${\ displaystyle \ Omega (n)}$
Desempenho médio	${\ displaystyle \ Theta (n \ log n)}$
Pior caso de complexidade de espaço	${\ displaystyle O (n)}$total com auxiliar, auxiliar com listas vinculadas${\ displaystyle O (n)}$${\ displaystyle O (1)}$

Na ciência da computação , merge sort (também comumente escrito como mergesort ) é um algoritmo de classificação eficiente, de propósito geral e baseado em comparação . A maioria das implementações produz uma classificação estável , o que significa que a ordem dos elementos iguais é a mesma na entrada e na saída. A classificação de mesclagem é um algoritmo de divisão e conquista inventado por John von Neumann em 1945. Uma descrição e análise detalhadas da classificação de mesclagem de baixo para cima apareceu em um relatório de Goldstine e von Neumann já em 1948.

Algoritmo

Conceitualmente, uma classificação por mesclagem funciona da seguinte maneira:

1. Divida a lista não classificada em n sublistas, cada uma contendo um elemento (uma lista de um elemento é considerada classificada).
2. Repetidamente fundir sublists para produzir novos sublists ordenadas até que haja apenas uma sublista restante. Esta será a lista classificada.

Implementação de cima para baixo

Exemplo de código semelhante a C usando índices para algoritmo de classificação de mesclagem de cima para baixo que divide recursivamente a lista (chamado de execuções neste exemplo) em sublistas até que o tamanho da sublista seja 1 e, em seguida, mescla essas sublistas para produzir uma lista classificada. O retrocesso da cópia é evitado com a alternância da direção da mesclagem com cada nível de recursão (exceto para uma cópia inicial única). Para ajudar a entender isso, considere uma matriz com dois elementos. Os elementos são copiados para B [] e, em seguida, mesclados de volta para A []. Se houver quatro elementos, quando o fundo do nível de recursão for atingido, as execuções de um único elemento de A [] serão mescladas com B [] e, em seguida, no próximo nível superior de recursão, essas execuções de dois elementos serão mescladas com A [ ] Esse padrão continua com cada nível de recursão.

// Array A[] has the items to sort; array B[] is a work array.
void TopDownMergeSort(A[], B[], n)
{
    CopyArray(A, 0, n, B);           // one time copy of A[] to B[]
    TopDownSplitMerge(B, 0, n, A);   // sort data from B[] into A[]
}

// Split A[] into 2 runs, sort both runs into B[], merge both runs from B[] to A[]
// iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set).
void TopDownSplitMerge(B[], iBegin, iEnd, A[])
{
    if (iEnd - iBegin <= 1)                     // if run size == 1
        return;                                 //   consider it sorted
    // split the run longer than 1 item into halves
    iMiddle = (iEnd + iBegin) / 2;              // iMiddle = mid point
    // recursively sort both runs from array A[] into B[]
    TopDownSplitMerge(A, iBegin,  iMiddle, B);  // sort the left  run
    TopDownSplitMerge(A, iMiddle,    iEnd, B);  // sort the right run
    // merge the resulting runs from array B[] into A[]
    TopDownMerge(B, iBegin, iMiddle, iEnd, A);
}

//  Left source half is A[ iBegin:iMiddle-1].
// Right source half is A[iMiddle:iEnd-1   ].
// Result is            B[ iBegin:iEnd-1   ].
void TopDownMerge(A[], iBegin, iMiddle, iEnd, B[])
{
    i = iBegin, j = iMiddle;
 
    // While there are elements in the left or right runs...
    for (k = iBegin; k < iEnd; k++) {
        // If left run head exists and is <= existing right run head.
        if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {
            B[k] = A[i];
            i = i + 1;
        } else {
            B[k] = A[j];
            j = j + 1;
        }
    }
}

void CopyArray(A[], iBegin, iEnd, B[])
{
    for (k = iBegin; k < iEnd; k++)
        B[k] = A[k];
}

A classificação de todo o array é realizada por TopDownMergeSort (A, B, length (A)) .

Implementação de baixo para cima

Exemplo de código semelhante ao C usando índices para algoritmo de classificação de mesclagem ascendente que trata a lista como uma matriz de n sublistas (chamadas de execuções neste exemplo) de tamanho 1 e mescla iterativamente as sublistas para frente e para trás entre dois buffers:

// array A[] has the items to sort; array B[] is a work array
void BottomUpMergeSort(A[], B[], n)
{
    // Each 1-element run in A is already "sorted".
    // Make successively longer sorted runs of length 2, 4, 8, 16... until the whole array is sorted.
    for (width = 1; width < n; width = 2 * width)
    {
        // Array A is full of runs of length width.
        for (i = 0; i < n; i = i + 2 * width)
        {
            // Merge two runs: A[i:i+width-1] and A[i+width:i+2*width-1] to B[]
            // or copy A[i:n-1] to B[] ( if (i+width >= n) )
            BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B);
        }
        // Now work array B is full of runs of length 2*width.
        // Copy array B to array A for the next iteration.
        // A more efficient implementation would swap the roles of A and B.
        CopyArray(B, A, n);
        // Now array A is full of runs of length 2*width.
    }
}

//  Left run is A[iLeft :iRight-1].
// Right run is A[iRight:iEnd-1  ].
void BottomUpMerge(A[], iLeft, iRight, iEnd, B[])
{
    i = iLeft, j = iRight;
    // While there are elements in the left or right runs...
    for (k = iLeft; k < iEnd; k++) {
        // If left run head exists and is <= existing right run head.
        if (i < iRight && (j >= iEnd || A[i] <= A[j])) {
            B[k] = A[i];
            i = i + 1;
        } else {
            B[k] = A[j];
            j = j + 1;    
        }
    } 
}

void CopyArray(B[], A[], n)
{
    for (i = 0; i < n; i++)
        A[i] = B[i];
}

Implementação de cima para baixo usando listas

Pseudocódigo para algoritmo de ordenação de mesclagem de cima para baixo que divide recursivamente a lista de entrada em sublistas menores até que as sublistas sejam classificadas trivialmente e, em seguida, mescla as sublistas enquanto retorna a cadeia de chamadas.

function merge_sort(list m) is
    // Base case. A list of zero or one elements is sorted, by definition.
    if length of m ≤ 1 then
        return m

    // Recursive case. First, divide the list into equal-sized sublists
    // consisting of the first half and second half of the list.
    // This assumes lists start at index 0.
    var left := empty list
    var right := empty list
    for each x with index i in m do
        if i < (length of m)/2 then
            add x to left
        else
            add x to right

    // Recursively sort both sublists.
    left := merge_sort(left)
    right := merge_sort(right)

    // Then merge the now-sorted sublists.
    return merge(left, right)

Neste exemplo, a função de mesclagem mescla as sublistas esquerda e direita.

function merge(left, right) is
    var result := empty list

    while left is not empty and right is not empty do
        if first(left) ≤ first(right) then
            append first(left) to result
            left := rest(left)
        else
            append first(right) to result
            right := rest(right)

    // Either left or right may have elements left; consume them.
    // (Only one of the following loops will actually be entered.)
    while left is not empty do
        append first(left) to result
        left := rest(left)
    while right is not empty do
        append first(right) to result
        right := rest(right)
    return result

Implementação ascendente usando listas

Pseudocódigo para algoritmo de ordenação de mesclagem ascendente que usa um pequeno array de tamanho fixo de referências a nós, onde array [i] é uma referência a uma lista de tamanho 2 ⁱ ou nulo . nó é uma referência ou ponteiro para um nó. A função merge () seria semelhante àquela mostrada no exemplo de listas de mesclagem de cima para baixo, ela mescla duas listas já classificadas e lida com listas vazias. Nesse caso, merge () usaria node para seus parâmetros de entrada e valor de retorno.

function merge_sort(node head) is
    // return if empty list
    if head = nil then
        return nil
    var node array[32]; initially all nil
    var node result
    var node next
    var int  i
    result := head
    // merge nodes into array
    while result ≠ nil do
        next := result.next;
        result.next := nil
        for (i = 0; (i < 32) && (array[i] ≠ nil); i += 1) do
            result := merge(array[i], result)
            array[i] := nil
        // do not go past end of array
        if i = 32 then
            i -= 1
        array[i] := result
        result := next
    // merge array into single list
    result := nil
    for (i = 0; i < 32; i += 1) do
        result := merge(array[i], result)
    return result

Tipo de mesclagem natural

Uma ordenação de mesclagem natural é semelhante a uma ordenação de mesclagem ascendente, exceto que quaisquer execuções naturais (sequências ordenadas) na entrada são exploradas. Tanto as execuções monotônicas quanto as bitônicas (alternando para cima / para baixo) podem ser exploradas, com listas (ou equivalentemente fitas ou arquivos) sendo estruturas de dados convenientes (usadas como filas FIFO ou pilhas LIFO ). Na classificação de mesclagem ascendente, o ponto de partida assume que cada execução tem um item de comprimento. Na prática, os dados de entrada aleatórios terão muitas execuções curtas que simplesmente são classificadas. No caso típico, a classificação de mesclagem natural pode não precisar de tantas passagens porque há menos execuções a serem mescladas. No melhor caso, a entrada já está classificada (ou seja, é uma execução), portanto, a classificação de mesclagem natural precisa apenas fazer uma passagem pelos dados. Em muitos casos práticos, execuções naturais longas estão presentes e, por essa razão, a classificação de mesclagem natural é explorada como o componente-chave do Timsort . Exemplo:

Start       :  3  4  2  1  7  5  8  9  0  6
Select runs : (3  4)(2)(1  7)(5  8  9)(0  6)
Merge       : (2  3  4)(1  5  7  8  9)(0  6)
Merge       : (1  2  3  4  5  7  8  9)(0  6)
Merge       : (0  1  2  3  4  5  6  7  8  9)

Formalmente, a classificação de mesclagem natural é considerada Runs -optimal, onde é o número de execuções , menos um. ${\ displaystyle {\ mathtt {Runs}} (L)}$${\ displaystyle L}$

As classificações de seleção de substituição de torneio são usadas para reunir as execuções iniciais de algoritmos de classificação externos.

Análise

Um algoritmo de classificação por mesclagem recursiva usado para classificar uma matriz de 7 valores inteiros. Estas são as etapas que um ser humano deve seguir para emular a classificação por mesclagem (de cima para baixo).

Ao classificar n objetos, a classificação por mesclagem tem um desempenho médio e de pior caso de O ( n  log  n ). Se o tempo de execução da classificação por fusão para uma lista de comprimento n for T ( n ), então a relação de recorrência T ( n ) = 2 T ( n / 2) + n segue da definição do algoritmo (aplique o algoritmo a dois listas com metade do tamanho da lista original e adicione as n etapas executadas para mesclar as duas listas resultantes). A forma fechada segue do teorema mestre para recorrências de divisão e conquista .

O número de comparações feitas por classificação por mesclagem no pior caso é dado pelos números de classificação . Esses números são iguais ou ligeiramente menores que ( n  ⌈ lg  n ⌉ - 2 ^{⌈lg  n ⌉} + 1), que está entre ( n  lg  n - n + 1) e ( n  lg  n + n + O (lg  n ) ) O melhor caso do Merge sort leva cerca de metade das iterações do pior caso.

Para n grande e uma lista de entrada ordenada aleatoriamente, o número esperado (médio) de comparações do merge sort se aproxima de α · n menos do que o pior caso, onde${\ displaystyle \ alpha = -1 + \ sum _ {k = 0} ^ {\ infty} {\ frac {1} {2 ^ {k} +1}} \ approx 0,2645.}$

No pior caso, merge sort usa aproximadamente 39% menos comparações do que quicksort em seu caso médio e, em termos de movimentos, a complexidade de pior caso de merge sort é O ( n  log  n ) - a mesma complexidade do melhor caso de quicksort.

A classificação por mesclagem é mais eficiente do que a classificação rápida para alguns tipos de listas se os dados a serem classificados só puderem ser acessados ​​sequencialmente de maneira eficiente e, portanto, é popular em linguagens como Lisp , onde estruturas de dados acessadas sequencialmente são muito comuns. Ao contrário de algumas implementações (eficientes) de quicksort, a classificação por mesclagem é uma classificação estável.

A implementação mais comum da classificação de mesclagem não classifica no local; portanto, o tamanho da memória da entrada deve ser alocado para que a saída classificada seja armazenada (veja abaixo as variações que precisam de apenas n / 2 espaços extras).

Variantes

As variantes de classificação de mesclagem estão preocupadas principalmente em reduzir a complexidade do espaço e o custo de cópia.

Uma alternativa simples para reduzir o overhead de espaço para n / 2 é manter a esquerda e a direita como uma estrutura combinada, copiar apenas a parte esquerda de m no espaço temporário e direcionar a rotina de mesclagem para colocar a saída mesclada em m . Com esta versão, é melhor alocar o espaço temporário fora da rotina de mesclagem , de forma que apenas uma alocação seja necessária. O excesso de cópia mencionado anteriormente também é mitigado, uma vez que o último par de linhas antes da declaração de resultado de retorno ( fusão de função no pseudocódigo acima) torna-se supérfluo.

Uma desvantagem da classificação por mesclagem, quando implementada em matrizes, é seu requisito de memória de trabalho O ( n ) . Várias variantes no local foram sugeridas:

• Katajainen et al. apresentam um algoritmo que requer uma quantidade constante de memória de trabalho: espaço de armazenamento suficiente para manter um elemento da matriz de entrada e espaço adicional para conter O (1) ponteiros na matriz de entrada. Eles atingem um limite de tempo O ( n log n ) com pequenas constantes, mas seu algoritmo não é estável.
• Várias tentativas foram feitas na produção de um algoritmo de mesclagem no local que pode ser combinado com uma classificação de mesclagem padrão (de cima para baixo ou de baixo para cima) para produzir uma classificação de mesclagem no local. Nesse caso, a noção de "no local" pode ser relaxada para significar "ocupando espaço de pilha logarítmica", porque a classificação de mesclagem padrão requer essa quantidade de espaço para seu próprio uso de pilha. Foi demonstrado por Geffert et al. que a fusão no local e estável é possível em tempo O ( n log n ) usando uma quantidade constante de espaço de rascunho, mas seu algoritmo é complicado e tem fatores constantes altos: a fusão de matrizes de comprimento n e m pode levar 5 n + 12 m + o ( m ) se move. Este fator de alta constante e algoritmo in-loco complicado foi simplificado e fácil de entender. Bing-Chao Huang e Michael A. Langston apresentaram um algoritmo de tempo linear direto e prático de mesclagem no local para mesclar uma lista ordenada usando uma quantidade fixa de espaço adicional. Ambos usaram o trabalho de Kronrod e outros. Ele se funde em tempo linear e espaço extra constante. O algoritmo leva um pouco mais de tempo médio do que os algoritmos de merge sort padrão, livres para explorar O (n) células de memória extras temporárias, por menos de um fator de dois. Embora o algoritmo seja muito mais rápido de uma forma prática, ele também é instável para algumas listas. Mas, usando conceitos semelhantes, eles conseguiram resolver esse problema. Outros algoritmos no local incluem SymMerge, que leva O (( n + m ) log ( n + m )) tempo total e é estável. Conectar tal algoritmo à classificação por mesclagem aumenta sua complexidade para o não linear , mas ainda quase- linear , O ( n (log n ) ² ) .
• Uma mesclagem linear e no local estável moderna é a classificação de mesclagem de bloco .

Uma alternativa para reduzir a cópia em várias listas é associar um novo campo de informação a cada chave (os elementos em m são chamados de chaves). Este campo será usado para vincular as chaves e quaisquer informações associadas em uma lista classificada (uma chave e suas informações relacionadas são chamadas de registro). Em seguida, a fusão das listas classificadas prossegue alterando os valores dos links; nenhum registro precisa ser movido. Um campo que contém apenas um link geralmente será menor do que um registro inteiro, portanto, menos espaço também será usado. Esta é uma técnica de classificação padrão, não restrita à classificação por mesclagem.

Use com unidades de fita

Os algoritmos do tipo mesclagem de classificação permitiam que grandes conjuntos de dados fossem classificados nos primeiros computadores que tinham pequenas memórias de acesso aleatório pelos padrões modernos. Os registros eram armazenados em fita magnética e processados ​​em bancos de unidades de fita magnética, como esses IBM 729s .

Uma classificação de mesclagem externa é prática para executar usando unidades de disco ou fita quando os dados a serem classificados são muito grandes para caber na memória . A classificação externa explica como a classificação por mesclagem é implementada com unidades de disco. Uma classificação típica de unidade de fita usa quatro unidades de fita. Toda E / S é sequencial (exceto para retrocessos no final de cada passagem). Uma implementação mínima pode ser realizada com apenas dois buffers de registro e algumas variáveis ​​de programa.

Nomeando as quatro unidades de fita como A, B, C, D, com os dados originais em A e usando apenas dois buffers de registro, o algoritmo é semelhante à implementação ascendente , usando pares de unidades de fita em vez de matrizes na memória. O algoritmo básico pode ser descrito da seguinte forma:

1. Mesclar pares de registros de A; escrever sublistas de dois registros alternadamente para C e D.
2. Mesclar sublistas de dois registros de C e D em sublistas de quatro registros; escrevendo-os alternadamente para A e B.
3. Mesclar sublistas de quatro registros de A e B em sublistas de oito registros; escrevendo-os alternadamente para C e D
4. Repita até que você tenha uma lista contendo todos os dados, classificados - em log ₂ ( n ) passagens.

Em vez de começar com execuções muito curtas, geralmente um algoritmo híbrido é usado, em que a passagem inicial lerá muitos registros na memória, fará uma classificação interna para criar uma execução longa e, em seguida, distribuirá essas execuções longas no conjunto de saída. A etapa evita muitos passes iniciais. Por exemplo, uma espécie interna de 1024 registros salvará nove passagens. A classificação interna costuma ser grande porque traz esse benefício. Na verdade, existem técnicas que podem tornar as execuções iniciais mais longas do que a memória interna disponível. Um deles, o 'limpa-neve' do Knuth (baseado em um min-heap binário ), gera execuções duas vezes mais longas (em média) do que o tamanho da memória usada.

Com alguma sobrecarga, o algoritmo acima pode ser modificado para usar três fitas. O tempo de execução O ( n log n ) também pode ser obtido usando duas filas , ou uma pilha e uma fila, ou três pilhas. Na outra direção, usando k > duas fitas (e O ( k ) itens na memória), podemos reduzir o número de operações de fita em O (log k ) vezes usando uma fusão k / 2 vias .

Uma classificação de mesclagem mais sofisticada que otimiza o uso da unidade de fita (e disco) é a classificação de mesclagem polifásica .

Otimizando a classificação de mesclagem

Classificação de mesclagem lado a lado aplicada a uma matriz de inteiros aleatórios. O eixo horizontal é o índice da matriz e o eixo vertical é o inteiro.

Em computadores modernos, a localidade de referência pode ser de suma importância na otimização de software , porque são utilizadas hierarquias de memória multinível . Versões com reconhecimento de cache do algoritmo de classificação de mesclagem, cujas operações foram escolhidas especificamente para minimizar o movimento de páginas para dentro e para fora do cache de memória de uma máquina, foram propostas. Por exemplo, o O algoritmo de classificação de mesclagem lado a lado interrompe o particionamento de submatrizes quando submatrizes de tamanho S são atingidos, onde S é o número de itens de dados que cabem no cache de uma CPU. Cada um desses subarrays é classificado com um algoritmo de classificação no local, comoclassificação por inserção, para desencorajar as trocas de memória, e a classificação de mesclagem normal é então concluída no modo recursivo padrão. Este algoritmo demonstrou melhor desempenho em máquinas que se beneficiam da otimização do cache. (LaMarca & Ladner 1997)

Kronrod (1969) sugeriu uma versão alternativa de merge sort que usa espaço adicional constante. Este algoritmo foi posteriormente refinado. ( Katajainen, Pasanen & Teuhola 1996 )

Além disso, muitos aplicativos de classificação externa usam uma forma de classificação por mesclagem, em que a entrada é dividida em um número maior de sublistas, idealmente para um número para o qual mesclá-las ainda faz com que o conjunto de páginas processado atualmente caiba na memória principal.

Classificação de mesclagem paralela

A classificação de mesclagem paraleliza bem devido ao uso do método de divisão e conquista . Várias variantes paralelas diferentes do algoritmo foram desenvolvidas ao longo dos anos. Alguns algoritmos de mesclagem paralela estão fortemente relacionados ao algoritmo de mesclagem sequencial de cima para baixo, enquanto outros têm uma estrutura geral diferente e usam o método de mesclagem K-way .

Mesclar classificação com recursão paralela

O procedimento de classificação de mesclagem sequencial pode ser descrito em duas fases, a fase de divisão e a fase de mesclagem. A primeira consiste em muitas chamadas recursivas que realizam repetidamente o mesmo processo de divisão até que as subsequências sejam classificadas trivialmente (contendo um ou nenhum elemento). Uma abordagem intuitiva é a paralelização dessas chamadas recursivas. O pseudocódigo a seguir descreve a classificação por mesclagem com recursão paralela usando as palavras-chave fork e join :

// Sort elements lo through hi (exclusive) of array A.
algorithm mergesort(A, lo, hi) is
    if lo+1 < hi then  // Two or more elements.
        mid := ⌊(lo + hi) / 2⌋
        fork mergesort(A, lo, mid)
        mergesort(A, mid, hi)
        join
        merge(A, lo, mid, hi)

Este algoritmo é a modificação trivial da versão sequencial e não paraleliza bem. Portanto, sua aceleração não é muito impressionante. Tem um intervalo de , que é apenas uma melhoria em comparação com a versão sequencial (consulte a Introdução aos Algoritmos ). Isso se deve principalmente ao método de mesclagem sequencial, pois é o gargalo das execuções paralelas. ${\ displaystyle \ Theta (n)}$${\ displaystyle \ Theta (\ log n)}$

Mesclar classificação com mesclagem paralela

Um melhor paralelismo pode ser alcançado usando um algoritmo de mesclagem paralela . Cormen et al. apresentam uma variante binária que mescla duas subseqüências classificadas em uma seqüência de saída classificada.

Em uma das sequências (a mais longa se o comprimento for desigual), o elemento do índice do meio é selecionado. A sua posição na outra sequência é determinada de tal forma que esta sequência permaneceria ordenada se este elemento fosse inserido nesta posição. Assim, sabe-se quantos outros elementos de ambas as sequências são menores e a posição do elemento selecionado na sequência de saída pode ser calculada. Para as sequências parciais dos elementos menores e maiores criados dessa forma, o algoritmo de mesclagem é executado novamente em paralelo até que o caso base da recursão seja alcançado.

O pseudocódigo a seguir mostra o método de classificação de mesclagem paralela modificado usando o algoritmo de mesclagem paralela (adotado de Cormen et al.).

/**
 * A: Input array
 * B: Output array
 * lo: lower bound
 * hi: upper bound
 * off: offset
 */
algorithm parallelMergesort(A, lo, hi, B, off) is
    len := hi - lo + 1
    if len == 1 then
        B[off] := A[lo]
    else let T[1..len] be a new array
        mid := ⌊(lo + hi) / 2⌋ 
        mid' := mid - lo + 1
        fork parallelMergesort(A, lo, mid, T, 1)
        parallelMergesort(A, mid + 1, hi, T, mid' + 1) 
        join 
        parallelMerge(T, 1, mid', mid' + 1, len, B, off)

Para analisar uma relação de recorrência para o pior caso, as chamadas recursivas de parallelMergesort devem ser incorporadas apenas uma vez devido à sua execução paralela, obtendo

$${\ 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 \ esquerda (\ log (n) ^ {2} \ direita).}$$

Para obter informações detalhadas sobre a complexidade do procedimento de mesclagem paralela, consulte Algoritmo de mesclagem .

A solução desta recorrência é dada por

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

Este algoritmo de mesclagem paralela atinge um paralelismo de , que é muito maior do que o paralelismo do algoritmo anterior. Essa classificação pode ter um bom desempenho na prática quando combinada com uma classificação sequencial rápida e estável, como classificação por inserção , e uma fusão sequencial rápida como um caso base para mesclar pequenos arrays. ${\ textstyle \ Theta \ left ({\ frac {n} {(\ log n) ^ {2}}} \ right)}$

Classificação de mesclagem de múltiplas vias paralelas

Parece arbitrário restringir os algoritmos de classificação por mesclagem a um método de mesclagem binário, uma vez que geralmente há p> 2 processadores disponíveis. Uma abordagem melhor pode ser usar um método de mesclagem K-way , uma generalização da mesclagem binária, na qual sequências ordenadas são mescladas. Esta variante de mesclagem é adequada para descrever um algoritmo de classificação em um PRAM . ${\ displaystyle k}$

Ideia básica

O processo de mesclagem de múltiplas vias paralelas em quatro processadores para .${\ displaystyle t_ {0}}$${\ displaystyle t_ {3}}$

Dada uma sequência não classificada de elementos, o objetivo é classificar a sequência com os processadores disponíveis . Esses elementos são distribuídos igualmente entre todos os processadores e classificados localmente usando um algoritmo de classificação sequencial . Portanto, a sequência consiste em sequências classificadas de comprimento . Para simplificação, deixe ser um 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}$

Essas sequências serão usadas para realizar uma seleção / seleção de divisor de múltiplas sequências. Pois , o algoritmo determina os elementos divisores com classificação global . Em seguida, as posições correspondentes de em cada sequência são determinadas com pesquisa binária e, portanto, são posteriormente particionados em subsequências com . ${\ 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}) \}}$

Além disso, os elementos de são atribuídos ao processador , significa todos os elementos entre a classificação e a classificação , que são distribuídos por todos . Assim, cada processador recebe uma sequência de sequências classificadas. O fato de que a classificação dos elementos divisores foi escolhida globalmente, fornece duas propriedades importantes: Por um lado, foi escolhido de forma que cada processador ainda pode operar em elementos após a atribuição. O algoritmo tem balanceamento de carga perfeito . Por outro lado, todos os elementos do processador são menores ou iguais a todos os elementos do processador . Conseqüentemente, cada processador realiza a mesclagem de via p localmente e, assim, obtém uma sequência classificada de suas subseqüências. Por causa da segunda propriedade, não é necessário realizar mais p -way-merge, os resultados precisam apenas ser colocados juntos na ordem do número do processador. ${\ 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}$

Seleção multi-sequência

Em sua forma mais simples, dadas as sequências ordenadas distribuídas uniformemente nos processadores e uma classificação , a tarefa é encontrar um elemento com uma classificação global na união das sequências. Portanto, isso pode ser usado para dividir cada um em duas partes em um índice de divisão , onde a parte inferior contém apenas os elementos que são menores do que , enquanto os elementos maiores do que estão localizados na 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}$

O algoritmo sequencial apresentado retorna os índices das divisões em cada sequência, por exemplo, os índices em sequências tais que tenham uma classificação global menor que e . ${\ 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}$

algorithm msSelect(S : Array of sorted Sequences [S_1,..,S_p], k : int) is
    for i = 1 to p do 
	(l_i, r_i) = (0, |S_i|-1)
	
    while there exists i: l_i < r_i do
	// pick Pivot Element in S_j[l_j], .., S_j[r_j], chose random j uniformly
	v := pickPivot(S, l, r)
	for i = 1 to p do 
	    m_i = binarySearch(v, S_i[l_i, r_i]) // sequentially
	if m_1 + ... + m_p >= k then // m_1+ ... + m_p is the global rank of v
	    r := m  // vector assignment
	else
	    l := m 
	
    return l

Para a análise de complexidade, o modelo PRAM é escolhido. Se os dados forem distribuídos uniformemente por todos , a execução da dobra p do método binarySearch terá um tempo de execução de . A profundidade de recursão esperada é como no Quickselect comum . Portanto, o tempo de execução geral esperado é . ${\ 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 na classificação de mesclagem de múltiplos caminhos paralela, esse algoritmo deve ser invocado em paralelo de forma que todos os elementos divisores de classificação para sejam encontrados simultaneamente. Esses elementos divisores podem então ser usados ​​para particionar cada sequência em partes, com o mesmo tempo total de execução de . ${\ textstyle i {\ frac {n} {p}}}$${\ displaystyle i = 1, .., p}$${\ displaystyle p}$${\ displaystyle {\ mathcal {O}} \ left (p \, \ log (n / p) \ log (n) \ right)}$

Pseudo-código

Abaixo, o pseudocódigo completo do algoritmo de ordenação de mesclagem de múltiplas vias paralelas é fornecido. Assumimos que há uma sincronização de barreira antes e depois da seleção multisssequência, de modo que cada processador pode determinar os elementos de divisão e a partição da sequência de maneira adequada.

/**
 * d: Unsorted Array of Elements
 * n: Number of Elements
 * p: Number of Processors
 * return Sorted Array
 */
algorithm parallelMultiwayMergesort(d : Array, n : int, p : int) is
    o := new Array[0, n]                         // the output array
    for i = 1 to p do in parallel                // each processor in parallel
        S_i := d[(i-1) * n/p, i * n/p] 	         // Sequence of length n/p
	sort(S_i)                                // sort locally
        synch
	v_i := msSelect([S_1,...,S_p], i * n/p)          // element with global rank i * n/p
        synch
	(S_i,1, ..., S_i,p) := sequence_partitioning(si, v_1, ..., v_p) // split s_i into subsequences
	    
	o[(i-1) * n/p, i * n/p] := kWayMerge(s_1,i, ..., s_p,i)  // merge and assign to output array
	
    return o

Análise

Em primeiro lugar, cada processador classifica os elementos atribuídos localmente usando um algoritmo de classificação com complexidade . Depois disso, os elementos divisores devem ser calculados a tempo . Finalmente, cada grupo de divisões deve ser mesclado em paralelo por cada processador com um tempo de execução de uso de um algoritmo de mesclagem sequencial p-way . Assim, o tempo geral de execução é 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}} \ direita) \ log (n) + {\ frac {n} {p}} \ log (p) \ direita)}$.

Adaptação prática e aplicação

O algoritmo de classificação de mesclagem de várias vias é muito escalonável por meio de sua alta capacidade de paralelização, que permite o uso de muitos processadores. Isso torna o algoritmo um candidato viável para classificar grandes quantidades de dados, como aqueles processados ​​em clusters de computador . Além disso, como em tais sistemas a memória geralmente não é um recurso limitante, a desvantagem da complexidade do espaço da classificação de mesclagem é insignificante. No entanto, outros fatores tornam-se importantes em tais sistemas, que não são levados em consideração na modelagem em um PRAM . Aqui, os seguintes aspectos precisam ser considerados: Hierarquia de memória , quando os dados não cabem no cache dos processadores, ou a sobrecarga de comunicação da troca de dados entre os processadores, que pode se tornar um gargalo quando os dados não podem mais ser acessados ​​por meio do compartilhamento memória.

Sanders et al. apresentaram em seu artigo um algoritmo paralelo síncrono em massa para mesclagem de múltiplos níveis multinível, que divide os processadores em grupos de tamanho . Todos os processadores são classificados primeiro localmente. Ao contrário do mergesort multiway de nível único, essas sequências são então particionadas em partes e atribuídas aos grupos de processadores apropriados. Essas etapas são repetidas recursivamente nesses grupos. Isso reduz a comunicação e, principalmente, evita problemas com muitas mensagens pequenas. A estrutura hierárquica da rede real subjacente pode ser usada para definir os grupos de processadores (por exemplo , racks , clusters , ...). ${\ displaystyle p}$${\ displaystyle r}$${\ displaystyle p '}$${\ displaystyle r}$

Outras variantes

A classificação de mesclagem foi um dos primeiros algoritmos de classificação em que a velocidade ideal foi alcançada, com Richard Cole usando um algoritmo de subamostragem inteligente para garantir a fusão O (1). Outros algoritmos sofisticados de classificação paralela podem atingir os mesmos ou melhores limites de tempo com uma constante inferior. Por exemplo, em 1991, David Powers descreveu um quicksort paralelizado (e um tipo de raiz relacionado ) que pode operar em tempo O (log n ) em uma máquina de acesso aleatório paralela CRCW (PRAM) com n processadores executando particionamento implicitamente. Powers mostra ainda que uma versão em pipeline do Batcher Bitonic Mergesort no tempo O ((log n ) ² ) em uma rede de classificação de borboletas é, na prática, realmente mais rápida do que sua classificação O (log n ) em um PRAM, e ele fornece uma discussão detalhada sobre o overheads ocultos em comparação, radix e classificação paralela.

Comparação com outros algoritmos de classificação

Embora o heapsort tenha os mesmos limites de tempo que o merge sort, ele requer apenas Θ (1) espaço auxiliar em vez do Θ ( n ) do merge sort . Em arquiteturas modernas típicas, implementações de quicksort eficientes geralmente superam a classificação de mesclagem para classificar matrizes baseadas em RAM. Por outro lado, a classificação por mesclagem é uma classificação estável e mais eficiente no tratamento de mídia sequencial de acesso lento. A ordenação por mesclagem é muitas vezes a melhor escolha para ordenar uma lista vinculada : nesta situação é relativamente fácil implementar uma ordenação por mesclagem de tal forma que requer apenas Θ (1) espaço extra e o desempenho de acesso aleatório lento de um link list faz com que alguns outros algoritmos (como quicksort) tenham um desempenho insatisfatório e outros (como heapsort) completamente impossíveis.

A partir do Perl 5.8, merge sort é seu algoritmo de ordenação padrão (era quicksort nas versões anteriores do Perl). Em Java , os métodos Arrays.sort () usam merge sort ou um quicksort ajustado dependendo dos tipos de dados e, para eficiência de implementação, mude para a ordenação por inserção quando menos de sete elementos do array estão sendo classificados. O kernel Linux usa merge sort para suas listas vinculadas. Python usa Timsort , outro híbrido ajustado de classificação por mesclagem e classificação por inserção, que se tornou o algoritmo de classificação padrão no Java SE 7 (para matrizes de tipos não primitivos), na plataforma Android e no GNU Octave .

Notas

Referências

• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. Introdução aos algoritmos (3ª ed.). MIT Press e McGraw-Hill. ISBN 0-262-03384-4.
• Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). "Mergesort prático no local" . Nordic Journal of Computing . 3 (1): 27–40. CiteSeerX  10.1.1.22.8523 . ISSN  1236-6064 . Arquivado do original em 07/08/2011 . Página visitada em 2009-04-04 .. Também Prático In-Place Mergesort . Também [3]
• Knuth, Donald (1998). "Seção 5.2.4: Classificação por fusão". Classificando e pesquisando . The Art of Computer Programming . 3 (2ª ed.). Addison-Wesley. pp. 158–168. ISBN 0-201-89685-0.
• Kronrod, MA (1969). “Algoritmo de ordenação ideal sem campo operacional”. Matemática Soviética - Doklady . 10 : 744.
• LaMarca, A .; Ladner, RE (1997). “A influência dos caches no desempenho da triagem”. Proc. 8th Ann. ACM-SIAM Symp. On Discrete Algorithms (SODA97) : 370–379. CiteSeerX  10.1.1.31.1153 .
• Skiena, Steven S. (2008). "4.5: Mergesort: Classificando por Dividir e Conquistar". The Algorithm Design Manual (2ª ed.). Springer. pp. 120-125. ISBN 978-1-84800-069-8.
• Sun Microsystems. "API de matrizes (Java SE 6)" . Página visitada em 2007-11-19 .
• Oracle Corp. "Arrays (Java SE 10 e JDK 10)" . Página visitada em 23/07/2018 .

links externos

• Algoritmos de classificação animados: mesclagem de classificação na máquina Wayback (arquivado em 6 de março de 2015) - demonstração gráfica
• Estruturas de dados abertas - Seção 11.1.1 - Classificar por mesclagem , Pat Morin