Speicher effizient int-int dict in Python

Sie können den IIBtree von Zope

Ich weiß nicht, ob es sich um eine One-Shot-Lösung oder um einen Teil eines laufenden Projekts handelt, aber wenn es Ersteres ist, wirft es mehr RAM als die notwendige Entwicklerzeit, um die Speichernutzung zu optimieren? Selbst bei 64 Byte pro Paar sehen Sie immer noch nur 15 GB, was in die meisten Desktop-Boxen problemlos passt.

Ich denke, die richtige Antwort liegt wahrscheinlich in den SciPy / NumPy-Bibliotheken, aber ich kenne die Bibliothek nicht genug, um Ihnen genau zu sagen, wo Sie suchen müssen.

Ссылка

Sie finden vielleicht auch einige nützliche Ideen in diesem Thread: Memory Efficient Alternativen zu Python Dictionaries

8 Bytes pro Schlüssel / Wert-Paar wären unter jeder Implementierung, Python oder anders, ziemlich schwierig. Wenn Sie keine Garantie haben, dass die Schlüssel zusammenhängend sind, dann würden Sie entweder viel Platz zwischen den Schlüsseln verschwenden, indem Sie eine Array-Repräsentation verwenden (oder eine Art von totem Wert benötigen, um einen Null-Schlüssel anzuzeigen), oder Sie Ich brauche einen separaten Index für Schlüssel / Wert-Paare, der definitionsgemäß Ihre 8 Bytes pro Paar überschreiten würde (wenn auch nur in geringem Umfang).

Ich schlage vor, Sie gehen mit Ihrer Array-Methode, aber der beste Ansatz hängt von der Art der Schlüssel ab, die ich erwarte.

Wenn Sie Ihre Daten oben betrachten, sind das nicht 49 Bytes pro int, es ist 25. Die anderen 24 Bytes pro Eintrag sind die int-Objekte selbst. Sie benötigen also etwas, das deutlich kleiner ist als 25 Bytes pro Eintrag. Es sei denn, Sie werden auch die int-Objekte neu implementieren, was zumindest für die Schlüssel-Hashes möglich ist. Oder implementieren Sie es in C, wo Sie die Objekte vollständig überspringen können (das ist, was Zopes IIBTree tut, oben erwähnt).

Um ehrlich zu sein, das Python-Wörterbuch ist in vielerlei Hinsicht sehr gut abgestimmt. Es wird nicht einfach sein, es zu übertreffen, aber viel Glück.

Wie wäre es mit einem Judy-Array, wenn Sie aus Ints mappen? Es ist eine Art Sparse-Array ... Verwendet 1/4 des Platzes der Wörterbuchimplementierung.

Judy:

Wörterbuch:

~ 1/4 der Raum:

(Ich benutze 64-Bit-Python, also meine Basis-Nummern können aufgrund von 64-Bit-Zeigern aufgebläht sein)

Ich habe mein eigenes int-int-Wörterbuch implementiert, hier verfügbar (BSD-Lizenz). Kurz gesagt, verwende ich array.array('i') , um Schlüssel / Wert-Paare nach Schlüsseln sortiert zu speichern. Statt eines großen Arrays halte ich ein Wörterbuch kleinerer Arrays (ein Schlüssel / Wert-Paar ist im Array key/65536 th gespeichert), um die Verschiebung während des Einfügens und die binäre Suche während des Abrufens zu beschleunigen. Jedes Array speichert die Schlüssel und Werte auf folgende Weise:

Eigentlich ist es nicht nur ein int-int-Dictionary, sondern ein allgemeines Objekt-int-Dictionary mit Objekten, die auf ihre Hashes reduziert sind. Daher kann das Hash-Int-Wörterbuch als Cache eines persistent gespeicherten Wörterbuchs verwendet werden.

Es gibt drei mögliche Strategien zur Behandlung von "Schlüsselkollisionen", dh Versuche, demselben Schlüssel einen anderen Wert zuzuweisen. Die Standardstrategie erlaubt es. Das "Löschen" entfernt den Schlüssel und markiert ihn als kollidierend, so dass weitere Versuche, ihm einen Wert zuzuweisen, keine Wirkung haben werden. Die "Geschrei" -Strategie löst während eines Überschreibversuchs und bei jedem weiteren Zugriff auf einen kollidierenden Schlüssel eine Ausnahme aus.

Siehe meine Antwort zu eine verwandte Frage für eine anders formulierte Beschreibung meines Ansatzes.