Speichereffizienter String-to-String-Karte in Python (oder C)

StackOverflow https://stackoverflow.com/questions/4026359

Frage

Ich brauche eine speichereffiziente Datenstruktur für zum Speichern von über eine Million Schlüssel - Wert-Paare, bei denen Schlüssel sind Strings von etwa 80 Bytes und Werte sind Strings von etwa 200 Bytes, die Gesamt Schlüssel und Wert Größe ca. 280 MB sein . Ich brauche auch eine effiziente Nachschlagen Wert von Schlüssel, vorzugsweise eine Hash-Karte. Die Speicher-Overhead sollte so wenig wie möglich sein, beispielsweise für 280MB von Nutzdaten, sollte die Datenstruktur verwenden Sie nicht mehr als 300 MB des virtuellen Speichers (einschließlich malloc() Overhead und alles andere). Die Nutzungsmuster sind folgende: wir mit einer leeren Datenstruktur zu starten, und wir füllen es allmählich, nie Schlüssel zu ändern, und nie die Länge der Werte zu ändern. Als Plus kann die Datenstruktur unterstützen die Länge der Werte, auf Kosten einer 100% Wert Overhead zu wechseln (was bedeutet, dass für x-Wert Bytes x Bytes könnte in vorübergehend in nicht genutzten Pufferraum verschwendet werden).

Ich brauche ein reines Python Modul oder einen eingebauten in Python-Modul oder eine C Umsetzung vorzugsweise mit (C) Python-Bindungen. Ich würde es vorziehen, wenn es möglich ist, die gesamte Datenstruktur auf dem Datenträger serialisiert wird, und es wieder sehr schnell zu lesen.

Nur um zu beweisen, dass ein so kleiner Aufwand ist möglich, ich habe ein einfaches Design erstellt mit offenen Adressierung , die Hash-Tabelle von 1,25 Millionen Elemente, die 4-Byte-Zeigern auf 1MB Datenblöcken, die Datenblöcke, die Schlüssel und Wert Längen base-128 varints . Dieser Entwurf hat eine wichtige Einschränkung: es nicht zulässt, dass das Entfernen oder Paare zu ändern, ohne ihren Speicherbereich zu verschwenden. Nach meinen Berechnungen mit 1 Million key - Wertepaaren von 280 Bytes, die jeweils, ist der Overhead von weniger als 3,6% (10 080 000 Byte). Die Grenzen oben sind großzügiger, sie 20 000 000 Byte Overhead ermöglichen.

Ich habe gerade http://www.pytables.org/ , die schnellen Zugriff und speichereffizienten Verpackung von Daten. Ich muss es genauer untersuchen zu überprüfen, ob es meinen Bedürfnissen entspricht.

War es hilfreich?

Lösung 10

Da ich keine vorhandenen Lösungen finden könnte, die eng die Speicher packen, habe ich beschlossen, es in C für mich zu implementieren. Sehen Sie mein Design mit offener Adressierung in der Frage.

Andere Tipps

Ok, der schmutz einfachen Ansatz.

Verwenden Sie ein Python-Wörterbuch für die Datenstruktur. Ich füllte einen Python-Wörterbuch mit 1 Million zufälligen Schlüssel-Wert-Paaren, wo der Schlüssel 80 Zeichen und der Wert 200 Zeichen waren. Es dauerte 360.844 Kb auf meinem Computer, die außerhalb der Spezifikation von nicht mehr als 300 MB ist, aber ich biete es sich als eine Lösung trotzdem, weil es immer noch ziemlich speichereffizient ist.

Dies scheitert auch Ihre Anforderung einen C-API zu haben. Ich bin mir nicht sicher, warum Sie C benötigen, aber als die Frage Python markiert ist und es fehlt einen C-Tag, werde ich die reine Python bieten, um zu sehen, ob es vielleicht nur die Rechnung passen.

In Bezug auf Ausdauer. Verwenden Sie das cPickle Modul. Es ist sehr schnell und, wieder, schmutz einfach. So speichern Sie Ihren Wörterbuch: 

cPickle.dump(mydict, "myfile.pkl")

Ihr Wörterbuch neu zu laden: 

mydict = cPickle.load("myfile.pkl")

Eine zweite schmutz einfache Idee ist es, das shelve Modul zu verwenden, die im Grunde Disk-basierte ist Python-Wörterbuch. Speicher-Overhead ist sehr gering (es ist alles auf der Festplatte). Aber es ist auch viel langsamer.

