Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #29394

Re: Jak stwierdzić wielkość użytecznej wolnej pamięci?

Show all headers | View raw

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/wyklady/ALG/Algusm5_1.pdf
> http://zofia.kruczkiewicz.staff.iiar.pwr.wroc.pl/wyklady/ALG/Algusm5_2.pdf
> http://zofia.kruczkiewicz.staff.iiar.pwr.wroc.pl/wyklady/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/Comp521F10Lecture17.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 ;-)

Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Jak stwierdzić wielkość użytecznej wolnej pamięci? Borneq <borneq@antyspam.hidden.pl> - 2017-02-02 19:51 +0100
  Re: Jak stwierdzić wielkość użytecznej wolnej pamięci? Maciej Sobczak <see.my.homepage@gmail.com> - 2017-02-03 04:51 -0800
    Re: Jak stwierdzić wielkość użytecznej wolnej pamięci? Borneq <borneq@antyspam.hidden.pl> - 2017-02-03 14:07 +0100
      Re: Jak stwierdzić wielkość użytecznej wolnej pamięci? "Stachu 'Dozzie' K." <dozzie@go.eat.some.screws.spammer.invalid> - 2017-02-03 14:15 +0000
        Re: Jak stwierdzić wielkość użytecznej wolnej pamięci? Borneq <borneq@antyspam.hidden.pl> - 2017-02-03 15:18 +0100
          Re: Jak stwierdzić wielkość użytecznej wolnej pamięci? "Stachu 'Dozzie' K." <dozzie@go.eat.some.screws.spammer.invalid> - 2017-02-03 16:30 +0000
        Re: Jak stwierdzić wielkość użytecznej wolnej pamięci? bartekltg <bartekltg@gmail.com> - 2017-02-03 18:59 +0100
          Re: Jak stwierdzić wielkość użytecznej wolnej pamięci? Borneq <borneq@antyspam.hidden.pl> - 2017-02-03 19:35 +0100
            Re: Jak stwierdzić wielkość użytecznej wolnej pamięci? Borneq <borneq@antyspam.hidden.pl> - 2017-02-03 19:41 +0100
            Re: Jak stwierdzić wielkość użytecznej wolnej pamięci? bartekltg <bartekltg@gmail.com> - 2017-02-03 20:03 +0100
              Re: Jak stwierdzić wielkość użytecznej wolnej pamięci? Borneq <borneq@antyspam.hidden.pl> - 2017-02-03 20:08 +0100
                Re: Jak stwierdzi? wielko?? u?ytecznej wolnej pami?ci? antispam@math.uni.wroc.pl - 2017-02-04 02:16 +0000
              Re: Jak stwierdzić wielkość użytecznej wolnej pamięci? Borneq <borneq@antyspam.hidden.pl> - 2017-02-07 23:42 +0100
                Re: Jak stwierdzić wielkość użytecznej wolnej pamięci? Borneq <borneq@antyspam.hidden.pl> - 2017-02-07 23:52 +0100
      Re: Jak stwierdzić wielkość użytecznej wolnej pamięci? "M.M." <mmarszik@gmail.com> - 2017-02-04 05:59 -0800
  Re: Jak stwierdzić wielkość użytecznej wolnej pamięci? Bartłomiej Golenko <bartek@zts.ita.pwr.wroc.pl> - 2017-02-21 21:40 +0000
    Re: Jak stwierdzić wielkość użytecznej wolnej pamięci? gof@somewhere.invalid (Adam Wysocki) - 2017-02-22 14:12 +0000
      Re: Jak stwierdzić wielkość użytecznej wolnej pamięci? "Stachu 'Dozzie' K." <dozzie@go.eat.some.screws.spammer.invalid> - 2017-02-22 14:30 +0000
      Re: Jak stwierdzić wielkość użytecznej wolnej pamięci? bartekltg <bartekltg@gmail.com> - 2017-02-22 15:32 +0100
        Re: Jak stwierdzić wielkość użytecznej wolnej pamięci? gof@somewhere.invalid (Adam Wysocki) - 2017-02-22 14:53 +0000
        Re: Jak stwierdzić wielkość użytecznej wolnej pamięci? "Stachu 'Dozzie' K." <dozzie@go.eat.some.screws.spammer.invalid> - 2017-02-22 15:19 +0000

csiph-web