W dniu 2012-11-24 02:49, Michoo pisze:
> On 20.11.2012 18:23, slawek wrote:
>
>> Aby nie być posądzanym o niekonstruktywną krytykę zapodam przykład (ktoś
>> chciał informatycznych wyzwań, żeby coś ciekawego było itd.) - to takie
>> zadanko:
>
> W ten sposób usunąłeś z zadanka jeden z ciekawych elementów, czyli "o co
> tu chodzi".
>
>>
>> "Dany jest plik długości 2 gigabajtów (tj. 2*1024*1024*1024). Wśród
>> wszystkich możliwych podciągów 16-bajtowych (których jest 2**31 - 2^4 +
>> 1, bo wybieramy kolejne bajty) znaleźć taki, który najczęściej występuje
>> w tym pliku. Uwaga: dane w pliku /mogą/ być zupełnie przypadkowe, może
>> też cały plik być wypełniony zerami itd. itp. - wszystkie złośliwe
>> przypadki dozwolone - tzn. nie wolno zgadywać, trzeba sprawdzić.
>> Premiowane będą rozwiązania szybkie i oszczędzające pamięć (zakładamy że
>> mamy tylko 512 MB RAM do dyspozycji)."
>
> Mamy problem znalezienia dominanty w zbiorze liczb 16 bajtowych. Jeżeli
> dobrze szacuję (a nie chce mi się poświęcać na to zadanko za dużo czasu):
> - dla działania w miejscu mamy O(n^2)
> - dla dodatkowej pamięci na dysku w rozmiarze 16*n schodzimy do
> O(n*log(n)) (Ale z uwzględnieniem losowych odwołań do dysku)
> - dla dodatkowej pamięci na dysku w rozmiarze 2*16*n schodzimy do
> O(n*log(n)) (Z sekwencyjnym dostępem, więc wielokrotnie szybciej niż w
> poprzednim przypadku.)

> n to oczywiście liczba liczb w ciągu

Być może opisuje to samo, co Ty w ostatnim punkcie.

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.

BTW. w Cormenie chyba były algorytmy 'sortowanie zewnętrznego'.
Może warto zajrzeć, bo będzie coś sprytniejszego.


Kołaczą mi się sztuczki ze statystyką i nie jestem pewien,
czy nie da się tego zrobić lepiej. Ale ciężko będzie,
5 przbiegów po dysku to podejrzewam minimum.
W koncu nawet log(n) jest większe.

pzdr
bartek