RoaringBitmap
1.3.16
Les bitsets, également appelés bitmaps, sont couramment utilisés comme structures de données rapides. Malheureusement, ils peuvent utiliser trop de mémoire. Pour compenser, nous utilisons souvent des bitmaps compressés.
Les bitmaps rugissants sont des bitmaps compressés qui ont tendance à surpasser les bitmaps compressés conventionnels tels que WAH, EWAH ou Concise. Dans certains cas, les bitmaps rugissants peuvent être des centaines de fois plus rapides et offrent souvent une compression bien meilleure. Ils peuvent même être plus rapides que les bitmaps non compressés.
Les bitmaps rugissants fonctionnent bien dans de nombreuses applications importantes :
Utilisez Roaring pour la compression bitmap autant que possible. N'utilisez pas d'autres méthodes de compression bitmap (Wang et al., SIGMOD 2017)
félicitations pour avoir créé quelque chose qui permet à mon logiciel de fonctionner 5 fois plus rapidement (Charles Parker de BigML)
Cette bibliothèque est utilisée par
La bibliothèque est mature et est utilisée en production depuis de nombreuses années.
Le moteur SQL YouTube, Google Procella, utilise des bitmaps Roaring pour l'indexation. Apache Lucene utilise des bitmaps Roaring, bien qu'ils aient leur propre implémentation indépendante. Les dérivés de Lucene tels que Solr et Elastic utilisent également des bitmaps Roaring. D'autres plates-formes telles que Whoosh, Microsoft Visual Studio Team Services (VSTS) et Pilosa utilisent également les bitmaps Roaring avec leurs propres implémentations. Vous trouvez des bitmaps Roaring dans InfluxDB, Bleve, Cloud Torrent, Redpanda, etc.
Il existe une spécification de format sérialisé pour l'interopérabilité entre les implémentations. Nous avons des implémentations interopérables C/C++, Java et Go.
(c) 2013-... les auteurs de RoaringBitmap
Ce code est sous licence Apache, version 2.0 (AL2.0).
Les ensembles sont une abstraction fondamentale dans les logiciels. Ils peuvent être implémentés de différentes manières, sous forme de jeux de hachage, d'arbres, etc. Dans les bases de données et les moteurs de recherche, les ensembles font souvent partie intégrante des index. Par exemple, nous devrons peut-être conserver un ensemble de tous les documents ou lignes (représentés par un identifiant numérique) qui satisfont à certaines propriétés. Outre l'ajout ou la suppression d'éléments de l'ensemble, nous avons besoin de fonctions rapides pour calculer l'intersection, l'union, la différence entre les ensembles, etc.
Pour implémenter un ensemble d'entiers, une stratégie particulièrement intéressante est le bitmap (également appelé bitset ou bit vector). En utilisant n bits, nous pouvons représenter n'importe quel ensemble composé d'entiers de la plage [0,n) : le ième bit est mis à un si l'entier i est présent dans l'ensemble. Les processeurs de produits utilisent des mots de W=32 ou W=64 bits. En combinant plusieurs de ces mots, nous pouvons prendre en charge de grandes valeurs de n. Les intersections, les unions et les différences peuvent ensuite être implémentées sous la forme d'opérations AND, OR et ANDNOT au niveau du bit. Des fonctions d'ensemble plus compliquées peuvent également être implémentées sous forme d'opérations au niveau du bit.
Lorsque l'approche du jeu de bits est applicable, elle peut être plusieurs fois plus rapide que toute autre implémentation possible d'un ensemble (par exemple, sous la forme d'un ensemble de hachage) tout en utilisant plusieurs fois moins de mémoire.
Cependant, un jeu de bits, même compressé, n'est pas toujours applicable. Par exemple, si vous disposez de 1 000 entiers aléatoires, un simple tableau pourrait être la meilleure représentation. Nous appelons ce cas le scénario « clairsemé ».
Un BitSet non compressé peut utiliser beaucoup de mémoire. Par exemple, si vous prenez un BitSet et définissez le bit en position 1 000 000 sur vrai et que vous disposez d'un peu plus de 100 Ko. Cela représente plus de 100 Ko pour stocker la position d'un bit. C'est du gaspillage même si vous ne vous souciez pas de la mémoire : supposons que vous ayez besoin de calculer l'intersection entre ce BitSet et un autre qui a un bit en position 1 000 001 à vrai, alors vous devez passer par tous ces zéros, que cela vous plaise ou non. Cela peut devenir très inutile.
Cela étant dit, il existe définitivement des cas où tenter d'utiliser des bitmaps compressés est un gaspillage. Par exemple, si vous avez un univers de petite taille. Par exemple, vos bitmaps représentent des ensembles d'entiers à partir de [0,n) où n est petit (par exemple, n=64 ou n=128). Si vous pouvez utiliser un BitSet non compressé et que cela n'explose pas votre utilisation de la mémoire, alors les bitmaps compressés ne vous sont probablement pas utiles. En fait, si vous n'avez pas besoin de compression, un BitSet offre une vitesse remarquable.
Le scénario clairsemé est un autre cas d’utilisation dans lequel les bitmaps compressés ne doivent pas être utilisés. Gardez à l’esprit que les données aléatoires ne sont généralement pas compressibles. Par exemple, si vous disposez d'un petit ensemble d'entiers aléatoires de 32 bits, il n'est pas mathématiquement possible d'utiliser bien moins de 32 bits par entier, et les tentatives de compression peuvent être contre-productives.
La plupart des alternatives à Roaring font partie d'une famille plus large de bitmaps compressés qui sont des bitmaps codés en longueur. Ils identifient les longues séries de 1 ou de 0 et les représentent avec un mot marqueur. Si vous avez un mélange local de 1 et de 0, vous utilisez un mot non compressé.
Il existe de nombreux formats dans cette famille :
Il y a un gros problème avec ces formats cependant qui peut vous faire très mal dans certains cas : il n'y a pas d'accès aléatoire. Si vous souhaitez vérifier si une valeur donnée est présente dans l'ensemble, vous devez recommencer depuis le début et "décompresser" le tout. Cela signifie que si vous voulez croiser un grand ensemble avec un grand ensemble, vous devez toujours décompresser l'ensemble du grand ensemble dans le pire des cas...
Le rugissement résout ce problème. Cela fonctionne de la manière suivante. Il divise les données en morceaux de 2 16 entiers (par exemple, [0, 2 16 ), [2 16 , 2 x 2 16 ), ...). Au sein d'un morceau, il peut utiliser un bitmap non compressé, une simple liste d'entiers ou une liste d'exécutions. Quel que soit le format utilisé, ils vous permettent tous de vérifier rapidement la présence d'une valeur (par exemple, avec une recherche binaire). Le résultat net est que Roaring peut calculer de nombreuses opérations beaucoup plus rapidement que les formats codés en longueur comme WAH, EWAH, Concise... Peut-être de manière surprenante, Roaring offre également généralement de meilleurs taux de compression.
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 );
}
}
} Veuillez consulter le dossier d'exemples pour plus d'exemples, que vous pouvez exécuter avec ./gradlew :examples:runAll , ou en exécuter un spécifique avec ./gradlew :examples:runExampleBitmap64 , etc.
http://www.javadoc.io/doc/org.roaringbitmap/RoaringBitmap/
Vous pouvez télécharger les versions depuis github : https://github.com/RoaringBitmap/RoaringBitmap/releases
Ajoutez la dépendance suivante à votre fichier pom.xml...
< dependency >
< groupId >com.github.RoaringBitmap.RoaringBitmap</ groupId >
< artifactId >roaringbitmap</ artifactId >
< version >1.3.16</ version >
</ dependency >Vous pouvez ajuster le numéro de version.
Ajoutez ensuite le référentiel à votre fichier pom.xml :
< repositories >
< repository >
< id >jitpack.io</ id >
< url >https://jitpack.io</ url >
</ repository >
</ repositories >Voir https://github.com/RoaringBitmap/JitPackRoaringBitmapProject pour un exemple complet.
Ajoutez la dépendance suivante à votre fichier pom.xml dans l'élément <dependencies> ...
< dependency >
< groupId >org.roaringbitmap</ groupId >
< artifactId >roaringbitmap</ artifactId >
< version >1.3.16</ version >
</ dependency > Ajoutez le référentiel GitHub dans l'élément <repositories> (fichier pom.xml )...
< 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 >Voir https://github.com/RoaringBitmap/MavenRoaringBitmapProject pour un exemple complet.
L'accès au registre est protégé par une autorisation. Vous devez donc ajouter vos informations d'identification GitHub à votre settings.xml global : $HOME.m2settings.xml .
Vous aurez besoin d'un jeton que vous pourrez générer sur GitHub.
GitHub > Settings > Developer Settings > Personal access tokens > Generate new token
Le jeton nécessite l’autorisation read:packages. L'identifiant du jeton est une longue chaîne telle que ghp_ieOkN .
Mettez ce qui suit dans votre fichier settings.xml , dans l'élément <servers> .
< server >
< id >github</ id >
< username >lemire</ username >
< password >ghp_ieOkN</ password >
</ server > Remplacez lemire par votre nom d'utilisateur GitHub et ghp_ieOkN par l'identifiant du token que vous venez de générer.
Ensuite, tout ce dont vous avez besoin est d'éditer votre fichier build.gradle comme ceci :
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 '
}Voir https://github.com/RoaringBitmap/JitPackRoaringBitmapProject pour un exemple complet.
Vous avez d'abord besoin de vos informations d'identification GitHub. Aller à
GitHub > Settings > Developer Settings > Personal access tokens > Generate new token
Et créez un jeton avec l’autorisation read:packages.
Si votre nom d'utilisateur GitHub est lemire et votre jeton personnel GitHub ghp_ieOkN , vous pouvez les définir à l'aide de variables système. Sous bash, vous pouvez procéder comme ceci :
export GITHUB_USER=lemire
export GITHUB_PASSWORD=ghp_ieOkN
Si vous préférez, vous pouvez écrire vos informations d'identification GitHub dans votre fichier gradle.properties
# gradle.properties
githubUser=lemire
githubPassword=ghp_ieOkN
Ensuite, tout ce dont vous avez besoin est d'éditer votre fichier build.gradle comme ceci :
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 '
}Voir https://github.com/RoaringBitmap/MavenRoaringBitmapProject pour un exemple complet.
Java ne dispose pas d'entiers natifs non signés, mais les entiers sont toujours considérés comme non signés dans Roaring et classés selon Integer.compareUnsigned . Cela signifie que Java ordonnera les nombres comme suit : 0, 1, ..., 2147483647, -2147483648, -2147483647,..., -1. Pour interpréter correctement, vous pouvez utiliser Integer.toUnsignedLong et Integer.toUnsignedString .
Si vous souhaitez que vos bitmaps se trouvent dans des fichiers mappés en mémoire, vous pouvez utiliser le package org.roaringbitmap.buffer à la place. Il contient deux classes importantes, ImmutableRoaringBitmap et MutableRoaringBitmap. Les MutableRoaringBitmaps sont dérivés d'ImmutableRoaringBitmap, afin que vous puissiez convertir (caster) un MutableRoaringBitmap en ImmutableRoaringBitmap en temps constant.
Un ImmutableRoaringBitmap qui n'est pas une instance de MutableRoaringBitmap est soutenu par un ByteBuffer qui entraîne une certaine surcharge de performances, mais avec la flexibilité supplémentaire que les données peuvent résider n'importe où (y compris en dehors du tas Java).
Parfois, vous devrez peut-être travailler avec des bitmaps résidant sur le disque (instances de ImmutableRoaringBitmap) et des bitmaps résidant dans la mémoire Java. Si vous savez que les bitmaps résideront dans la mémoire Java, il est préférable d'utiliser des instances MutableRoaringBitmap, non seulement elles pourront être modifiées, mais elles seront également plus rapides. De plus, comme les instances MutableRoaringBitmap sont également des instances ImmutableRoaringBitmap, vous pouvez écrire une grande partie de votre code en attendant ImmutableRoaringBitmap.
Si vous écrivez votre code en attendant des instances ImmutableRoaringBitmap, sans tenter de convertir les instances, alors vos objets seront véritablement immuables. Le MutableRoaringBitmap a une méthode pratique (toImmutableRoaringBitmap) qui est un simple retour vers une instance ImmutableRoaringBitmap. Du point de vue de la conception du langage, les instances de la classe ImmutableRoaringBitmap ne sont immuables que lorsqu'elles sont utilisées conformément à l'interface de la classe ImmutableRoaringBitmap. Etant donné que la classe n'est pas définitive, il est possible de modifier les instances, via d'autres interfaces. Nous n’acceptons donc pas le terme « immuable » dans un sens puriste, mais plutôt dans un sens pratique.
L'une de nos motivations pour cette conception où les instances MutableRoaringBitmap peuvent être converties en instances ImmutableRoaringBitmap est que les bitmaps sont souvent volumineux ou utilisés dans un contexte où les allocations de mémoire doivent être évitées, nous évitons donc de forcer les copies. Des copies pourraient être attendues si l'on doit mélanger et faire correspondre les instances ImmutableRoaringBitmap et MutableRoaringBitmap.
L'exemple de code suivant illustre comment créer un ImmutableRoaringBitmap à partir d'un ByteBuffer. Dans de tels cas, le constructeur charge uniquement les métadonnées dans la RAM tandis que les données réelles sont accessibles à la demande depuis le ByteBuffer.
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 ); Alternativement, nous pouvons sérialiser directement vers un ByteBuffer avec la méthode serialize(ByteBuffer) .
Les opérations sur un ImmutableRoaringBitmap telles que et, ou, xor, flip, généreront un RoaringBitmap qui se trouve dans la RAM. Comme son nom l'indique, l'ImmutableRoaringBitmap lui-même ne peut pas être modifié.
Cette conception a été inspirée par Apache Druid.
On peut trouver un exemple de travail complet dans le fichier de test TestMemoryMapping.java.
Notez que vous ne devez pas mélanger les classes du package org.roaringbitmap avec les classes du package org.roaringbitmap.buffer. Ils sont incompatibles. Cependant, ils sérialisent sur la même sortie. Les performances du code du package org.roaringbitmap sont généralement supérieures car il n'y a pas de surcharge due à l'utilisation d'instances ByteBuffer.
En général, il n'est pas sûr d'accéder aux mêmes bitmaps à l'aide de threads différents : les bitmaps ne sont pas synchronisés pour des raisons de performances. Si vous souhaitez accéder à un Bitmap à partir de plusieurs threads, vous devez fournir une synchronisation. Cependant, vous pouvez accéder à un bitmap immuable à partir de plusieurs threads, à condition de respecter l'interface ImmutableBitmapDataProvider .
De nombreuses applications utilisent Kryo pour la sérialisation/désérialisation. On peut utiliser efficacement les bitmaps Roaring avec Kryo grâce à un sérialiseur personnalisé (Kryo 5) :
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 ;
}
} Bien que les Roaring Bitmaps aient été conçus en pensant au cas 32 bits, nous avons des extensions pour les entiers 64 bits. Nous proposons deux classes à cet effet : Roaring64NavigableMap et Roaring64Bitmap .
Le Roaring64NavigableMap s'appuie sur un arbre rouge-noir conventionnel. Les clés sont des entiers de 32 bits représentant les 32 bits les plus significatifs des éléments tandis que les valeurs de l'arborescence sont des bitmaps Roaring de 32 bits. Les bitmaps Roaring 32 bits représentent les bits les moins significatifs d'un ensemble d'éléments.
La nouvelle approche Roaring64Bitmap s'appuie sur la structure de données ART pour contenir la paire clé/valeur. La clé est constituée des 48 bits d'éléments les plus significatifs tandis que les valeurs sont des conteneurs Roaring de 16 bits. Il s'inspire de The Adaptive Radix Tree: ARTful Indexing for Main-Memory Database de 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 );La sérialisation des bitmaps Roaring 64 bits est spécifiée : voir https://github.com/RoaringBitmap/RoaringFormatSpec#extention-for-64-bit-implementations
Cependant, il n'est implémenté que par Roaring64NavigableMap , en commutant :
Roaring64NavigableMap.SERIALIZATION_MODE = Roaring64NavigableMap.SERIALIZATION_MODE_PORTABLE
RangeBitmap est une structure de données succincte prenant en charge les requêtes de plage. Chaque valeur ajoutée au bitmap est associée à un identifiant incrémentiel, et les requêtes produisent un RoaringBitmap des identifiants associés aux valeurs qui satisfont la requête. Chaque valeur ajoutée au bitmap est stockée séparément, de sorte que si une valeur est ajoutée deux fois, elle sera stockée deux fois, et si cette valeur est inférieure à un certain seuil, il y aura au moins deux entiers dans le RoaringBitmap résultant.
Il est plus efficace – en termes de temps et d’espace – de fournir une valeur maximale. Si vous ne connaissez pas la valeur maximale, fournissez un Long.MAX_VALUE . La commande non signée est utilisée comme ailleurs dans la bibliothèque.
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 peut être écrit sur le disque et la mémoire mappée :
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 );Le format de sérialisation utilise l'ordre des octets petit-boutiste.
Obtenir Java
./gradlew assemble va compiler
./gradlew build compilera et exécutera les tests unitaires
./gradlew test exécutera les tests
./gradlew :roaringbitmap:test --tests TestIterators.testIndexIterator4 exécute uniquement le test TestIterators.testIndexIterator4 ; ./gradlew -i :roaringbitmap:test --tests TestRoaringBitmap.issue623 exécute uniquement le test issue623 dans la classe TestRoaringBitmap lors de l'impression sur la console.
./gradlew bsi:test --tests BufferBSITest.testEQ exécute uniquement le test BufferBSITest.testEQ dans le sous-module bsi
Si vous envisagez de contribuer à RoaringBitmap, vous pouvez le charger dans votre IDE préféré.
Les contributions sont sollicitées. Nous utilisons le style Google Java (voir roaring_google_checks.xml ). Il peut être appliqué automatiquement à votre code avec ./gradlew spotlessApply
Merci de ne pas reformater le code inutilement (surtout sur les commentaires/javadoc).
Dans les fichiers sérialisés, une partie des 4 premiers octets est dédiée à un « cookie » qui sert à indiquer le format du fichier.
Si vous essayez de désérialiser ou de mapper un bitmap à partir de données contenant un « cookie » non reconnu, le code annulera le processus et signalera une erreur.
Ce problème se produira avec tous les utilisateurs qui ont sérialisé des bitmaps Roaring à l'aide de versions antérieures à 0.4.x lors de la mise à niveau vers la version 0.4.x ou supérieure. Ces utilisateurs doivent actualiser leurs bitmaps sérialisés.
Étant donné N entiers dans [0,x), alors la taille sérialisée en octets d'un bitmap Roaring ne doit jamais dépasser cette limite :
8 + 9 * ((long)x+65535)/65536 + 2 * N
Autrement dit, étant donné une surcharge fixe pour la taille de l'univers (x), les bitmaps Roaring n'utilisent jamais plus de 2 octets par entier. Vous pouvez appeler RoaringBitmap.maximumSerializedSize pour une estimation plus précise.
Il n’existe pas de structure de données toujours idéale. Vous devez vous assurer que les bitmaps Roaring correspondent à votre profil d'application. Il existe au moins deux cas dans lesquels les bitmaps Roaring peuvent être facilement remplacés par des alternatives supérieures en termes de compression :
Vous avez peu de valeurs aléatoires s'étendant sur un grand intervalle (c'est-à-dire que vous avez un ensemble très clairsemé). Par exemple, prenons l'ensemble 0, 65536, 131072, 196608, 262144... Si cela est typique de votre application, vous pouvez envisager d'utiliser un HashSet ou un simple tableau trié.
Vous disposez d’un ensemble dense de valeurs aléatoires qui ne forment jamais des séries de valeurs continues. Par exemple, considérons l'ensemble 0,2,4,...,10000. Si cela est typique de votre application, vous pourriez être mieux servi avec un jeu de bits conventionnel (par exemple, la classe BitSet de Java).
Comment sélectionner un élément au hasard ?
Random random = new Random();
bitmap.select(random.nextInt(bitmap.getCardinality()));
Pour exécuter des benchmarks JMH, utilisez les commandes suivantes :
$ ./gradlew jmh::shadowJar
$ java -jar jmh/build/libs/benchmarks.jar
Vous pouvez également exécuter un benchmark spécifique :
$ java -jar jmh/build/libs/benchmarks.jar 'org.roaringbitmap.aggregation.and.identical.*'
Si vous disposez d'un shell bash, vous pouvez également exécuter notre script qui construit et exécute automatiquement des tests spécifiques...
$ ./jmh/run.sh 'org.roaringbitmap.aggregation.and.identical.*'
https://groups.google.com/forum/#!forum/roaringbitmaps
Ce travail a été soutenu par la subvention numéro 26143 du CRSNG.
