On 03.02.2017 19:35, Borneq wrote:
> W dniu 03.02.2017 o 18:59, bartekltg pisze:
>> Z drugiej strony to problem istotny tylko przy słąbych algorytmach.
>> Jeśli skorzystać z 256 plików, to 65 terabajtów posortuję za pomocą
>> gigabajta w trzech seriach odczyt/zapis ;-)
>
> A tego nie znałem. Stosowałem
> http://zofia.kruczkiewicz.staff.iiar.pwr.wroc.pl/wyk
lady/ALG/Algusm5_1.pdf
> http://zofia.kruczkiewicz.staff.iiar.pwr.wroc.pl/wyk
lady/ALG/Algusm5_2.pdf
> http://zofia.kruczkiewicz.staff.iiar.pwr.wroc.pl/wyk
lady/ALG/Algusm5_3.pdf

Mistrzostwo dydaktyki to nie jest.

> pliki o rozmiarach wynikających z ciągu Fibonacciego któregoś rzędu.
> Przy czym te pliki zachowywały się jak kolejka, nie można było usunąć z
> początku (przydałyby się dziury plikowe) to wzrastały do co najmiej
> wielkości sortowanego pliku.

A to w jakimkolwiek pliku (systemie operacyjnym) można przesunąć
poczatek pliku?


> Więc metoda 3 plikowa wymaga 3 krotnie
> więcej dysku niż ten plik, 5 - plikowa mniej przebiegów ale więcej dysku.
> Co zrobić aby te 256 plików nie zajmowało 256*65 TB = 17 Petabajtów dysku?

Masz dwa razy więcej dysku.

Wczytujesz umówiony gigabajt do pamięci, sortujesz, zapisujesz do nowego
pliku.
Masz (rozmiar / 1GB) plików po 1GB.
Kasujesz oryginały.
Robisz merge na 256 plikach na raz.
Masz więc w kolejnych fazach
(rozmiar / 1GB)/265
(rozmiar / 1GB)/256^2
...
pliów.


Jak robisz merge na raz więcej niż jednemu plikowi?

Trzymasz parę(wartość, indeks)
indeks to numer pliku z którego pochodzi wartość.
Na start wypełniasz je jednym elementem z każdego pliku.

Zabierasz parę z wierzchołka kopca, wartosć do pliku wyjściowego,
z pliku indeks wsadzasz do kopca jeden element.



Oczywiście, nie czytasz pliów po elementcuie, tylko je sobie buforujesz
w pamięci. Bufory nie muszą być wcale duże, byle się wygodnie czytało
z dysku.

256 plików wynika raczej z ograniczenia pamięci (przy naszych
załozeniach mamy po 4MB na plik) niż z tego, że kopiec by słabo
działał dla większej liczby.


Tu widzę jakieś wariacje na temat:
http://www.csbio.unc.edu/mcmillan/Media/Comp521F10Le
cture17.pdf
Ładnie, kolorowo, bez traści kodu z którego i tak nie skorzystamy ;-)


pzdr
bartekltg

PS: z drugiego postu nic nie rozumiem.
Chyba jednak mówimy o czym innym ;-)