RoaringBitmap
1.3.16
Bitsets, auch Bitmaps genannt, werden häufig als schnelle Datenstrukturen verwendet. Leider können sie zu viel Speicher verbrauchen. Zum Ausgleich verwenden wir häufig komprimierte Bitmaps.
Roaring-Bitmaps sind komprimierte Bitmaps, die herkömmliche komprimierte Bitmaps wie WAH, EWAH oder Concise tendenziell übertreffen. In einigen Fällen können brüllende Bitmaps hunderte Male schneller sein und bieten oft eine deutlich bessere Komprimierung. Sie können sogar schneller sein als unkomprimierte Bitmaps.
Roaring-Bitmaps funktionieren in vielen wichtigen Anwendungen gut:
Verwenden Sie nach Möglichkeit Roaring für die Bitmap-Komprimierung. Verwenden Sie keine anderen Bitmap-Komprimierungsmethoden (Wang et al., SIGMOD 2017)
Ein großes Lob dafür, dass Sie etwas geschaffen haben, das meine Software fünfmal schneller laufen lässt (Charles Parker von BigML)
Diese Bibliothek wird verwendet von
Die Bibliothek ist ausgereift und wird seit vielen Jahren in der Produktion eingesetzt.
Die YouTube SQL Engine, Google Procella, verwendet Roaring-Bitmaps für die Indizierung. Apache Lucene verwendet Roaring-Bitmaps, obwohl sie über eine eigene unabhängige Implementierung verfügen. Derivate von Lucene wie Solr und Elastic verwenden ebenfalls Roaring-Bitmaps. Auch andere Plattformen wie Whoosh, Microsoft Visual Studio Team Services (VSTS) und Pilosa verwenden Roaring-Bitmaps mit eigenen Implementierungen. Roaring-Bitmaps finden Sie in InfluxDB, Bleve, Cloud Torrent, Redpanda usw.
Für die Interoperabilität zwischen Implementierungen gibt es eine serialisierte Formatspezifikation. Wir verfügen über interoperable C/C++-, Java- und Go-Implementierungen.
(c) 2013-... die RoaringBitmap-Autoren
Dieser Code ist unter der Apache-Lizenz Version 2.0 (AL2.0) lizenziert.
Mengen sind eine grundlegende Abstraktion in der Software. Sie können auf verschiedene Arten implementiert werden, als Hash-Sets, als Bäume usw. In Datenbanken und Suchmaschinen sind Sets oft ein integraler Bestandteil von Indizes. Beispielsweise müssen wir möglicherweise einen Satz aller Dokumente oder Zeilen (dargestellt durch eine numerische Kennung) verwalten, die eine bestimmte Eigenschaft erfüllen. Neben dem Hinzufügen oder Entfernen von Elementen zur Menge benötigen wir schnelle Funktionen zur Berechnung des Schnittpunkts, der Vereinigung, der Differenz zwischen Mengen usw.
Eine besonders attraktive Strategie zur Implementierung einer Menge von Ganzzahlen ist die Bitmap (auch Bitset oder Bitvektor genannt). Mit n Bits können wir jede Menge darstellen, die aus ganzen Zahlen aus dem Bereich [0,n] besteht: Das i-te Bit wird auf eins gesetzt, wenn die ganze Zahl i in der Menge vorhanden ist. Warenprozessoren verwenden Wörter mit W=32 oder W=64 Bit. Durch die Kombination vieler solcher Wörter können wir große Werte von n unterstützen. Schnittmengen, Vereinigungen und Differenzen können dann als bitweise AND-, OR- und ANDNOT-Operationen implementiert werden. Kompliziertere Mengenfunktionen können auch als bitweise Operationen implementiert werden.
Wenn der Bitset-Ansatz anwendbar ist, kann er um Größenordnungen schneller sein als andere mögliche Implementierungen eines Satzes (z. B. als Hash-Satz) und benötigt gleichzeitig ein Vielfaches weniger Speicher.
Allerdings ist ein Bitsatz, selbst ein komprimierter, nicht immer anwendbar. Wenn Sie beispielsweise über 1000 zufällig aussehende Ganzzahlen verfügen, ist ein einfaches Array möglicherweise die beste Darstellung. Wir bezeichnen diesen Fall als das „sparse“-Szenario.
Ein unkomprimiertes BitSet kann viel Speicher verbrauchen. Wenn Sie beispielsweise ein BitSet nehmen und das Bit an Position 1.000.000 auf „true“ setzen, haben Sie etwas mehr als 100 KB. Das sind über 100 kB, um die Position eines Bits zu speichern. Dies ist selbst dann verschwenderisch, wenn Ihnen der Speicher egal ist: Angenommen, Sie müssen den Schnittpunkt zwischen diesem BitSet und einem anderen BitSet berechnen, das an Position 1.000.001 ein Bit mit „true“ hat, dann müssen Sie alle diese Nullen durchgehen, ob Ihnen das gefällt oder nicht. Das kann sehr verschwenderisch werden.
Allerdings gibt es definitiv Fälle, in denen der Versuch, komprimierte Bitmaps zu verwenden, verschwenderisch ist. Zum Beispiel, wenn Ihr Universum klein ist. Ihre Bitmaps stellen beispielsweise Mengen von ganzen Zahlen aus [0,n) dar, wobei n klein ist (z. B. n=64 oder n=128). Wenn Sie ein unkomprimiertes BitSet verwenden können und es Ihre Speichernutzung nicht in die Höhe treibt, sind komprimierte Bitmaps wahrscheinlich nicht nützlich für Sie. Wenn Sie keine Komprimierung benötigen, bietet ein BitSet tatsächlich eine bemerkenswerte Geschwindigkeit.
Das Sparse-Szenario ist ein weiterer Anwendungsfall, bei dem komprimierte Bitmaps nicht verwendet werden sollten. Bedenken Sie, dass zufällig aussehende Daten normalerweise nicht komprimierbar sind. Wenn Sie beispielsweise über einen kleinen Satz zufälliger 32-Bit-Ganzzahlen verfügen, ist es mathematisch nicht möglich, weit weniger als 32 Bits pro Ganzzahl zu verwenden, und Komprimierungsversuche können kontraproduktiv sein.
Die meisten Alternativen zu Roaring gehören zu einer größeren Familie komprimierter Bitmaps, bei denen es sich um lauflängencodierte Bitmaps handelt. Sie identifizieren lange Folgen von Einsen oder Nullen und stellen sie mit einem Markierungswort dar. Wenn Sie eine lokale Mischung aus Einsen und Nullen haben, verwenden Sie ein unkomprimiertes Wort.
Es gibt viele Formate in dieser Familie:
Allerdings gibt es bei diesen Formaten ein großes Problem, das Ihnen in manchen Fällen schwer schaden kann: Es gibt keinen wahlfreien Zugriff. Wenn Sie prüfen möchten, ob ein bestimmter Wert in der Menge vorhanden ist, müssen Sie von vorne beginnen und das Ganze „entpacken“. Das heißt, wenn man eine große Menge mit einer großen Menge überschneiden möchte, muss man im schlimmsten Fall immer noch die gesamte große Menge dekomprimieren ...
Brüllen löst dieses Problem. Es funktioniert auf folgende Weise. Es unterteilt die Daten in Blöcke von 2 16 Ganzzahlen (z. B. [0, 2 16 ), [2 16 , 2 x 2 16 ), ...). Innerhalb eines Blocks kann eine unkomprimierte Bitmap, eine einfache Liste von Ganzzahlen oder eine Liste von Läufen verwendet werden. Unabhängig davon, welches Format verwendet wird, können Sie mit allen schnell prüfen, ob ein bestimmter Wert vorhanden ist (z. B. mit einer binären Suche). Das Endergebnis ist, dass Roaring viele Operationen viel schneller berechnen kann als lauflängencodierte Formate wie WAH, EWAH, Concise ... Es überrascht vielleicht, dass Roaring im Allgemeinen auch bessere Komprimierungsraten bietet.
import org . roaringbitmap . RoaringBitmap ;
public class Basic {
public static void main ( String [] args ) {
RoaringBitmap rr = RoaringBitmap . bitmapOf ( 1 , 2 , 3 , 1000 );
RoaringBitmap rr2 = new RoaringBitmap ();
rr2 . add ( 4000L , 4255L );
rr . select ( 3 ); // would return the third value or 1000
rr . rank ( 2 ); // would return the rank of 2, which is index 1
rr . contains ( 1000 ); // will return true
rr . contains ( 7 ); // will return false
RoaringBitmap rror = RoaringBitmap . or ( rr , rr2 ); // new bitmap
rr . or ( rr2 ); //in-place computation
boolean equals = rror . equals ( rr ); // true
if (! equals ) throw new RuntimeException ( "bug" );
// number of values stored?
long cardinality = rr . getLongCardinality ();
System . out . println ( cardinality );
// a "forEach" is faster than this loop, but a loop is possible:
for ( int i : rr ) {
System . out . println ( i );
}
}
} Weitere Beispiele finden Sie im Ordner „Beispiele“, die Sie mit ./gradlew :examples:runAll ausführen können, oder ein bestimmtes Beispiel mit ./gradlew :examples:runExampleBitmap64 usw. ausführen können.
http://www.javadoc.io/doc/org.roaringbitmap/RoaringBitmap/
Sie können Veröffentlichungen von Github herunterladen: https://github.com/RoaringBitmap/RoaringBitmap/releases
Fügen Sie Ihrer pom.xml-Datei die folgende Abhängigkeit hinzu...
< dependency >
< groupId >com.github.RoaringBitmap.RoaringBitmap</ groupId >
< artifactId >roaringbitmap</ artifactId >
< version >1.3.16</ version >
</ dependency >Sie können die Versionsnummer anpassen.
Fügen Sie dann das Repository zu Ihrer pom.xml-Datei hinzu:
< repositories >
< repository >
< id >jitpack.io</ id >
< url >https://jitpack.io</ url >
</ repository >
</ repositories >Ein vollständiges Beispiel finden Sie unter https://github.com/RoaringBitmap/JitPackRoaringBitmapProject.
Fügen Sie die folgende Abhängigkeit zu Ihrer pom.xml Datei innerhalb des <dependencies> -Elements hinzu ...
< dependency >
< groupId >org.roaringbitmap</ groupId >
< artifactId >roaringbitmap</ artifactId >
< version >1.3.16</ version >
</ dependency > Fügen Sie das GitHub-Repository innerhalb des <repositories> -Elements ( pom.xml -Datei) hinzu ...
< repositories >
< repository >
< id >github</ id >
< name >Roaring Maven Packages</ name >
< url >https://maven.pkg.github.com/RoaringBitmap/RoaringBitmap</ url >
< releases >< enabled >true</ enabled ></ releases >
< snapshots >< enabled >true</ enabled ></ snapshots >
</ repository >
</ repositories >Ein vollständiges Beispiel finden Sie unter https://github.com/RoaringBitmap/MavenRoaringBitmapProject.
Der Registry-Zugriff ist durch eine Autorisierung geschützt. Sie müssen also Ihre GitHub-Anmeldeinformationen zu Ihrer globalen Settings.xml hinzufügen: $HOME.m2settings.xml .
Sie benötigen einen Token, den Sie auf GitHub generieren können.
GitHub > Settings > Developer Settings > Personal access tokens > Generate new token
Das Token benötigt die Berechtigung read:packages. Die Token-ID ist eine lange Zeichenfolge, z. B. ghp_ieOkN .
Fügen Sie Folgendes in Ihre Datei settings.xml im Element „ <servers> “ ein.
< server >
< id >github</ id >
< username >lemire</ username >
< password >ghp_ieOkN</ password >
</ server > Ersetzen Sie lemire durch Ihren GitHub-Benutzernamen und ghp_ieOkN durch die soeben generierte Token-ID.
Dann müssen Sie nur noch Ihre build.gradle Datei wie folgt bearbeiten:
plugins {
id ' java '
}
group ' org.roaringbitmap ' // name of your project
version ' 1.0-SNAPSHOT ' // version of your project
repositories {
mavenCentral()
maven {
url ' https://jitpack.io '
}
}
dependencies {
implementation ' com.github.RoaringBitmap.RoaringBitmap:roaringbitmap:1.3.16 '
testImplementation ' junit:junit:3.8.1 '
}Ein vollständiges Beispiel finden Sie unter https://github.com/RoaringBitmap/JitPackRoaringBitmapProject.
Sie benötigen zunächst Ihre GitHub-Anmeldeinformationen. Gehe zu
GitHub > Settings > Developer Settings > Personal access tokens > Generate new token
Und erstellen Sie ein Token mit der Berechtigung read:packages.
Wenn Ihr GitHub-Benutzername lemire und Ihr persönliches GitHub-Token ghp_ieOkN ist, können Sie diese mithilfe von Systemvariablen festlegen. Unter Bash können Sie es so machen:
export GITHUB_USER=lemire
export GITHUB_PASSWORD=ghp_ieOkN
Wenn Sie möchten, können Sie Ihre GitHub-Anmeldeinformationen in Ihre gradle.properties-Datei schreiben
# gradle.properties
githubUser=lemire
githubPassword=ghp_ieOkN
Dann müssen Sie nur noch Ihre build.gradle Datei wie folgt bearbeiten:
plugins {
id ' java '
}
group ' org.roaringbitmap ' // name of your project
version ' 1.0-SNAPSHOT ' // version of your project
repositories {
mavenCentral()
maven {
url ' https://maven.pkg.github.com/RoaringBitmap/RoaringBitmap '
credentials {
username = System . properties[ ' githubUser ' ] ?: System . env . GITHUB_USER
password = System . properties[ ' githubPassword ' ] ?: System . env . GITHUB_PASSWORD
}
}
}
dependencies {
implementation ' org.roaringbitmap:roaringbitmap:1.3.16 '
testImplementation ' junit:junit:3.8.1 '
}Ein vollständiges Beispiel finden Sie unter https://github.com/RoaringBitmap/MavenRoaringBitmapProject.
In Java fehlen native Ganzzahlen ohne Vorzeichen, aber Ganzzahlen werden in Roaring immer noch als vorzeichenlos betrachtet und gemäß Integer.compareUnsigned geordnet. Das bedeutet, dass Java die Zahlen wie folgt anordnet: 0, 1, ..., 2147483647, -2147483648, -2147483647, ..., -1. Zur korrekten Interpretation können Sie Integer.toUnsignedLong und Integer.toUnsignedString verwenden.
Wenn Sie möchten, dass Ihre Bitmaps in speicherzugeordneten Dateien liegen, können Sie stattdessen das Paket org.roaringbitmap.buffer verwenden. Es enthält zwei wichtige Klassen, ImmutableRoaringBitmap und MutableRoaringBitmap. MutableRoaringBitmaps werden von ImmutableRoaringBitmap abgeleitet, sodass Sie eine MutableRoaringBitmap in konstanter Zeit in eine ImmutableRoaringBitmap konvertieren (umwandeln) können.
Eine ImmutableRoaringBitmap, die keine Instanz einer MutableRoaringBitmap ist, wird von einem ByteBuffer unterstützt, der einen gewissen Leistungsaufwand mit sich bringt, aber die zusätzliche Flexibilität bietet, dass sich die Daten überall befinden können (auch außerhalb des Java-Heaps).
Manchmal müssen Sie möglicherweise mit Bitmaps arbeiten, die sich auf der Festplatte befinden (Instanzen von ImmutableRoaringBitmap) und mit Bitmaps, die sich im Java-Speicher befinden. Wenn Sie wissen, dass sich die Bitmaps im Java-Speicher befinden, verwenden Sie am besten MutableRoaringBitmap-Instanzen. Sie können nicht nur geändert werden, sondern sind auch schneller. Da MutableRoaringBitmap-Instanzen außerdem auch ImmutableRoaringBitmap-Instanzen sind, können Sie einen Großteil Ihres Codes so schreiben, dass ImmutableRoaringBitmap erwartet wird.
Wenn Sie Ihren Code so schreiben, dass ImmutableRoaringBitmap-Instanzen erwartet werden, ohne zu versuchen, die Instanzen umzuwandeln, sind Ihre Objekte wirklich unveränderlich. Die MutableRoaringBitmap verfügt über eine praktische Methode (toImmutableRoaringBitmap), die eine einfache Rückumwandlung in eine ImmutableRoaringBitmap-Instanz darstellt. Aus Sicht des Sprachdesigns sind Instanzen der ImmutableRoaringBitmap-Klasse nur dann unveränderlich, wenn sie gemäß der Schnittstelle der ImmutableRoaringBitmap-Klasse verwendet werden. Da die Klasse nicht endgültig ist, ist es möglich, Instanzen über andere Schnittstellen zu ändern. Daher verstehen wir den Begriff „unveränderlich“ nicht puristisch, sondern eher praktisch.
Einer unserer Beweggründe für dieses Design, bei dem MutableRoaringBitmap-Instanzen in ImmutableRoaringBitmap-Instanzen umgewandelt werden können, ist, dass Bitmaps oft groß sind oder in einem Kontext verwendet werden, in dem Speicherzuweisungen vermieden werden müssen, sodass wir das Erzwingen von Kopien vermeiden. Kopien sind zu erwarten, wenn ImmutableRoaringBitmap- und MutableRoaringBitmap-Instanzen gemischt und abgeglichen werden müssen.
Das folgende Codebeispiel veranschaulicht, wie eine ImmutableRoaringBitmap aus einem ByteBuffer erstellt wird. In solchen Fällen lädt der Konstruktor nur die Metadaten in den RAM, während auf die eigentlichen Daten bei Bedarf vom ByteBuffer zugegriffen wird.
import org . roaringbitmap . buffer .*;
//...
MutableRoaringBitmap rr1 = MutableRoaringBitmap . bitmapOf ( 1 , 2 , 3 , 1000 );
MutableRoaringBitmap rr2 = MutableRoaringBitmap . bitmapOf ( 2 , 3 , 1010 );
ByteArrayOutputStream bos = new ByteArrayOutputStream ();
DataOutputStream dos = new DataOutputStream ( bos );
// If there were runs of consecutive values, you could
// call rr1.runOptimize(); or rr2.runOptimize(); to improve compression
rr1 . serialize ( dos );
rr2 . serialize ( dos );
dos . close ();
ByteBuffer bb = ByteBuffer . wrap ( bos . toByteArray ());
ImmutableRoaringBitmap rrback1 = new ImmutableRoaringBitmap ( bb );
bb . position ( bb . position () + rrback1 . serializedSizeInBytes ());
ImmutableRoaringBitmap rrback2 = new ImmutableRoaringBitmap ( bb ); Alternativ können wir mit der Methode serialize(ByteBuffer) direkt in einen ByteBuffer serialisieren.
Operationen an einer ImmutableRoaringBitmap wie and oder xor, flip generieren eine RoaringBitmap, die im RAM liegt. Wie der Name schon sagt, kann die ImmutableRoaringBitmap selbst nicht geändert werden.
Dieses Design wurde von Apache Druid inspiriert.
Ein vollständiges Arbeitsbeispiel finden Sie in der Testdatei TestMemoryMapping.java.
Beachten Sie, dass Sie die Klassen aus dem Paket org.roaringbitmap nicht mit den Klassen aus dem Paket org.roaringbitmap.buffer mischen sollten. Sie sind nicht kompatibel. Sie serialisieren jedoch zur gleichen Ausgabe. Die Leistung des Codes im Paket org.roaringbitmap ist im Allgemeinen überlegen, da durch die Verwendung von ByteBuffer-Instanzen kein Overhead entsteht.
Im Allgemeinen ist es unsicher, über verschiedene Threads auf dieselben Bitmaps zuzugreifen – die Bitmaps sind aus Leistungsgründen nicht synchronisiert. Wenn Sie von mehr als einem Thread aus auf eine Bitmap zugreifen möchten, sollten Sie eine Synchronisierung bereitstellen. Sie können jedoch von mehreren Threads aus auf eine unveränderliche Bitmap zugreifen, solange Sie sich an die ImmutableBitmapDataProvider -Schnittstelle halten.
Viele Anwendungen nutzen Kryo zur Serialisierung/Deserialisierung. Dank eines benutzerdefinierten Serialisierers (Kryo 5) können Roaring-Bitmaps mit Kryo effizient verwendet werden:
public class RoaringSerializer extends Serializer < RoaringBitmap > {
@ Override
public void write ( Kryo kryo , Output output , RoaringBitmap bitmap ) {
try {
bitmap . serialize ( new KryoDataOutput ( output ));
} catch ( IOException e ) {
e . printStackTrace ();
throw new RuntimeException ();
}
}
@ Override
public RoaringBitmap read ( Kryo kryo , Input input , Class <? extends RoaringBitmap > type ) {
RoaringBitmap bitmap = new RoaringBitmap ();
try {
bitmap . deserialize ( new KryoDataInput ( input ));
} catch ( IOException e ) {
e . printStackTrace ();
throw new RuntimeException ();
}
return bitmap ;
}
} Obwohl Roaring Bitmaps für den 32-Bit-Fall entwickelt wurden, gibt es Erweiterungen für 64-Bit-Ganzzahlen. Zu diesem Zweck bieten wir zwei Klassen an: Roaring64NavigableMap und Roaring64Bitmap .
Die Roaring64NavigableMap basiert auf einem herkömmlichen Rot-Schwarz-Baum. Die Schlüssel sind 32-Bit-Ganzzahlen, die die höchstwertigen 32-Bit-Elemente darstellen, während die Werte des Baums 32-Bit-Roaring-Bitmaps sind. Die 32-Bit-Roaring-Bitmaps stellen die niedrigstwertigen Bits einer Reihe von Elementen dar.
Der neuere Roaring64Bitmap -Ansatz basiert auf der ART-Datenstruktur, um das Schlüssel/Wert-Paar zu speichern. Der Schlüssel besteht aus den höchstwertigen 48-Bit-Elementen, während die Werte 16-Bit-Roaring-Container sind. Es ist inspiriert von The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases von Leis et al. (ICDE '13).
import org . roaringbitmap . longlong .*;
// first Roaring64NavigableMap
LongBitmapDataProvider r = Roaring64NavigableMap . bitmapOf ( 1 , 2 , 100 , 1000 );
r . addLong ( 1234 );
System . out . println ( r . contains ( 1 )); // true
System . out . println ( r . contains ( 3 )); // false
LongIterator i = r . getLongIterator ();
while ( i . hasNext ()) System . out . println ( i . next ());
// second Roaring64Bitmap
bitmap1 = new Roaring64Bitmap ();
bitmap2 = new Roaring64Bitmap ();
int k = 1 << 16 ;
long i = Long . MAX_VALUE / 2 ;
long base = i ;
for (; i < base + 10000 ; ++ i ) {
bitmap1 . add ( i * k );
bitmap2 . add ( i * k );
}
b1 . and ( bitmap2 );Die Serialisierung von 64-Bit-Roaring-Bitmaps ist angegeben: siehe https://github.com/RoaringBitmap/RoaringFormatSpec#extention-for-64-bit-implementations
Es wird jedoch nur von Roaring64NavigableMap implementiert, indem Folgendes geändert wird:
Roaring64NavigableMap.SERIALIZATION_MODE = Roaring64NavigableMap.SERIALIZATION_MODE_PORTABLE
RangeBitmap ist eine prägnante Datenstruktur, die Bereichsabfragen unterstützt. Jeder zur Bitmap hinzugefügte Wert ist mit einem inkrementellen Bezeichner verknüpft, und Abfragen erzeugen eine RoaringBitmap der Bezeichner, die mit Werten verknüpft sind, die die Abfrage erfüllen. Jeder zur Bitmap hinzugefügte Wert wird separat gespeichert. Wenn also ein Wert zweimal hinzugefügt wird, wird er zweimal gespeichert. Wenn dieser Wert unter einem bestimmten Schwellenwert liegt, enthält die resultierende RoaringBitmap mindestens zwei Ganzzahlen.
Es ist sowohl zeitlich als auch räumlich effizienter, einen maximalen Mehrwert zu bieten. Wenn Sie den Maximalwert nicht kennen, geben Sie einen Long.MAX_VALUE an. Die nicht signierte Reihenfolge wird wie an anderen Stellen in der Bibliothek verwendet.
var appender = RangeBitmap . appender ( 1_000_000 );
appender . add ( 1L );
appender . add ( 1L );
appender . add ( 100_000L );
RangeBitmap bitmap = appender . build ();
RoaringBitmap lessThan5 = bitmap . lt ( 5 ); // {0,1}
RoaringBitmap greaterThanOrEqualTo1 = bitmap . gte ( 1 ); // {0, 1, 2}
RoaringBitmap greaterThan1 = bitmap . gt ( 1 ); // {2}
RoaringBitmap equalTo1 = bitmap . eq ( 1 ); // {0, 1}
RoaringBitmap notEqualTo1 = bitmap . neq ( 1 ); // {2} RangeBitmap kann auf die Festplatte geschrieben und dem Speicher zugeordnet werden:
var appender = RangeBitmap . appender ( 1_000_000 );
appender . add ( 1L );
appender . add ( 1L );
appender . add ( 100_000L );
ByteBuffer buffer = mapBuffer ( appender . serializedSizeInBytes ());
appender . serialize ( buffer );
RangeBitmap bitmap = RangeBitmap . map ( buffer );Das Serialisierungsformat verwendet die Little-Endian-Bytereihenfolge.
Holen Sie sich Java
./gradlew assemble wird kompiliert
./gradlew build kompiliert die Komponententests und führt sie aus
./gradlew test führt die Tests aus
./gradlew :roaringbitmap:test --tests TestIterators.testIndexIterator4 führt nur den Test aus TestIterators.testIndexIterator4 ; ./gradlew -i :roaringbitmap:test --tests TestRoaringBitmap.issue623 führt beim Ausdrucken auf der Konsole nur den Test issue623 in der Klasse TestRoaringBitmap aus.
./gradlew bsi:test --tests BufferBSITest.testEQ führt nur den Test BufferBSITest.testEQ im bsi Submodul aus
Wenn Sie vorhaben, zu RoaringBitmap beizutragen, können Sie es in Ihre bevorzugte IDE laden.
Beiträge sind erwünscht. Wir verwenden den Google Java-Stil (siehe roaring_google_checks.xml ). Es kann mit ./gradlew spotlessApply automatisch auf Ihren Code angewendet werden
Bitte formatieren Sie den Code nicht unnötig neu (insbesondere bei Kommentaren/Javadoc).
In den serialisierten Dateien ist ein Teil der ersten 4 Bytes einem „Cookie“ zugeordnet, das zur Angabe des Dateiformats dient.
Wenn Sie versuchen, eine Bitmap aus Daten zu deserialisieren oder zuzuordnen, die ein nicht erkanntes „Cookie“ enthalten, bricht der Code den Vorgang ab und meldet einen Fehler.
Dieses Problem tritt bei allen Benutzern auf, die Roaring-Bitmaps mit Versionen vor 0.4.x serialisiert haben, wenn sie auf Version 0.4.x oder höher aktualisieren. Diese Benutzer müssen ihre serialisierten Bitmaps aktualisieren.
Bei N ganzen Zahlen in [0,x) sollte die serialisierte Größe in Bytes einer Roaring-Bitmap diese Grenze niemals überschreiten:
8 + 9 * ((long)x+65535)/65536 + 2 * N
Das heißt, bei einem festen Overhead für die Universumsgröße (x) verwenden Roaring-Bitmaps nie mehr als 2 Bytes pro Ganzzahl. Für eine genauere Schätzung können Sie RoaringBitmap.maximumSerializedSize aufrufen.
Es gibt keine Datenstruktur, die immer ideal ist. Sie sollten sicherstellen, dass Roaring-Bitmaps zu Ihrem Anwendungsprofil passen. Es gibt mindestens zwei Fälle, in denen Roaring-Bitmaps hinsichtlich der Komprimierung leicht durch überlegene Alternativen ersetzt werden können:
Sie haben wenige Zufallswerte, die sich über ein großes Intervall erstrecken (dh Sie haben eine sehr spärliche Menge). Nehmen Sie zum Beispiel die Menge 0, 65536, 131072, 196608, 262144 ... Wenn dies für Ihre Anwendung typisch ist, können Sie die Verwendung eines HashSet oder eines einfachen sortierten Arrays in Betracht ziehen.
Sie verfügen über eine dichte Menge zufälliger Werte, die niemals Reihen kontinuierlicher Werte bilden. Betrachten Sie beispielsweise die Menge 0,2,4,...,10000. Wenn dies typisch für Ihre Anwendung ist, ist ein herkömmlicher Bitsatz (z. B. die BitSet-Klasse von Java) möglicherweise besser für Sie geeignet.
Wie wähle ich ein Element zufällig aus?
Random random = new Random();
bitmap.select(random.nextInt(bitmap.getCardinality()));
Um JMH-Benchmarks auszuführen, verwenden Sie die folgenden Befehle:
$ ./gradlew jmh::shadowJar
$ java -jar jmh/build/libs/benchmarks.jar
Sie können auch einen bestimmten Benchmark ausführen:
$ java -jar jmh/build/libs/benchmarks.jar 'org.roaringbitmap.aggregation.and.identical.*'
Wenn Sie eine Bash-Shell haben, können Sie auch unser Skript ausführen, das automatisch bestimmte Tests erstellt und ausführt ...
$ ./jmh/run.sh 'org.roaringbitmap.aggregation.and.identical.*'
https://groups.google.com/forum/#!forum/roaringbitmaps
Diese Arbeit wurde durch die NSERC-Zuschussnummer 26143 unterstützt.
