W dniu 2012-11-24 12:36, bartekltg pisze:

>
> Mając dodatkową pamięć dysku równo pierwotnej tablicy
> (a tak naprawdę 0.5) możemy posortować tablicę
> w 4 przebiegach _sekwencyjnego_ odczytu/zapisu.
>
> Dominantę w posortowanej tablicy znajdujemy już
> liniowo i szybko.
>
> Jak sortujemy: pobieramy paczki po 512MB (albo mnijsze,
> jeśli nasze 512MB jest sztywne i nie możemy dodać tym
> czegoś lon(n)), sortujemy w RAM czymkolwiek sprawnym.
>
> Mamy 8 posortowanych fragmentów pliku. Łączymy je mergesortem.
> w 4, w 2, i w końcu w posortowany.
>
> Co istotne, merga robimy nie bezpośrednio na dysku, ale na
> buforach w ramie. Pobieramy odcinki po jakies 100MB,
> kręcimy procedurą w mergesort, jak któryś bufor się wyczerpie,
> napełniamy go ponownie kolejnymi danymi z dysku.
>
> Dzięki temu czytamy sekwencyjnie, dysk nie lata ciągle np między
> początkiem a środkiem pliku.
>
> Niestety, nadal n log (n) i n*log(n/|RAM|) operacji (Sekwencyjnych)
> na dysku, ale równoważnych przesłaniu tych kilkudziesięciu GB
> - robialne.

Optymalizacja: znajdowanie dominanty można upchnąć w ostatnią
fazę mergesorta. Odpada jeden odczyt.
Jeśli posortowana tablica nie jest nam do szczęścia potrzebna,
możemy też jej nie zapisywać.
Czyli 4 odczyty i 3 zapisy (4 zapisy, jeśli chcemy zachować
posortowaną tablicę na potem)
oba +1 jeśli użyjemy kawałków po 256MB.

pzdr
bartek