java: spärlicher Bit-Vektor

Question

Gibt es bekannte Bibliotheken in Java für spärliche Bitvektoren?

(Und gibt es Leitlinien dafür, wie spärlich sie im Vergleich zu verwenden sind. java.util.BitSet ?)

Answer 1

Wenn es wirklich spärlich ist (z. B. weniger als 1 % Ladung), dann ist die Verwendung einer Hash-Tabelle, die durch einen Bit-Index indiziert ist, wahrscheinlich ziemlich gut; das bloße Vorhandensein oder Fehlen des Index in der Tabelle ist alles, was Sie brauchen, um zu wissen, ob das Bit eins bzw. null ist.

Wenn die Dichte ein paar Prozent übersteigt, können Sie eine Hash-Tabelle verwenden, die durch den Bit-Index geteilt durch 64 indiziert ist, und Folgendes speichern lang Wörter in der Hashtabelle, die tatsächliche Bits enthalten. Bit N ist gesetzt, wenn die Hash-Tabelle den Wert V para int(N/64) y (V>>(N mod 64))&1 wahr ist.

Beide Antworten gehen davon aus, dass Sie den zufälligen Zugriff auf Bits optimieren wollen. Wenn Sie den sequentiellen (oder anderen) Zugriff auf Bits nach Index optimieren wollen, dann möchten Sie vielleicht eine dünnbesetzte Matrixstruktur, die dieselbe Art von Low-Level-Bitvektor-Darstellung verwendet, je nach erwarteter Dichte. Siehe Spärliche Matrizen

Answer 2

Les Colt-Bibliothek hat spärliche Matrizen (1D, 2D und 3D). Außerdem verfügt es über einen effizienten BitVektor mit 1 Bit pro Wert, anstatt 8 Bits wie boolean[] tut.

Die spärlichen Matrizen unterstützen jedoch keine Bits direkt, sondern nur Doubles und Objekte. Sie könnten die 1D-Sparse-Double-Matrix einpacken, indem Sie Bit-Indizes auf Long-Indizes abbilden (bitIndex>>6) da jeder Long 64 Bits enthält, konvertieren den abgerufenen Double-Wert in einen rohen Long-Wert um, und verwenden Sie Bitmanipulation, um auf die Bits des abgerufenen Long-Wertes zuzugreifen. Ein wenig Arbeit, aber bei weitem nicht so viel wie die Implementierung des Sparse-Vektors selbst. Sobald Ihr Wrapper funktioniert, können Sie die Umwandlung von Doubles in Longs vermeiden und eine echte sparse long 1d-Matrix implementieren, indem Sie den verfügbaren Colt-Quellcode für die double 1D sparse matrix als Ausgangspunkt verwenden.

EDIT: Weitere Informationen. Die Colt-Vektoren/Matrizen benötigen anfangs keinen Speicher für die Speicherung, vorausgesetzt, alle Bits (Longs) sind anfangs 0. Das Setzen eines Wertes auf ungleich Null verbraucht Speicher. Wenn der Wert wieder auf 0 gesetzt wird, wird weiterhin Speicher verbraucht, obwohl der Speicher für Nullwerte regelmäßig zurückgewonnen wird.

Wenn die Bits wirklich spärlich sind, so dass für jeden zurückliegenden langen Wert nur ein Bit gesetzt ist, dann ist der Speicheraufwand sehr gering und erfordert 64 Bits pro tatsächlich gespeichertem Bit. Aber wie Sie erwähnen typischen Fall ist 20-40% spärlich, dann wird der Overhead viel niedriger sein, mit möglicherweise keine verschwendeten Speicherplatz, wenn Bits in Bereichen, z. B. Bits von 0-100, dann 1000-1100 und 2000-2200 (Werte in hex.) Insgesamt nur 1/16 der Region Bits zugeordnet ist, aber die Clusterung bedeutet, dass die Bits ohne verschwendeten Platz gespeichert werden.

Answer 3

Sie könnten versuchen FastUtils AVL-Baumkarte .

Answer 4

CERN COLT wird häufig für Vektor- und Matrixberechnungen verwendet und verfügt über dünn besetzte Matrizen, wird aber nicht speziell für Bitvektoren verwendet.

http://acs.lbl.gov/software/colt/api/cern/colt/matrix/impl/SparseObjectMatrix1D.html

Answer 5

Eine Hashtabelle, bei der das bloße Vorhandensein oder Nichtvorhandensein eines Schlüssels etwas aussagt? Das wäre dann ein Hash-Set! Ich bin skeptisch, was die Leistung eines Sets (selbst eines Hash-Sets) gegenüber einem BitSet angeht. Es hängt wirklich davon ab, ob Geschwindigkeit oder Speicher der primäre Treiber ist.