Wirkungsgrad: Welche Datenstruktur soll verwendet werden...?

Question

Ich arbeite mit einem sehr großen Datensatz. Im Wesentlichen werde ich mit Millionen von Datensätzen arbeiten und einen Wert in einem Dataset speichern.

Jedes Mal, wenn ich einen Wert speichere, muss ich zunächst prüfen, ob der Wert nicht bereits in der Datenstruktur enthalten ist. Wenn sich der Wert in der Datenstruktur befindet, muss ich den Datensatz aktualisieren (oder entfernen/hinzufügen), um die Zählung zu aktualisieren.

Es gibt Wiederholungen innerhalb des Datensatzes, und ich möchte keine schlechte Datenstruktur verwenden und eine Geschwindigkeit von O(n) erreichen, da ich in der Lage sein möchte, dies über Nacht laufen zu lassen und am Morgen damit fertig zu sein!

Haben Sie einen Rat?

Answer 1

Wie bereits gesagt wurde, ist eine Hash-Tabelle wahrscheinlich die richtige Antwort, sondern Hash-Tabellen sind nicht sehr platzsparend. Wenn Sie also an den Punkt kommen, an dem Ihr Speicher voll ist, sollten Sie ein sortiertes Array von Schlüsseln und ein parallel sortiertes Array von Werten in Betracht ziehen. Wenn Sie im Voraus Zugriff auf die gesamte Schlüsselliste haben, erstellen Sie ein Array mit diesen Schlüsseln und sortieren Sie es. Dann erstellen Sie ein paralleles Array mit Werten. Jedes Mal, wenn Sie etwas speichern müssen, führen Sie einfach eine binäre Suche (O(log N)) durch, um den Index im Schlüssel-Array zu finden, und aktualisieren dann den entsprechenden Index im Werte-Array. Dies ist zwar weniger schnell als eine Hash-Tabelle, garantiert aber praktisch keinen Platzbedarf.

Answer 2

Es klingt, als wollten Sie eine Hash-Tabelle , kombiniert mit (möglicherweise) einer Liste oder einer bestimmten Struktur. Das klingt für mich wie eine Datenbank .

Answer 3

Eine Hashtabelle verwenden

Answer 4

Sie könnten es mit einem Binärbaum versuchen. log_2(1.000.000) ist etwa 20. Dies könnte besser sein, wenn Sie nicht wissen, was alle Schlüssel im Voraus sein werden.