Mit Hash Karten eine extrem große Datenquelle darstellen

Question

Ich habe eine sehr großen möglichen Datensatz, den ich auf einmal sichtbar zu machen versuchen. Das Set selbst besteht aus Hunderttausenden von Segmenten, von denen jeder auf eine ID zugeordnet ist.

Ich habe eine zweite Datenquelle erhalten, die mehr Echtzeitinformationen für jedes Segment gibt, aber die IDs entsprechen nicht den ids ich habe.

Ich habe eine 1: 1-Abbildung der Daten-ID (9-Zeichenketten) auf die aktuellen IDs (Long Integer). Das Problem ist, dass es eine Menge von IDs ist, und die Daten, die kommt in ist in keiner bestimmten Reihenfolge.

Die Lösung kam ich mit einer Hash-Karte zu haben, der die Saiten auf die Straße ids abbildet. Das Problem ist, dass ich weiß nicht, ob die Hash-Karte effizient genug sein wird, alle 166k Dateneinträge zu haben.

Hat jemand irgendwelche Vorschläge und / oder Hash-Algorithmen, die ich für dieses verwenden kann?

Answer 1

Wenn Sie nur mit Hunderttausenden von Datenpunkten zu tun, wird es wahrscheinlich nicht ein Problem mit dem naiven Weg zu gehen und nur Stick mit einer Hash-Karte.

Auch wenn Sie 500.000 9-Zeichenkette und eine gleiche Anzahl von longs, dass nach wie vor nur 16ish Bytes pro Artikel haben, oder 8.000.000 Bytes insgesamt. Auch wenn Sie doppelt so hoch für Overhead, 16 MB kaum zu groß sind, auf einmal im Speicher zu haben.

Im Grunde versuchen, die einfache Möglichkeit, zuerst, und nur darum kümmern, wenn der Profiler sagt Ihnen, es zu lange dauert.

Answer 2

Judy Arrays für diese Art von Dingen bestimmt: „Judys wichtigsten Vorteile sind Skalierbarkeit, hohe Leistung, und Speichereffizienz. [...] Judy können viele gemeinsame Datenstrukturen ersetzen, wie Arrays, sparse-Arrays, Hash-Tabellen, B-Bäume, binäre Bäume, lineare Listen, skiplists, andere Art und Suchalgorithmen und Zählfunktionen.“

Answer 3

Da die Kommentare zu der Frage geben die primären Anliegen können die Speichernutzung sein:

• Verwenden Sie ein Pooling oder andere kleine objektoptimierte allocator ; vorausgesetzt, Sie haben Zugriff zu steigern Sie wahrscheinlich einen Drop-in-Ersatz in Pool . ein besseren Kleines Objekt allocator verwenden ist wahrscheinlich der größte Speicher gewinnen Sie finden.
• Wenn Sie wissen, die Saiten mit fester Breite sind, Sie können sicherstellen, dass Sie sind nur genügend Platz Zuweisung , um sie zu speichern. Zum Beispiel, wickelte eine Struktur um ein feste Länge char [] mit einem benutzerdefinierten Vergleichsoperator arbeiten kann besser als ein std :: string. std :: string kommt mit einer zusätzlichen dynamischen Zuordnung (und verwendet Platz für den entsprechenden Zeiger) und einige zusätzliche Größe und Kapazitäts-Overhead zu verfolgen. (In der Regel versuchen, reduziert die Anzahl der Zuweisungen , die sich um Stick;. Reduziert Overhead)
• (STL Angenommen) Schauen Sie sich den Ober Unterschied zwischen std :: map und std :: unordered_map (letztere kann oder zur Zeit noch nicht zur Verfügung steht); eine RBtree-basierte std :: map kann auf die Lookup-Leistungsmerkmale Ihres „hashmap“ nahe genug sein und (oder auch nicht) kann mehr Speicher effizient je nach Standard-Bibliothek Implementierung.

Welche Route nehmen Sie an info beeinflusst werden soll, können Sie sammeln -. Versuchen, ein Bild von der Anzahl der Allocs und alloc Größe / Ausrichtung-Overhead zu bekommen

Sie können entweder Instrument Ihre allocator oder ein paar Elemente einfügen und sehen Sie, wie Sie im Vergleich zu tun, wie Sie denken, sollten Sie in Bezug auf die Speichernutzung tun.

Answer 4

Da die Saiten bekannt sind vorne und haben eine feste Länge, theoretisch und praktisch die beste Lösung ist ein perfekt Hash. Sie könnten verwenden CMPH es zu erzeugen.

Laut Wikipedia Ihre Schlüssel woud 2,5 Bit / Schlüssel nehmen, oder etwa 50 KB. Das ist vernachlässigbar im Vergleich zu dem 664KB für die Werte.

Answer 5

Obwohl 166k Dateneinträge ist eher klein IMO können Sie sich auch unter google-sparsehash