mesclagem de várias vias vs mesclagem de duas vias

10

Quando mesclamos externamente um arquivo grande, dividimos em um arquivo pequeno, classificamos os arquivos e os mesclamos de volta para um arquivo grande classificado.

Ao mesclar, podemos fazer muitas passagens de mesclagem de duas vias ou uma mesclagem multidirecional.

Eu estou querendo saber qual abordagem é melhor? e por quê?

    
por KFL 04.08.2012 в 08:22
fonte

1 resposta

6

Uma mesclagem multidirecional geralmente é melhor. Considere três arquivos pequenos:

a1
a2
a3

e

b1
b2
b3

e finalmente

c1
c2
c3

Se você fizer uma mesclagem com a e b , ficaremos com (digamos)

a1
b1
a2
b2
b3
a3

e

c1
c2
c3

Uma mesclagem final criaria a lista classificada, mas observe como nessa mesclagem final temos que visitar os itens a e b novamente. É essa re-fusão que é um desperdício em cascatas em fusões bidirecionais.

O que você pode fazer é uma mesclagem unidirecional. No entanto, tenha cuidado como você faz isso. Especificamente, evite o loop duplo ingênuo que varre cada cursor para ver qual tem o valor mínimo. Use um min-heap em vez disso. Isso trará a complexidade de volta para O(n log n) .

    
por phs 04.08.2012 / 08:39
fonte