Znajdowanie elementu, który występuje najczęściej w bardzo dużym pliku

Słyszałem to pytanie podczas wywiadu i miałem nadzieję uzyskać opinie na temat dobrych odpowiedzi: masz duży plik 10+ GB i chcesz dowiedzieć się, który element występuje najczęściej, co jest dobrym sposobem zrobić to?

Iterowanie i śledzenie mapy prawdopodobnie nie jest dobrym pomysłem, ponieważ zużywasz dużo pamięci, a śledzenie pojawiających się wpisów nie jest najlepszą opcją, ponieważ po postawieniu tego pytania plik zwykle już istnieje.

Inne przemyślenia, które załączyłem, to podzielenie pliku, który ma być iterowany i przetwarzany przez wiele wątków, a następnie połączyć te wyniki, ale problem dotyczący pamięci dla map nadal występuje.

Kiedy masz naprawdę duży plik i jest w nim wiele elementów, ale najbardziej powszechny element jest bardzo powszechny - występuje w ułamku czasu - możesz go znaleźć w czasie liniowym ze słowami spacji stała w notacji jest bardzo mała, w zasadzie 2, jeśli nie policzysz pamięci na rzeczy pomocnicze, takie jak haszowanie. Co więcej, działa to świetnie z pamięcią zewnętrzną, ponieważ plik jest przetwarzany w sekwencji jeden element na raz, a algorytm nigdy nie „ogląda się wstecz”. Jednym ze sposobów, aby to zrobić, jest klasyczny algorytm Misry i Griesa, patrz notatki z wykładu . Problem ten jest obecnie znany jako problem ciężkich uderzających (częstymi elementami są ciężkie uderzające).$> 1/k$$O(k)$$O()$

Założenie, że najczęściej pojawia się element ułamka czasu dla małej liczby, może wydawać się silne, ale jest to w pewien sposób konieczne! To znaczy, jeśli będziesz miał sekwencyjny dostęp do swojego pliku (a jeśli plik jest ogromny losowy dostęp będzie zbyt drogi), każdy algorytm, który zawsze znajdzie najczęstszy element w stałej liczbie przejść, użyje spacji liniowej w liczbie elementów . Więc jeśli nie zakładasz czegoś o danych wejściowych, nie możesz pobić tabeli skrótów. Założenie, że najczęstszy element jest bardzo częsty, jest być może najbardziej naturalnym sposobem na obejście negatywnych wyników.$> 1/k$$k$

Oto szkic dla , tj. Gdy występuje pojedynczy element, który występuje w ponad połowie przypadków. Ten szczególny przypadek jest znany jako algorytm głosowania większościowego i jest spowodowany przez Boyera i Moore'a. Zachowamy jeden element i jedną liczbę. Zainicjuj licznik na 1 i zapisz pierwszy element pliku. Następnie przetworz plik w sekwencji:$k = 2$

• jeśli bieżący element pliku jest taki sam jak element przechowywany, zwiększ liczbę o jeden
• jeśli bieżący element pliku różni się od zapisanego elementu, zmniejsz liczbę o jeden
• jeśli zaktualizowana liczba wynosi 0, „wykop” zapisany element i zapisz bieżący element pliku; zwiększyć liczbę do 1
• przejdź do następnego elementu pliku

Trochę myślenia o tej procedurze przekona cię, że jeśli istnieje element „większościowy”, tj. Taki, który występuje ponad połowę czasu, to element ten będzie elementem przechowywanym po przetworzeniu całego pliku.

Dla ogólnego , zachować elementów i liczy się, i zainicjować elementy do pierwszej różnych elementów pliku oraz liczbę do liczby razy każdy z tych elementów wydaje się, zanim zobaczyć -tego wyraźny element. Następnie wykonujesz zasadniczo tę samą procedurę: liczba elementów jest zwiększana za każdym razem, gdy się napotyka, wszystkie liczby elementów są zmniejszane, jeśli napotkany jest element, który nie jest przechowywany, a gdy pewna liczba jest równa zero, element ten jest wykopywany na korzyść bieżący element pliku. To jest algorytm Misra-Gries.$k$$k-1$k $k-1$$k$$k$

Oczywiście możesz użyć tabeli skrótów do zindeksowania przechowywanych elementów . Na zakończenie algorytm gwarantuje, że zwróci każdy element, który wystąpi częściej niż ułamka czasu. Jest to w zasadzie najlepsze, co możesz zrobić z algorytmem, który wykonuje stałą liczbę przejść przez plik i przechowuje tylko słów.1 / k O ( k $k-1$$1/k$$O(k)$

I ostatnia rzecz: po znalezieniu kandydatów na „ciężkich hitterów” (tj. Częstych elementów), możesz wykonać jeszcze jedno przejście przez plik, aby policzyć częstotliwość każdego elementu. W ten sposób można uszeregować elementów między sobą i sprawdzić, czy wszystko z nimi występować więcej niż ułamek czasu (jeśli istnieją mniej niż takich elementów, niektóre z elementów zwracanych przez algorytm może być fałszywie dodatnie ).1 / k k - $k$$1/k$$k-1$

Oczywistą odpowiedzią jest oczywiście utrzymanie mapy skrótów i przechowywanie licznika występowania elementów podczas przeglądania pliku, jak już sugerował Nejc. Jest to (pod względem złożoności czasowej) optymalne rozwiązanie.

Jeśli jednak masz mało miejsca, możesz wykonać sortowanie zewnętrzne w pliku, a następnie znaleźć najdłuższy kolejny ciąg równych elementów. Poniższe powinny mieć stały ślad pamięci i można to zrobić w$\Theta(n\log{n}).$

Jeśli najbardziej powszechny element jest znacznie powszechniejszy niż następny wspólny element o znaczny margines, a liczba różnych elementów jest niewielka w porównaniu do rozmiaru pliku, możesz losowo próbkować kilka elementów i zwracać najczęstszy element w próbce.