Ich habe hunderttausende NumPy-Boolean-Arrays, die ich gerne als Schlüssel für ein Wörterbuch verwenden würde. (Die Werte dieses Wörterbuchs geben an, wie oft wir jedes dieser Arrays beobachtet haben.) NumPy-Arrays sind nicht hashbar und können nicht selbst als Schlüssel verwendet werden. Ich möchte diese Arrays so effizient wie möglich serialisieren.
Wir haben zwei Definitionen für die Effizienz, die hier angesprochen werden:
Ich versuche, ein gutes Gleichgewicht zwischen diesen beiden konkurrierenden Interessen zu finden, jedoch ist eine effiziente Speichernutzung für mich wichtiger und ich bin bereit, Rechenzeit zu opfern.
Es gibt zwei Eigenschaften, von denen ich hoffe, dass sie diese Aufgabe erleichtern:
1 s und 0 s, eine Bitsequenz Gibt es eine effiziente Python-Datenstruktur (2.7 oder, wenn möglich, 2.6), zu der ich diese serialisieren könnte (vielleicht eine Art Byte-Struktur), und könnten Sie ein Beispiel für die Konvertierung zwischen einem Array und dieser Struktur geben und von der Struktur zurück zum ursprünglichen Array?
Beachten Sie, dass es nicht notwendig ist, Informationen darüber zu speichern, ob jeder Index True oder False war; Eine Struktur, die einfach Indizes speicherte, wo das Array True war, würde ausreichen, um das Array wiederherzustellen.
Eine ausreichende Lösung würde für ein eindimensionales Array funktionieren, aber eine gute Lösung würde auch für ein zweidimensionales Array funktionieren, und eine große Lösung würde für Arrays mit noch höheren Dimensionen funktionieren.
Zunächst habe ich vorgeschlagen, bitarray zu verwenden. Wie jedoch von @senderle richtig ausgeführt wurde, kann bitarray nicht geändert werden, so dass es nicht direkt in dict eingefügt werden kann.
Hier ist eine überarbeitete Lösung (noch intern auf bitarray bezogen):
Dies funktioniert mit Python 2.5+, erfordert ein Bit pro Array-Element und unterstützt Arrays mit beliebigen Formen / Dimensionen.
BEARBEITEN: In den letzten Versionen müssen Sie ba.tostring und ba.fromstring auf ba.tobytes und ba.frombytes (Veraltet seit Version 0.4.0) ersetzen.
Ich habe drei Vorschläge. Meine erste wird von aix gestohlen. Das Problem ist, dass bitarray -Objekte veränderbar sind und ihre hash es inhaltsunabhängig sind (d. H. Für bitarray b , hash(b) == id(b) ). Dies kann umgangen werden, wie die Antwort von aix zeigt, aber in der Tat brauchen Sie bitarray s überhaupt nicht - Sie können einfach tostring verwenden!
Jetzt haben wir eine unveränderliche Bytefolge, die sich perfekt als Wörterbuchschlüssel eignet. Um zu verdeutlichen, dass diese Escapes nicht maskiert sind, ist dies so kompakt, wie es ohne bitstring -style Serialisierung möglich ist.
Das Zurückkonvertieren ist einfach und schnell:
%Vor% Wie Aix konnte ich nicht herausfinden, wie man Dimensionsinformationen auf einfache Weise speichert. Wenn Sie das haben müssen, müssen Sie möglicherweise längere Schlüssel ertragen. cPickle scheint jedoch eine gute Wahl zu sein. Dennoch ist seine Ausgabe 10x so groß ...
Es ist auch langsamer:
%Vor% Mein dritter Vorschlag verwendet bitstring s - speziell bitstring.ConstBitArray . Es ist ähnlich wie die aix Lösung, aber ConstBitArray s sind unveränderlich, also machen sie was du willst, hash -wise.
Sie müssen das numpy Array explizit reduzieren:
%Vor%Es ist unveränderlich, also hasst es gut:
%Vor%Es ist superleicht, wieder in ein Array zu konvertieren, aber auch hier gehen die Forminformationen verloren.
%Vor%Es ist auch die langsamste Option bei weitem:
%Vor% Hier finden Sie weitere Informationen. Ich habe weiter herumgespielt und Dinge getestet und mir folgendes ausgedacht. Erstens ist bitarray Weg schneller als bitstring , wenn Sie es richtig verwenden:
Zweitens, wie Sie oben sehen können, sind alle tostring shenanigans unnötig; Sie könnten das Array numpy auch explizit reduzieren. Aber tatsächlich ist die Methode von aix schneller, und darauf basieren die jetzt überarbeiteten Zahlen.
Hier also eine vollständige Zusammenfassung der Ergebnisse. Erstens, Definitionen:
%Vor% keysize ist das Ergebnis von sys.getsizeof({small|big}_nda.tostring()) , sys.getsizeof({small|big}_barray) + sys.getsizeof({small|big}_barray.tostring()) oder sys.getsizeof({small|big}_bstr) + sys.getsizeof({small|big}_bstr.tobytes()) - beide letzteren Methoden geben Bitstrings zurück, die in Bytes gepackt sind. Daher sollten sie eine gute Schätzung des von ihnen belegten Speicherplatzes sein.
speed ist die Zeit, die für die Konvertierung von {small|big}_nda in einen Schlüssel und zurück benötigt wird, plus die Zeit, die zum Konvertieren eines bitarray -Objekts in eine Zeichenfolge für Hashing benötigt wird, die entweder ein einmaliger Aufwand ist Sie können die Zeichenfolge oder eine Kosten pro dict-Operation zwischenspeichern, wenn Sie sie nicht zwischenspeichern.
Wie Sie sehen, ist bitarray beeindruckend schnell und aix 'Vorschlag einer Unterklasse von bitarray sollte gut funktionieren. Sicher ist es viel schneller als bitstring . Freut mich zu sehen, dass du diese Antwort akzeptiert hast.
Auf der anderen Seite fühle ich mich immer noch der Methode numpy.array.tostring() verbunden. Die Schlüssel, die es erzeugt, sind asymptotisch 8x so groß, aber die Beschleunigung, die Sie für große Arrays bekommen, bleibt beträchtlich - ungefähr 30x auf meiner Maschine für große Arrays. Es ist ein guter Kompromiss. Dennoch ist es wahrscheinlich nicht genug, sich damit zu beschäftigen, bis es zum Flaschenhals wird.
Ich würde das Array mit np.packbits in ein Bitfeld konvertieren. Dies ist ziemlich speichereffizient, es verwendet alle Bits eines Bytes. Trotzdem ist der Code relativ einfach.
%Vor%Seien Sie vorsichtig mit Bool-Arrays variabler Länge, der Code unterscheidet nicht zwischen einem Array mit allen Falsen von beispielsweise 6 oder 7 Mitgliedern. Für mehrdimensionale Arrays benötigen Sie etwas Umformung ..
Wenn dies immer noch nicht effizient genug ist und Ihre Arrays groß sind, können Sie den Speicher möglicherweise weiter reduzieren, indem Sie Folgendes packen:
%Vor%Es funktioniert jedoch nicht für zufällige, nicht komprimierbare Daten
Tags und Links python serialization dictionary numpy