Znajdź dwie linie w pliku, które są takie same

Question

Zostałem zadany to pytanie w wywiadzie dla Amazonki.

Masz plik z wieloma liniami, ale dwie linie są takie same. Znajdź te dwie linie. Podałem oczywistą odpowiedź, która działała w czasie N^2. Następnie wymyśliłem odpowiedź, która posłużyła się tablicą mieszającą, ale nie podobała im się ta odpowiedź, ponieważ powiedzieli, że nie zadziała, jeśli plik znajduje się w gigabajtach. Inną odpowiedzią, jaką wymyśliłem, było zamiast przechowywania wyniku haszowania w pamięci, utworzenie pliku o tej samej nazwie, co wartość skrótu, i zapisanie linii z tą samą wartością skrótu w pliku. Albo nie mogli zrozumieć mojego rozwiązania, albo im się nie podobało.

Jakieś myśli?

Dzięki

Answer 1

mogę myśleć o dwóch zasadniczych klas rozwiązań tego problemu:

1. probabilistyczne rozwiązania w pamięci. Możesz spróbować rozwiązać ten problem, przechowując podsumowanie linii pliku w pamięci głównej. Następnie możesz wykonać obliczenia w głównej pamięci, aby zidentyfikować możliwe duplikaty, a następnie sprawdzić każdy możliwy duplikat, patrząc wstecz na dysk. Rozwiązania te są prawdopodobnie najlepsze, ponieważ mają niskie zużycie pamięci, wysoką wydajność i naśladują dostęp do dysku. Rozwiązania w tej kategorii obejmują:

   1. Wylicz hash każdego wiersza pliku, a następnie zapisz hasze. Każda linia, w której występuje kolizja hash, reprezentuje jedną możliwą parę linii, które mogą się kolidować, i tylko te linie mogą być eksplorowane.
   2. Użyj filtru Bloom, aby zapisać wszystkie wiersze pliku, a następnie sprawdź tylko te pary, które kolidują z filtrem Bloom. Jest to zasadniczo odmiana (1), która jest bardziej efektywna pod względem przestrzeni.

2. Deterministyczne rozwiązania na dyskach. Możesz próbować wykonywać obliczenia z całym zestawem danych na dysku, używając pamięci głównej jako tymczasowej przestrzeni scratch. Umożliwi to uzyskanie dokładnych odpowiedzi bez konieczności przechowywania całego pliku w pamięci, ale prawdopodobnie będzie wolniejszy, chyba że wykonasz później pewne przetwarzanie i możesz skorzystać na restrukturyzacji danych.Rozwiązania w tej kategorii obejmują:

   1. Aby posortować plik, użyj zewnętrznego algorytmu sortowania (zewnętrznego szybkiego sortowania, sortowania na zewnątrz radixa itp.), A następnie przeszukuj liniowo pod kątem dwóch duplikatów elementów.
   2. Zbuduj strukturę danych na dysku, taką jak drzewo B z wszystkimi ciągami, a następnie zapytaj o drzewo B. Zajmuje to dużo czasu wstępnego przetwarzania, ale znacznie przyspiesza przyszłe operacje na pliku.
   3. Umieść wszystko w bazie danych i przeszukuj bazę danych.

Mam nadzieję, że to pomoże!

Answer 2

uruchomić poprzez linie i długościach obliczeniowych każdego wiersza. W rezultacie otrzymasz coś takiego:

0: 4 
1: 6 
2: 10 
3: 4 
.... 

Porównaj tylko te linie, które mają tę samą długość. Praca z takim indeksem może być dalej optymalizowana (np. Nie przechowywać wszystkiego w płaskiej tablicy, ale w jakimś drzewie lub czymkolwiek).

Przy okazji, drugi pomysł z plikiem może zostać odrzucony ze względu na wydajność. Zwykle dobrym pomysłem jest częste losowe IO z dyskiem twardym: staraj się przechowywać jak najwięcej w pamięci.

Answer 3

Można użyć filtru Bloom:

http://en.wikipedia.org/wiki/Bloom_filter

Następnie można wykryć (z kilku fałszywych alarmów) linie, które są powtarzane, a następnie przechowywać w pamięci, a następnie przejść do pliku po raz kolejny.

Dwa przechodzi przez plik, bardzo mało wykorzystania pamięci, piękne