Ich habe das sehr häufige Problem, einen Index für ein festplatteninternes Array von Zeichenfolgen zu erstellen. Kurz gesagt, ich muss die Position jeder Zeichenfolge in der platteninternen Darstellung speichern. Eine sehr naive Lösung wäre beispielsweise ein Index-Array wie folgt:

uint64 idx [] = {0, 20, 500, 1024, ..., 103434};

Dies besagt, dass sich die erste Zeichenfolge an Position 0, die zweite an Position 20, die dritte an Position 500 und die n-te an Position 103434 befindet.

Die Positionen sind immer nicht negative 64-Bit-Ganzzahlen in sequentieller Reihenfolge. Obwohl die Zahlen um jeden Unterschied variieren können, erwarte ich in der Praxis einen typischen Unterschied im Bereich von 2 ^ 8 bis 2 ^ 20. Ich gehe davon aus, dass dieser Index im Speicher abgelegt wird und dass auf die Positionen zufällig zugegriffen wird (unter der Annahme einer gleichmäßigen Verteilung).

Ich dachte darüber nach, meinen eigenen Code zu schreiben, um eine Art Block-Delta-Codierung oder eine andere komplexere Codierung durchzuführen, aber es gibt so viele verschiedene Kompromisse zwischen Codierungs- / Decodierungsgeschwindigkeit und Speicherplatz, dass ich mir lieber eine funktionierende Bibliothek als Ausgangspunkt zulegen würde und sich vielleicht sogar mit etwas ohne Anpassungen zufrieden geben.

Irgendwelche Hinweise? Eine C-Bibliothek wäre ideal, aber eine C ++ -Bibliothek würde es mir auch ermöglichen, einige anfängliche Benchmarks durchzuführen.

Ein paar weitere Details, wenn Sie noch folgen. Dies wird verwendet, um eine Bibliothek ähnlich wie cdb (zu erstellen.http://cr.yp.to/cdb/cdbmake.html) oben die Bibliothek cmph (http://cmph.sf.net). Kurz gesagt, handelt es sich um eine große festplattenbasierte assoziative Lesekarte mit einem kleinen Index im Speicher.

Da es sich um eine Bibliothek handelt, habe ich keine Kontrolle über die Eingabe, aber der typische Anwendungsfall, den ich optimieren möchte, hat Millionen von Hunderten von Werten, eine Durchschnittsgröße in den Bereichen von wenigen Kilobyte und einen Maximalwert von 2 ^ 31.

Wenn ich für den Datensatz keine Bibliothek vorfinde, die zur Verwendung bereit ist, beabsichtige ich, eine Delta-Codierung in Blöcken mit 64 Ganzzahlen zu implementieren, wobei die Anfangsbytes den Blockversatz bis jetzt angeben. Die Blöcke selbst würden mit einem Baum indiziert, was mir eine Zugriffszeit von 0 (log (n / 64)) gäbe. Es gibt viel zu viele andere Optionen und ich würde es vorziehen, sie nicht zu diskutieren. Ich freue mich sehr darauf, Code anstelle von Ideen zur Implementierung der Codierung zu verwenden. Ich werde froh sein, mit allen zu teilen, was ich getan habe, wenn es funktioniert.

Ich bedanke mich für Ihre Hilfe und teile mir mit, wenn Sie irgendwelche Zweifel haben.