Effizientes Entfernen von Duplikaten mit geringem Speicheraufwand

Ich möchte eine Liste von Ganzzahlen effizient nach Duplikaten filtern, sodass nur die resultierende Menge gespeichert werden muss.

Ein Weg dies kann gesehen werden:

• wir haben einen Bereich von ganzen Zahlen mit N groß (sagen wir 2 40 )$S = \{1, \dots{}, N\}$$N$$2^{40}$
• wir haben eine Funktion mit angeblich vielen Kollisionen (die Bilder sind gleichmäßig in S verteilt )$f : S \to S$$S$
• wir müssen dann speichern , das heißt { f ( x ) | x ∈ S $f[S]$$\{f(x) | x \in S\}$

Ich habe eine ziemlich genaue (probabilistische) Schätzung dessen, was ist und kann daher Datenstrukturen im Voraus zuweisen (sagen wir | f [ S ] | ≈ 2 30 ).$|f[S]|$$|f[S]| \approx 2^{30}$

Ich hatte einige Ideen, bin mir aber nicht sicher, was der beste Ansatz wäre:

• Ein Bitset kommt nicht in Frage, da der Eingabesatz nicht in den Speicher passt.
• eine Hash-Tabelle, aber (1) es erfordert etwas Speicher-Overhead, sagen wir 150% von und (2) die Tabelle muss beim Erstellen untersucht werden, was aufgrund des Speicheraufwands zusätzliche Zeit erfordert.$|f[S]|$
• eine "on the fly" -Sorte, vorzugsweise mit -Komplexität (Nichtvergleichssortierung). In Bezug darauf bin ich mir nicht sicher, was der Hauptunterschied zwischen Bucket Sort und Flashsort ist .$O(N)$
• Ein einfaches Array mit einem binären Suchbaum, für das jedoch erforderlich ist .$O(N \log |f[S]|)$
• Möglicherweise kann die Verwendung von Bloom-Filtern oder einer ähnlichen Datenstruktur hilfreich sein, um das Problem zu lösen (mit falsch positiven Ergebnissen).

Einige Fragen zu Stackoverflow scheinen sich mit solchen Dingen zu befassen ( /programming/12240997/sorting-array-in-on-run-time , /programming/3951547/java) -array-find-duplicates ), aber keines scheint meinen Anforderungen zu entsprechen.

Warum nicht Mülleimer und Kette?

Die Idee besteht darin, positive ganze Zahlen, die durch Bits darstellbar sind, in einem Array A von 2 k Einträgen zu speichern, die Wertebereiche darstellen: Eintrag A [ y ] , y ≥ 0 , repräsentiert den Bereich [ 2 m y , 2 m ( y) + 1 ) - 1 ] . Für jede 1 ≤ x < 2 n können wir x = 2 m y schreiben$n = k+m$$A$$2^k$$A[y]$$y \ge 0$$[2^m y, 2^m(y+1)-1]$$1 \le x \lt 2^n$ , wo y hat k Bits und z hat m Bits. Versuchen Sie, z (nicht x !) An Position y zu speichern:$x = 2^m y + z$$y$$k$$z$$m$$z$$x$$y$

• Wenn bereits ist, tun Sie nichts: x ist ein Duplikat.$A[y]=z$$x$

• Wenn nicht initialisiert ist, speichern Sie z bei A [ y ] .$A[y]$$z$$A[y]$

• Andernfalls speichert einen Index in eine separate Anordnung zur Ketten des ‚s (die bei kollidiert ist y ) in verknüpften Listen. Sie müssen die Liste mit der Überschrift A [ y ] linear durchsuchen und je nachdem, was die Suche aufdeckt, möglicherweise z in die Liste einfügen .$z$$y$$A[y]$$z$

Am Ende, ist leicht durch Einschleifen durch die initialisierten Einträge zu erholen A und - lediglich durch zwei Bitstrings Verketten - Zusammenbauen jeden Z an der Stelle gefunden y (entweder direkt oder innerhalb einer Kette referenzierten dort) in die ursprünglichen Wert x = 2 m y + z .$f(S)$$A$$z$$y$$x = 2^m y + z$

Wenn die Verteilung nahezu gleichmäßig ist und N überschreitet , kommt es zu keiner starken Verkettung (dies kann auf die übliche Weise beurteilt werden), und die Ketten sind tendenziell kurz. Wenn die Verteilung ungleichmäßig ist, funktioniert der Algorithmus immer noch, kann jedoch ein quadratisches Timing erreichen. Wenn dies möglich ist, verwenden Sie etwas Effizienteres als Ketten (und zahlen Sie ein wenig Overhead für die Lagerung).$2^k$$N$

Der benötigte Speicher beträgt höchstens Bits für A und 2 2 k Bits für die Ketten (unter der Annahme von m ≤ k ). Dies ist genau der Speicherplatz, der zum Speichern von 2 k- Werten mit jeweils n Bits benötigt wird. Wenn Sie von der Einheitlichkeit überzeugt sind, können Sie den Speicher für die Ketten zu wenig zuordnen. Wenn eine Ungleichmäßigkeit möglich ist, möchten Sie möglicherweise k erhöhen und die Kettenspeicherung vollständig befürworten.$2^n$$A$$2^{2k}$$m \le k$$2^k$$n$$k$

Eine alternative Art, über diese Lösung nachzudenken, besteht darin, dass es sich um eine Hash-Tabelle mit einer besonders schönen Hash-Funktion handelt (nehmen Sie die höchstwertigen Bits), und aus diesem Grund müssen wir nur die niedrigstwertigen m = n - k Bits in speichern Der Tisch.$k$$m=n-k$

Es gibt Möglichkeiten, Speicher für die Ketten mit dem Speicher für zu überlagern, aber es scheint die Mühe nicht wert zu sein, da dies nicht viel Platz spart (vorausgesetzt, m ist viel kleiner als k ) und die Entwicklung des Codes erschwert. debuggen und pflegen.$A$$m$$k$