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

eGospodarka.pl › Grupy › pl.comp.programming › Jak stwierdzić wielkość użytecznej wolnej pamięci? › Re: Jak stwierdzić wielkość użytecznej wolnej pamięci?

Path: news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed2.atman.pl!newsfeed.atman.pl!.P
OSTED!not-for-mail
From: bartekltg <b...@g...com>
Newsgroups: pl.comp.programming
Subject: Re: Jak stwierdzić wielkość użytecznej wolnej pamięci?
Date: Fri, 3 Feb 2017 20:03:57 +0100
Organization: ATMAN - ATM S.A.
Lines: 80
Message-ID: <o72k6t$k3k$1@node1.news.atman.pl>
References: <o6vv41$dl7$1@node2.news.atman.pl>
<6...@g...com>
<o71va5$ub4$1@node1.news.atman.pl> <s...@j...net>
<o72gei$g9k$1@node1.news.atman.pl> <o72ihq$ib5$1@node1.news.atman.pl>
NNTP-Posting-Host: 89-70-119-159.dynamic.chello.pl
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: node1.news.atman.pl 1486148637 20596 89.70.119.159 (3 Feb 2017 19:03:57 GMT)
X-Complaints-To: u...@a...pl
NNTP-Posting-Date: Fri, 3 Feb 2017 19:03:57 +0000 (UTC)
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101
Thunderbird/45.5.1
In-Reply-To: <o72ihq$ib5$1@node1.news.atman.pl>
Xref: news-archive.icm.edu.pl pl.comp.programming:210222
[ ukryj nagłówki ]
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 ;-)