1. Dom
  2. Pytanie i odpowiedź
  3. Znajdź zduplikowane ciągi w dużym pliku

Znajdź zduplikowane ciągi w dużym pliku

2010-10-09 12 views

Odpowiedz

4

Podziel plik na N części. Na każdej maszynie załaduj jak najwięcej części do pamięci i posortuj łańcuchy. Zapisz te porcje do pamięci masowej na tej maszynie. Na każdym komputerze połącz porcje w jeden strumień, a następnie połącz strumień z każdej maszyny ze strumieniem zawierającym wszystkie ciągi w porządku posortowanym. Porównaj każdy ciąg z poprzednim. Jeśli są takie same, jest to duplikat.

Źródło

2010-10-09 18:26:14 erickson

+0

Aby scalić porcje w jeden strumień, musisz załadować wszystkie rekordy w pamięci. W przypadku pliku zapisu 1 mil, wszystkie rekordy 1 mil musiałby być w pamięci na ostatnim etapie scalania w powyższym algorytmie, prawda? Jeśli tak, to to pokonuje cel. –

+0

@AndyDufresne "Aby scalić porcje w jeden strumień, musisz załadować wszystkie rekordy do pamięci." Nie, nie zrobiłbyś tego. Potrzebujesz tylko tyle pamięci, aby załadować kolejny ciąg z każdej części naraz, aby je porównać. Po wykonaniu porównania następny ciąg zajmie tę przestrzeń pamięci. – erickson

+0

Nie rozumiem twojego algorytmu scalania. Załóżmy, że mamy plik zapisu 1 mil i tylko 5k rekordów może być załadowanych do pamięci. Z tego, co zrozumiałem, muszę najpierw podzielić plik na N elementów z 5K rekordami każdy. Następnie posortuj wszystkie rekordy w każdym pliku rekordów 5k i odpisz. Aby scalić dwa pliki rekordów 5k, musiałbym załadować pamięć o wielkości 10k w pamięci? Jeśli nie o to ci chodziło, możesz wyjaśnić, jak znaleźć duplikaty rekordów w pliku rekordu 1 mil z limitem pamięci ładowania tylko 5-krotnych rekordów. –

8

Odpowiedź ericksona jest prawdopodobnie oczekiwana przez kogoś, kto postawił to pytanie.

Można użyć każdej z maszyn N jak wiadro w hashtable:

  • dla każdej struny, (słownie liczba ciąg i kolejno) obliczenie funkcji skrótu na nim h.
  • wysłać wartości i i h do numeru maszyny n do przechowywania, gdzie n = h% N.
  • z każdego komputera, pobrać listę wszystkich wartości skrótu h, dla których otrzymano więcej niż jeden indeks, łącznie z listą indeksów.
  • sprawdź zestawy ciągów o równych wartościach skrótu, aby sprawdzić, czy są one rzeczywiście równe.

Szczerze mówiąc, za 10 miliardów łańcuchów można to prawdopodobnie zrobić na 1 komputerze. Hashtable może zajmować około 80-120 GB z 32-bitowym hash, w zależności od dokładnej implementacji hashtable. Jeśli szukasz wydajnego rozwiązania, musisz być nieco bardziej dokładny, co masz na myśli, mówiąc "maszyna", ponieważ zależy to od tego, ile jest w nim miejsca, a także od względnego kosztu komunikacji sieciowej.

Źródło

2010-10-09 19:27:41

Powiązane problemy

 Powiązane problemy