W dniu wtorek, 20 listopada 2012 18:23:43 UTC+1 użytkownik slawek napisał:

"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)."


Fajne zadanie. Tak od razu po przeczytaniu nie wiem jak je rozwiązać
szybko i zagwarantować dokładny wynik. Heurystycznie bym zrobił kolejkę
priorytetową i dodawał do niej klucze pod-ciągów, a te które wystąpiły
najrzadziej bym wywalał. W 512MB można upakować powiedzmy 60mln
par (klucz,częstość). Podciągów niestety jest 32 razy więcej.

Heurystycznie można jeszcze przejrzeć plik kilka razy, z różnych
offsetów i w rożnych kolejnościach.

Co tam jeszcze może być pomocne... 256MB pamięci RAM to 2G bitów. Można
funkcją hash ustawić bity. Jeśli bit jest ustawiony, a klucza nie ma
w kolejce, to być może klucz został przedwcześnie usunięty z kolejki. Może w
takich sytuacjach należy się cofnąć na początek pliku, policzyć częstość
tylko tego jednego klucza, a jeśli częstość przekroczy minimum jakie jest
w kolejce, to dodać go z powrotem. Zdaje się że taki algorytm przy doskonałej
funkcji hash gwarantuje rozwiązanie. Jednak po pierwsze doskonałej nie da się
zrobić dla każdych danych, a po drugie nawrotów na początek pliku może być
dużo - więc czas obliczeń może być długi. Niby można policzyć kilka razy dla
różnych funkcji hash - ale to też nie zagwarantuje rozwiązania na 100%.



Pozdrawiam