DAA - Padrão de fusão ideal
Mescle um conjunto de arquivos classificados de comprimentos diferentes em um único arquivo classificado. Precisamos encontrar uma solução ótima, onde o arquivo resultante será gerado em tempo mínimo.
Se o número de arquivos classificados for fornecido, há muitas maneiras de mesclá-los em um único arquivo classificado. Esta fusão pode ser realizada em pares. Portanto, este tipo de fusão é chamado de2-way merge patterns.
Como diferentes emparelhamentos requerem diferentes períodos de tempo, nesta estratégia queremos determinar uma maneira ideal de mesclar muitos arquivos. Em cada etapa, duas sequências mais curtas são mescladas.
Para fundir um p-record file e um q-record file requer possivelmente p + q gravar movimentos, sendo a escolha óbvia, mesclar os dois arquivos menores em cada etapa.
Os padrões de mesclagem bidirecional podem ser representados por árvores de mesclagem binárias. Vamos considerar um conjunto den arquivos classificados {f1, f2, f3, …, fn}. Inicialmente, cada elemento disso é considerado uma árvore binária de nó único. Para encontrar essa solução ideal, o seguinte algoritmo é usado.
Algorithm: TREE (n)
for i := 1 to n – 1 do
declare new node
node.leftchild := least (list)
node.rightchild := least (list)
node.weight) := ((node.leftchild).weight) + ((node.rightchild).weight)
insert (list, node);
return least (list);No final deste algoritmo, o peso do nó raiz representa o custo ótimo.
Exemplo
Vamos considerar os arquivos fornecidos, f 1 , f 2 , f 3 , f 4 ef 5 com 20, 30, 10, 5 e 30 números de elementos respectivamente.
Se as operações de mesclagem forem realizadas de acordo com a sequência fornecida, então
M1 = merge f1 and f2 => 20 + 30 = 50
M2 = merge M1 and f3 => 50 + 10 = 60
M3 = merge M2 and f4 => 60 + 5 = 65
M4 = merge M3 and f5 => 65 + 30 = 95
Portanto, o número total de operações é
50 + 60 + 65 + 95 = 270
Agora, surge a pergunta: existe alguma solução melhor?
Classificando os números de acordo com seu tamanho em ordem crescente, obtemos a seguinte sequência -
f4, f3, f1, f2, f5
Portanto, as operações de mesclagem podem ser realizadas nesta sequência
M1 = merge f4 and f3 => 5 + 10 = 15
M2 = merge M1 and f1 => 15 + 20 = 35
M3 = merge M2 and f2 => 35 + 30 = 65
M4 = merge M3 and f5 => 65 + 30 = 95
Portanto, o número total de operações é
15 + 35 + 65 + 95 = 210
Obviamente, isso é melhor do que o anterior.
Neste contexto, vamos agora resolver o problema usando este algoritmo.
Conjunto Inicial
Passo 1
Passo 2
Etapa 3
Passo 4
Portanto, a solução leva 15 + 35 + 60 + 95 = 205 número de comparações.