Istnieją dwie liczby całkowite, każda w bardzo dużych plikach (każdy rozmiar jest większy niż pamięć RAM). Jak znaleźć elementy wspólne w tablicach w czasie liniowym?Znajdź wspólne elementy z dwóch bardzo dużych tablic:
Nie mogę znaleźć przyzwoitego rozwiązania tego problemu. Jakieś pomysły?
Jedno przejście na jeden plik - zbuduj bitmapę (lub Bloom filter, jeśli zakres całkowity jest zbyt duży dla mapy bitowej w pamięci).
Jedno przejście drugiego pliku powoduje znalezienie duplikatów (lub kandydatów w przypadku użycia filtru Bloom).
Jeśli używasz filtru Bloom, wynik jest probabilistyczny. Nowe podania mogą zredukować fałszywy wynik pozytywny (filtry Blooma nie mają fałszywych wartości ujemnych).
ok. Muszę teraz przeczytać o filtrach kwiatowych. crap: P –
Dla 4-bajtowych liczb całkowitych, nie potrzebujesz filtra Bloom, tylko 0.5Gb pamięci. – AProgrammer
thats tooable chyba. brzmi jak dobre rozwiązanie. dzięki. –
Oczywiście można użyć tabeli mieszania, aby znaleźć wspólne elementy o złożoności czasu O (n).
Najpierw należy utworzyć tablicę asocjacyjną przy użyciu pierwszej tablicy, a następnie porównać drugą tablicę za pomocą tej tabeli mieszania.
Rozmiar listy jest WIĘKSZY niż w pamięci RAM. Twój hashtable nie będzie posiadał żadnej tablicy całkowicie ..:/ –
oczywiście będziesz musiał zaimplementować mieszanie oparte na plikach. – CashCow
proszę opracować ... co masz na myśli –
Zakładając, że mówimy o liczbach całkowitych o tym samym rozmiarze i zapisanych w plikach w trybie binarnym, najpierw sortuj 2 pliki (użyj quicksorta, ale odczytywanie i zapisywanie do pliku "przesunięć"). Następnie wystarczy przejść od początku 2 plików i sprawdzić pod kątem zgodności, jeśli masz dopasowanie, wypisz wynik do innego pliku (zakładając, że nie możesz zapisać wyniku w pamięci) i kontynuuj przenoszenie plików do EOF.
Sortowanie nie jest O (n) zgodnie z wymaganiami. –
Sortowanie liczb całkowitych o stałej wielkości jest w rzeczywistości O (n): sortowanie radix. Jednak obsługa plików większych niż pamięć może stanowić problem. – blaze
Sortowanie plików. W przypadku liczb całkowitych o stałej długości można to zrobić w czasie O (n):
Na posortowanych plikach znajdź wspólny podzbiór liczb całkowitych: porównaj liczby, zapisz je, jeśli są one równe, a następnie wykonaj krok o jeden numer naprzód w pliku o mniejszej liczbie. To jest O (n).
Wszystkie operacje to O (n), a ostateczny algorytm to również O (n).
EDYCJA: metoda bitmapowa jest znacznie szybsza, jeśli masz wystarczającą ilość pamięci dla bitmap. Ta metoda działa dla dowolnych stałych liczb całkowitych, na przykład 64-bitowych. Bitmapa o rozmiarze 2^31 Mb nie będzie praktyczna przez co najmniej kilka lat :)
Zakładając, że wielkość całkowita ma 4 bajty. Teraz możemy mieć maksymalnie 2^32 liczby całkowite, np. Mogę mieć bitvector z 2^32 bitami (512 MB) do reprezentowania wszystkich liczb całkowitych, gdzie każdy bit reprezentuje jedną liczbę całkowitą. 1. Inicjalizuj ten wektor wszystkimi zerami 2. Teraz przejdź przez jeden plik i ustaw bity w tym wektorze na 1, jeśli znajdziesz liczbę całkowitą. 3. Teraz przejdź przez inny plik i poszukaj dowolnego zestawu bitów w bitach Vector.
Złożoność O (n + m) przestrzeń złożoność 512 MB
Działa to tylko wtedy, gdy wiele wystąpień może być traktowanych jak pojedyncze wyjście. Świetnie w mojej opinii. –
2^32 bity to 512 MB, czyż nie? – blaze
To prawie tak samo jak powyższe rozwiązanie " –
Załóżmy wystarczająco pamięć RAM jest dostępna do przechowywania 5% mieszania każdej dany plik array (FA).
Tak, mogę podzielić tablice plików (FA1 i FA2) na 20 kawałków każda - powiedzmy, wykonaj MOD 20 zawartości. Otrzymujemy FA1 (0) ....FA1 (19) i FA2 (0) ...... FA2 (19). Można to zrobić w czasie liniowym.
Hash FA1 (0) w pamięci i porównaj zawartość FA2 (0) z tym hashem. Hashing i sprawdzanie istnienia są ciągłymi operacjami czasowymi.
Zniszcz ten skrót i powtórz dla FA1 (1) ... FA1 (19). Jest to również liniowe. Cała operacja jest liniowa.
czy zostały posortowane? –
nr .. liczby losowe –
Jaki rozmiar całkowity? – harold