Teraz, gdy jestem już po studiach zaczynam za nimi tęsknić. Ciekawe dlaczego ;)
Do rzeczy. Spotkałem się z problemem Milion na Milion. Może zagadnienie nie jest tak ciekawe jak problem C10K, ale IMHO wymaga ruszenia głową. Na czym polega ten problem?
Na znalezieniu prostej i szybkiej metody, która odpowie na pytanie: Które wersy ze zbioru 1 000 000 wersów zawierają słowo ze słownika składającego się z 1 000 000 słów?
Zanim pokażę jedno z rozwiązań, którego złożoność i czas wyszukiwania satysfakcjonuje mnie, podpuszczę tych, którzy jednak tu zerkają. Proszę w komentarzach umieścić proponowane rozwiązanie problemu.
Na koniec (13.04.2009?) wyzwania umieszczę wyniki testu wykonanego na tym samym sprzęcie i tych samych plikach dla wszystkich propozycji z komentarzy.
Dla ujednolicenia warunków pracy zamieszczam je poniżej:
- system Linux (mogą być 32-bity)
- wszystko co dostępne po standardowej instalacji dystrybucji Ubuntu (8.10 lub nowszy), ewentualnie mogę coś doinstalować.
Żeby było wszystko jasne dodam jeszcze wymaganie odnośnie czasu rozwiązania problemu: Dla 1 000 000 linii logów i słownika złożonego z 1 000 000 słów odpowiedź powinienem otrzymać w czasie poniżej 1h. (najlepiej poniżej minuty ;))
Powodzenia!
Subskrybuj:
Komentarze do posta (Atom)
1 komentarze:
Najprościej i najwolniej to mogłoby być tak:
export IFS='
'
for wyraz in `cat slownik.txt` ; do grep -wn "$wyraz" wersy.txt ; done
Prześlij komentarz