C++ effiziente und kompakte Karte mit ganzzahligen Tasten

Question

Ich habe 200 Sätze von etwa 50.000 eindeutige ganze Zahlen im Bereich von 0 bis 500.000 Ich muss auf einen anderen kleinen Wert (Paar von Ints, Werte sind nicht verwandt, also keine On-Demand-Berechnung) zuordnen.

Ich versuchte mit std :: unordered_maps, und das verwendete rund 50MB (gemessen in VS2015 Heap-Diagnose-Tool), und während die Leistung war in Ordnung Id möchte diese Speicherauslastung (auf einige kleine 500 MB Cloud-Server).

Effektiv meine ursprüngliche Version war 200 getrennt std::unordered_map<int, std::pair<int, int>>.

Eine Option scheint ein sortiertes Array zu sein und binäre Suche zu verwenden, aber gibt es noch etwas anderes?

Answer 1

Ich denke, sortierte Vektor sollte funktionieren, wenn Sie den Vektor nicht ändern, sobald es sortiert ist. Es ist wirklich platzsparend, d. H. Kein Zeiger-Overhead.

Wenn Sie noch bessere Leistung brauchen, und etwas gegen eine Bibliothek von Drittanbietern. Sie können versuchen sparse_hash_map, die Hash-Map mit sehr wenig Speicherplatzaufwand implementieren.

Answer 2

Ich denke, dass die meisten Speicher effizient ein std::vector<std::pair<int, std::set<Something>>> sein wird, wie Sie bereits vorgeschlagen.

In diesem Fall werden Sie nur Speicher-Overhead als Ergebnis haben:

• die fix Gemeinkosten von std :: vector (sehr begrenzt)
• Manchmal ist eine höhere Speichernutzung während der ‚wachsen‘ wie die alten Daten und die neuen in diesem Moment am leben zu sein haben
• der freie Speicherplatz in std :: vector

Sie irgendwie zeigen, dass nach dem Aufbau muss man nicht mehr den Vektor verlängern, damit entweder können Sie reserve oder shrink_to_fit den ungenutzten Raum loswerden. (Beachten Sie, dass die Reserve auch die Spikes im Speicherverbrauch während des Wachstums korrigiert)

Wenn Sie eine dichtere Nutzung hätten, könnten Sie den Speicher auf std::vector<std::set<Something>> oder std::vector<std::unique_ptr<std::set<Something>>> ändern. In dieser Struktur ist der Index implizit, obwohl der Speichergewinn nur angezeigt wird, wenn Sie für jeden Index einen Wert haben.

Der Nachteil der Verwendung eines Vektors besteht darin, dass Sie einen benutzerdefinierten Code schreiben müssen. In diesem Fall std::unordered_map und std::map nicht so schlimm ist, wenn Sie nicht mehr Cache-Misses auf dem Prozessor-Caches (L1 ...) für weniger Standardimplementierungen ausmachen, könnte man überprüfen Googles sparsehash, Googles cpp-btree oder Facebooks AtomicHashMap from Folly, obwohl ich don‘ Ich habe keine Erfahrung damit.

Schließlich könnte man sich wundern, warum Sie diese Daten alle im Speicher haben, obwohl ich keine Möglichkeit sehe, dies zu verhindern, wenn Sie optimale Leistung benötigen.

Answer 3

Für eine effiziente Speicherung können Sie, abhängig vom genauen Wertebereich, Bitoperationen verwenden, um die Schlüssel/Wert-Paare in einem einzigen Wert zu speichern: Wenn die Werte beispielsweise sehr klein sind, könnten Sie sogar 24 Bit verwenden die Schlüssel und 8 Bits für die Werte, was zu einem einzelnen 32-Bit-Eintrag führt. Ich glaube, dass die meisten Compiler heutzutage 32- oder 64-Bit-Alignments verwenden, so dass das Speichern von beispielsweise 32-Bit-Schlüsseln und 16-Bit-Werten immer noch 64 Bit pro Eintrag erfordert. Die Verwendung einfacher Komprimierung kann auch für die Leistung von Vorteil sein, wenn der Flaschenhals die Speicherbus- und Cache-Fehler sind, und nicht die CPU selbst.

Dann hängt es von der Art der Operationen ab, die Sie ausführen möchten. Die einfachste Art, die Schlüssel zu speichern, wäre ein sortiertes Array von Strukturen oder der kombinierte Ley/Value-Eintrag, den ich oben vorgeschlagen habe. Dies ist schnell und sehr platzsparend, erfordert jedoch O (log n) Lookup.

Wenn Sie etwas ausgefallener sein möchten, könnten Sie perfect hashing verwenden, die Idee ist es, eine Hash-Funktion zu finden, die eindeutige Hash-Werte für jeden Schlüssel erzeugt. Dies ermöglicht, dass die Hashmap ein einfaches Array ist, das nur geringfügig größer sein muss als das sortierte Array, das ich oben vorgeschlagen habe. Das Finden einer guten Hash-Funktion sollte relativ schnell sein, Sie können es noch einfacher machen, indem Sie das Array ein wenig größer machen und einige ungenutzte Felder im Array zulassen. Here ist eine Implementierung von perfektem Hashing, aber ich habe es selbst nicht verwendet.

In beiden Fällen wäre der Speicherverbrauch: (Anzahl der Paare) * (Bit pro Eintrag) Bit, plus Speichern der Hash-Funktion, wenn Sie den zweiten Ansatz verwenden.

** EDIT **

Aktualisiert nach Kommentar von @FireLancer. Außerdem wurden einige Wörter zur Leistung von komprimierten Arrays hinzugefügt.