Martijn erwähnte dies in einem Kommentar (nicht sicher, warum die Leute mit Antworten Kommentar), aber ich stimme zu: Verwendung SQLite. Sie sollten es versuchen und sehen, ob es Ihren Bedürfnissen gerecht wird.

Wenn Sie nicht eine großen Mengen von Löschungen zu haben, planen, dann ist dies nicht so schwer. Löschungen führen zu einer Fragmentierung.

Sie müssen auch auf eine feste Länge Schlüssel begehen. Sie erwähnten 80 Bytes. Sind Ihre Schlüssel erlaubt zu duplizieren? Wenn nicht, ist es noch einfacher.

So, hier ist was Sie tun.

Erstellen Sie eine Reihe von: 

struct {
    char value[80];
    char *data;
} key;

Und Sie halten dieses Array sortiert werden.

Wenn Sie Schlüssel können duplizieren, dann benötigen Sie: 

struct link {
    char *data;
    link *next;
}

struct {
    char value[80];
    link *data;
} key;

(Mein C ist rostig, aber dies ist der Kern von ihm) Letztere jeden Schlüssel auf einer verknüpften Liste von Werten hat.

Dann wird eine Lookup ist eine einfache binäre Suche. Der „Schmerz“ ist, diese Anordnung zu erhalten und das Einfügen / Löschen von Schlüsseln. Es ist nicht so schmerzhaft, wie es klingt, aber es spart viel Speicher, insbesondere auf 64-Bit-Systemen.

Was Sie wollen, zu reduzieren, ist die Anzahl der Zeiger. Zeiger sind teuer, wenn Sie viele Strukturen mit Zeigern gefüllt haben. Auf einem 64-Bit-System wird ein Zeiger 8 Bytes. Also für einen einzigen Zeiger, es geht 8MB Ihren Speicher Budget.

So ist der Aufwand der Anordnung im Gebäude, das Kopieren und Verdichtungsspeicher (wenn Sie „wissen“ Sie eine Million Zeilen haben wird und dass begehen kann, dann malloc (1000000 * sizeof (key)) sofort, es‘ ll Sie einige Kopieren während der Expansion speichern).

Aber keine Angst, wenn es mal läuft, ist die Leistung sehr gut. Moderne CPUs sind eigentlich ziemlich gut im Kopieren 100M Speicherblöcke herum.

Wie Nebenbei bemerkt, ich habe gerade etwas ähnlich wie dies in Java. Auf einem 64-Bit-JVM ist eine Karte mit 25M Einträgen 2G RAM. Meine Lösung (mit ähnlichen Techniken dazu) hat bei rund 600 m). Java verwendet mehr als Zeiger C, aber die Prämisse ist das gleiche.

Haben Sie versucht, eine einfache DIKT? Die meisten Ihrer Daten in Strings, so dass der Aufwand in Ihren Anforderungen entsprechen können.

Sie können die sha1 des Schlüssels anstelle des Schlüssels selbst. Wenn die Schlüssel eindeutig sind, dann ist die sha1 Hash des Schlüssels wahrscheinlich auch. Es bietet eine Speichereinsparungen zu Quietschen versuchen unter dem Grenzwert. 

from random import choice
from string import letters
from hashlib import sha1

def keygen(length):
    return "".join(choice(letters) for _ in xrange(length))

def gentestdata(n=1000*1000):
    # return dict((sha1(keygen(80)).digest(), keygen(200)) for _ in xrange(n))
    d = {}
    for _ in xrange(n):
        key = sha1(keygen(80)).digest()
        assert key not in d
        value = keygen(200)
        d[key] = value
    return d

if __name__ == '__main__':
    d = gentestdata()

Auf meiner Ubuntu-Box, diese Spitze liegt bei 304 MB Speicher aus: 

2010-10-26 14:26:02 hbrown@hbrown-ubuntu-wks:~$ ps aux | grep python
[...]
hbrown   12082 78.2  7.5 307420 303128 pts/1   S+   14:20   4:47 python

Es liegt nahe genug? Es ist Python, nicht C.

Später: auch, wenn Ihre Daten etwas redundant ist, können Sie die Werte gzip. Es ist eine Zeit im Vergleich zu Raum Trade-off.

SQLite ist eine gute Idee. Eine schnelle Implementierung kann sagen, wenn Sie schnell genug mit wenig Aufwand.

Wenn Sie feststellen, Sie haben Ihre eigene Rolle, würde ich empfehlen Ihnen:

