Skuteczne usuwanie duplikatów przy niskim obciążeniu pamięci

Chcę wydajnie filtrować listę liczb całkowitych dla duplikatów w taki sposób, że tylko wynikowy zestaw musi być przechowywany.

Można to zobaczyć na jeden sposób:

• mamy szereg liczb całkowitych $S = \{1, \dots{}, N\}$ z $N$ duży (powiedzmy $2^{40}$)
• mamy funkcję $f : S \to S$ z podobno wieloma kolizjami (obrazy są równomiernie rozmieszczone w $S$)
• następnie musimy przechowywać $f[S]$, to jest $\{f(x) | x \in S\}$

Mam dość dokładne (probabilistyczne) oszacowanie tego, co $|f[S]|$ jest i dlatego może wcześniej przydzielić struktury danych (powiedzmy $|f[S]| \approx 2^{30}$).

Miałem kilka pomysłów, ale nie jestem pewien, jakie byłoby najlepsze podejście:

• zestaw bitów nie wchodzi w rachubę, ponieważ zestaw danych wejściowych nie mieści się w pamięci.
• tablica skrótów, ale (1) wymaga trochę pamięci, powiedzmy 150% z $|f[S]|$ oraz (2) tabela musi zostać zbadana po zbudowaniu, co wymaga dodatkowego czasu z powodu narzutu pamięci.
• „w locie”, najlepiej z $O(N)$złożoność (sortowanie nieporównywalne). W związku z tym nie jestem pewien, jaka jest główna różnica między sortowaniem kubełkowym a sortowaniem flash .
• prosta tablica z binarnym drzewem wyszukiwania, ale to wymaga $O(N \log |f[S]|)$ czas.
• być może użycie filtrów Blooma lub podobnej struktury danych może być przydatne w rozluźnieniu (z fałszywymi pozytywami) problemu.

Wydaje się, że niektóre pytania dotyczące stackoverflow dotyczą tego rodzaju rzeczy ( /programming/12240997/sorting-array-in-on-run-time , /programming/3951547/java -array-find-duplicates ), ale żaden nie wydaje się odpowiadać moim wymaganiom.

Dlaczego nie bin i łańcuch?

Pomysł polega na przechowywaniu dodatnich liczb całkowitych reprezentowanych przez $n = k+m$ bity w tablicy $A$ z $2^k$ wpisy reprezentujące zakresy wartości: wpis $A[y]$, $y \ge 0$, reprezentuje zakres $[2^m y, 2^m(y+1)-1]$. Dla każdego$1 \le x \lt 2^n$ możemy pisać $x = 2^m y + z$ gdzie $y$ ma $k$ bity i $z$ ma $m$bitów Spróbuj przechowywać$z$ (nie $x$!) na miejscu $y$:

• Kiedy $A[y]=z$ już nic nie rób: $x$ jest duplikatem.

• Kiedy $A[y]$ jest niezainicjowany, zapisz $z$ w $A[y]$.

• W przeciwnym razie przechowuj indeks w osobnej tablicy używanej do łączenia łańcucha $z$(które zderzyły się w $y$) na połączonych listach. Będziesz musiał przeszukiwać liniowo listę kierowaną przez$A[y]$ i, w zależności od tego, co odkryje wyszukiwanie, potencjalnie wstaw $z$ na listę.

Na końcu, $f(S)$ można łatwo odzyskać, zapętlając zainicjowane wpisy $A$ oraz - łącząc tylko dwa ciągi bitów - ponownie je łącząc $z$ znalezione w miejscu $y$ (bezpośrednio lub w obrębie łańcucha tam wymienionego) do oryginalnej wartości $x = 2^m y + z$.

Gdy rozkład jest zbliżony do jednorodnego i $2^k$ przekracza $N$, łańcuchów nie będzie dużo (można to ocenić w zwykły sposób), a łańcuchy będą zwykle krótkie. Gdy rozkład jest nierównomierny, algorytm nadal działa, ale może osiągnąć kwadratowe taktowanie. Jeśli to możliwe, użyj czegoś wydajniejszego niż łańcuchy (i zapłać trochę kosztów ogólnych za przechowywanie).

Potrzebne miejsce jest co najwyżej $2^n$ bity dla $A$ i $2^{2k}$ bity dla łańcuchów (przy założeniu $m \le k$). To jest dokładnie miejsce potrzebne do przechowywania$2^k$ wartości $n$bitów każdy. Jeśli masz pewność co do jednolitości, możesz zbytnio przydzielić miejsce na łańcuchy. Jeśli niejednolity charakter jest możliwy, możesz chcieć zwiększyć$k$ i w pełni popieramy przechowywanie łańcucha.

Alternatywnym sposobem myślenia o tym rozwiązaniu jest to, że jest to tablica skrótów ze szczególnie przyjemną funkcją skrótu (weź$k$ najbardziej znaczące bity) i dlatego musimy przechowywać tylko najmniej znaczące $m=n-k$ bity w tabeli.

Istnieją sposoby nałożenia pamięci dla łańcuchów z pamięcią dla $A$ ale nie wydaje się to warte zawracania głowy, ponieważ nie zaoszczędziłoby wiele (zakładając $m$ jest znacznie mniejszy niż $k$) i utrudniają tworzenie, debugowanie i konserwację kodu.