Wie gut können Sie vorhersagen, die Anzahl der Paare, oder eine obere Grenze für das?
Wie gut können Sie vorhersagen, die gesamte Datengröße oder eine Obergrenze für das?

Arena allocator für Streicher und Knoten. (In der Regel, Sie auf einer Liste von Arenen arbeiten würden, so dass Sie die Gesamtgröße nicht vorhersagen müssen).

Ausrichtung auf Algorithmen hängt im Prinzip könnte man es packen Byte dicht, und die einzigen Aufwand ist Ihre Überlastung, die nur wirkt minimal Ihren Arbeitssatz.

Wenn Sie jedoch jede cmp laufen müssen / kopieren usw. Operationen auf diesem Strings, denken Sie daran, dass mit den folgenden Garantien, können Sie ein wenig oder viel von diesen String-Operationen drücken:

  • alle Elemente CPU Wort ausgerichtet
  • alle Auffüllbytes sind (z) 0
  • Sie können sicher lesen „über“ eine Zeichenfolge Ende, solange Sie keine CPU Grenze überqueren

Hash-Tabelle für den Index. Ein Wörterbuch würde auch funktionieren, aber das macht nur Sinn, wenn potenziellen Abbau / Wiederkäuen ein ernstes Problem sein würde. Ich kenne keine „Lager“ Hash-Tabelle Implementierung für C, aber es sollte man, richtig? richtig? Ersetzen Sie einfach Zuweisungen bei Anrufen in der Arena Allocator.

Speicherlokalizität

Wenn Sie diese Lookup garantieren nie einen String anfordern, die nicht in der Karte ist, sollten Sie die Schlüssel in einer separaten Arena speichern, da sie nur auf Hash-Kollisionen benötigt werden. Das kann Speicherlokalizität erheblich verbessern. (In diesem Fall, wenn Sie jemals eine „endgültige“ Tisch haben, können Sie kopieren sogar die kollidierenden Schlüssel zu einer neuen Arena, und werfen alle anderen weg. Die Vorteile, die wahrscheinlich marginal sind, though.)

Die Trennung kann helfen oder schaden, je nach Zugriffsmuster. Wenn Sie in der Regel einmal den Wert verwenden, nach jeder Lookup, sie paarweise in der gleichen Arena ist groß. Wenn Sie zum Beispiel schaut ein paar Tasten, dann verwenden, um ihre Werte immer wieder, getrennte Arenen Sinn ergeben.

Wenn Sie „lustige Zeichen“ unterstützen / Unicode, normalisiert die Saiten, bevor sie gespeichert werden.

Sie könnten struct-Modul verwenden, um binäre Daten zu packen und entpacken, wenn nötig. Sie können einen Speicher effiziente Speicherung mit diesem Ansatz implementieren. Ich denke, Zugang wäre ein Schmerz sein.

Apache Portable Runtime (auch bekannt als APR) hat eine c-basierte Hash-Tabelle. Sie können Dokumentation unter http://apr.apache.org/docs/apr/ sehen 0.9 / GROUP_ April _hash.html

Mit apr_hash_t alles, was Sie speichern ist void *. Also es gibt Ihnen die volle Kontrolle über Werte. SO, wenn Sie möchten, dass Sie Zeiger auf einen 100-Byte-Block anstelle der tatsächlichen Länge des Strings speichern können.

Judy sollte speichereffizient: http://judy.sourceforge.net/
(Benchmarks: http://www.nothings.org/computer/judy/ finden Sie unter " Datenstruktur Size ").
Siehe auch: http://www.dalkescientific.com/Python/PyJudy.html

Auch

Für Tasten einer festen Größe gibt es http://panthema.net/2007/stx-btree / in C ++ (ich bin sicher, dass mit einem benutzerdefinierten C-Wrapper kann es von CPython verwendet werden). Wenn der Datensatz es erlaubt, können Sie die Schlüssel mit variabler Länge im Wert speichern und einen Hash oder einen Präfix des Schlüssels mit variabler Länge als feste Länge Schlüssel verwenden.

Die gleiche Logik gilt für http://google-opensource.blogspot.ru/2013/01/c-containers-that-save-memory-and-time.html und http://code.google.com/p/sparsehash/ - istead einen schweren std der Verwendung :: string als Schlüssel, einen 32-Bit verwenden oder 64-Bit-integer-Schlüssel, es irgendwie von den realen Schlüsseln mit variabler Länge zu machen.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top