RoaringBitmap
1.3.16
Bitset, juga disebut bitmap, biasanya digunakan sebagai struktur data cepat. Sayangnya, mereka dapat menggunakan terlalu banyak memori. Untuk mengimbanginya, kita sering menggunakan bitmap terkompresi.
Bitmap menderu adalah bitmap terkompresi yang cenderung mengungguli bitmap terkompresi konvensional seperti WAH, EWAH, atau Ringkas. Dalam beberapa kasus, bitmap menderu bisa ratusan kali lebih cepat dan sering kali menawarkan kompresi yang jauh lebih baik. Mereka bahkan bisa lebih cepat daripada bitmap yang tidak terkompresi.
Bitmap menderu ternyata berfungsi dengan baik di banyak aplikasi penting:
Gunakan Roaring untuk kompresi bitmap bila memungkinkan. Jangan gunakan metode kompresi bitmap lainnya (Wang et al., SIGMOD 2017)
pujian karena telah membuat sesuatu yang membuat perangkat lunak saya berjalan 5x lebih cepat (Charles Parker dari BigML)
Perpustakaan ini digunakan oleh
Perpustakaan sudah matang dan telah digunakan dalam produksi selama bertahun-tahun.
Mesin SQL YouTube, Google Procella, menggunakan bitmap Roaring untuk pengindeksan. Apache Lucene menggunakan bitmap Roaring, meskipun mereka memiliki implementasi independennya sendiri. Turunan Lucene seperti Solr dan Elastic juga menggunakan bitmap Roaring. Platform lain seperti Whoosh, Microsoft Visual Studio Team Services (VSTS) dan Pilosa juga menggunakan bitmap Roaring dengan implementasinya sendiri. Anda menemukan bitmap Roaring di InfluxDB, Bleve, Cloud Torrent, Redpanda, dan lain sebagainya.
Ada spesifikasi format serial untuk interoperabilitas antar implementasi. Kami memiliki implementasi C/C++, Java, dan Go yang dapat dioperasikan.
(c) 2013-... penulis RoaringBitmap
Kode ini dilisensikan di bawah Lisensi Apache, Versi 2.0 (AL2.0).
Himpunan adalah abstraksi mendasar dalam perangkat lunak. Mereka dapat diimplementasikan dalam berbagai cara, sebagai kumpulan hash, sebagai pohon, dan sebagainya. Dalam database dan mesin pencari, kumpulan sering kali merupakan bagian integral dari indeks. Misalnya, kita mungkin perlu mempertahankan kumpulan semua dokumen atau baris (diwakili oleh pengidentifikasi numerik) yang memenuhi beberapa properti. Selain menambah atau menghapus elemen dari himpunan, kita memerlukan fungsi cepat untuk menghitung perpotongan, penggabungan, selisih antar himpunan, dan sebagainya.
Untuk mengimplementasikan sekumpulan bilangan bulat, strategi yang sangat menarik adalah bitmap (juga disebut bitset atau bit vektor). Dengan menggunakan n bit, kita dapat merepresentasikan himpunan apa pun yang terbuat dari bilangan bulat dari rentang [0,n): bit ke-i disetel ke satu jika bilangan bulat i ada di himpunan tersebut. Pemroses komoditas menggunakan kata-kata W=32 atau W=64 bit. Dengan menggabungkan banyak kata seperti itu, kita dapat mendukung nilai n yang besar. Persimpangan, kesatuan dan perbedaan kemudian dapat diimplementasikan sebagai operasi bitwise AND, OR dan ANDNOT. Fungsi himpunan yang lebih rumit juga dapat diimplementasikan sebagai operasi bitwise.
Ketika pendekatan bitset dapat diterapkan, pendekatan ini bisa menjadi lipat lebih cepat dibandingkan kemungkinan implementasi himpunan lainnya (misalnya, sebagai himpunan hash) dengan menggunakan memori beberapa kali lebih sedikit.
Namun, bitset, bahkan yang terkompresi tidak selalu dapat diterapkan. Misalnya, jika Anda memiliki 1000 bilangan bulat yang tampak acak, maka array sederhana mungkin merupakan representasi terbaik. Kami menyebut kasus ini sebagai skenario "jarang".
BitSet yang tidak terkompresi dapat menggunakan banyak memori. Misalnya, jika Anda mengambil BitSet dan menyetel bit pada posisi 1.000.000 ke true dan Anda memiliki lebih dari 100kB. Itu lebih dari 100kB untuk menyimpan posisi satu bit. Ini sia-sia bahkan jika Anda tidak peduli dengan memori: misalkan Anda perlu menghitung perpotongan antara BitSet ini dan BitSet lain yang memiliki sedikit pada posisi 1.000.001 menjadi benar, maka Anda harus melewati semua angka nol ini, apakah Anda menyukainya atau tidak. Hal ini bisa menjadi sangat sia-sia.
Meskipun demikian, ada beberapa kasus di mana upaya menggunakan bitmap terkompresi adalah sia-sia. Misalnya, jika Anda memiliki ukuran alam semesta yang kecil. Misalnya, bitmap Anda mewakili kumpulan bilangan bulat dari [0,n) di mana n kecil (misalnya, n=64 atau n=128). Jika Anda dapat menggunakan BitSet yang tidak terkompresi dan tidak menghabiskan penggunaan memori Anda, maka bitmap terkompresi mungkin tidak berguna bagi Anda. Faktanya, jika Anda tidak memerlukan kompresi, BitSet menawarkan kecepatan luar biasa.
Skenario renggang adalah kasus penggunaan lain di mana bitmap terkompresi tidak boleh digunakan. Ingatlah bahwa data yang tampak acak biasanya tidak dapat dikompres. Misalnya, jika Anda memiliki sekumpulan kecil bilangan bulat acak 32-bit, secara matematis tidak mungkin menggunakan kurang dari 32 bit per bilangan bulat, dan upaya kompresi dapat menjadi kontraproduktif.
Kebanyakan alternatif untuk Roaring adalah bagian dari keluarga besar bitmap terkompresi yang merupakan bitmap yang dikodekan sepanjang proses. Mereka mengidentifikasi jangka panjang 1 atau 0 dan mewakilinya dengan kata penanda. Jika Anda memiliki campuran lokal 1 dan 0, Anda menggunakan kata yang tidak terkompresi.
Ada banyak format dalam keluarga ini:
Namun ada masalah besar dengan format ini yang dapat merugikan Anda dalam beberapa kasus: tidak ada akses acak. Jika Anda ingin memeriksa apakah nilai tertentu ada dalam kumpulan, Anda harus memulai dari awal dan "membuka kompresi" semuanya. Ini berarti bahwa jika Anda ingin memotong himpunan besar dengan himpunan besar, Anda masih harus membuka kompresi seluruh himpunan besar dalam kasus terburuk...
Mengaum memecahkan masalah ini. Ini bekerja dengan cara berikut. Ini membagi data menjadi potongan-potongan 2 16 bilangan bulat (misalnya, [0, 2 16 ), [2 16 , 2 x 2 16 ), ...). Dalam sebuah chunk, ia dapat menggunakan bitmap yang tidak terkompresi, daftar bilangan bulat sederhana, atau daftar proses. Apapun format yang digunakan, semuanya memungkinkan Anda memeriksa keberadaan satu nilai dengan cepat (misalnya, dengan pencarian biner). Hasil akhirnya adalah Roaring dapat menghitung banyak operasi jauh lebih cepat daripada format run-length-encoded seperti WAH, EWAH, Concise... Mungkin mengejutkan, Roaring juga umumnya menawarkan rasio kompresi yang lebih baik.
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 );
}
}
} Silakan lihat folder contoh untuk contoh lainnya, yang dapat Anda jalankan dengan ./gradlew :examples:runAll , atau jalankan folder tertentu dengan ./gradlew :examples:runExampleBitmap64 , dll.
http://www.javadoc.io/doc/org.roaringbitmap/RoaringBitmap/
Anda dapat mengunduh rilis dari github: https://github.com/RoaringBitmap/RoaringBitmap/releases
Tambahkan ketergantungan berikut ke file pom.xml Anda...
< dependency >
< groupId >com.github.RoaringBitmap.RoaringBitmap</ groupId >
< artifactId >roaringbitmap</ artifactId >
< version >1.3.16</ version >
</ dependency >Anda dapat menyesuaikan nomor versi.
Kemudian tambahkan repositori ke file pom.xml Anda:
< repositories >
< repository >
< id >jitpack.io</ id >
< url >https://jitpack.io</ url >
</ repository >
</ repositories >Lihat https://github.com/RoaringBitmap/JitPackRoaringBitmapProject untuk contoh lengkap.
Tambahkan ketergantungan berikut ke file pom.xml Anda di dalam elemen <dependencies> ...
< dependency >
< groupId >org.roaringbitmap</ groupId >
< artifactId >roaringbitmap</ artifactId >
< version >1.3.16</ version >
</ dependency > Tambahkan repositori GitHub di dalam elemen <repositories> ( file 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 >Lihat https://github.com/RoaringBitmap/MavenRoaringBitmapProject untuk contoh lengkap.
Akses registri dilindungi oleh otorisasi. Jadi, Anda harus menambahkan kredensial GitHub Anda ke settings.xml global Anda: $HOME.m2settings.xml .
Anda memerlukan token yang dapat Anda hasilkan di GitHub.
GitHub > Settings > Developer Settings > Personal access tokens > Generate new token
Token memerlukan izin read:packages. Pengidentifikasi token adalah string panjang seperti ghp_ieOkN .
Letakkan yang berikut ini di file settings.xml Anda, di dalam elemen <servers> .
< server >
< id >github</ id >
< username >lemire</ username >
< password >ghp_ieOkN</ password >
</ server > Ganti lemire dengan nama pengguna GitHub Anda dan ghp_ieOkN dengan pengidentifikasi token yang baru saja Anda buat.
Maka yang Anda perlukan hanyalah mengedit file build.gradle Anda seperti:
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 '
}Lihat https://github.com/RoaringBitmap/JitPackRoaringBitmapProject untuk contoh lengkap.
Pertama-tama Anda memerlukan kredensial GitHub Anda. Pergi ke
GitHub > Settings > Developer Settings > Personal access tokens > Generate new token
Dan buat token dengan izin read:packages.
Jika nama pengguna GitHub Anda adalah lemire dan token pribadi GitHub Anda ghp_ieOkN , Anda dapat mengaturnya menggunakan variabel sistem. Di bawah bash, Anda dapat melakukannya seperti ini:
export GITHUB_USER=lemire
export GITHUB_PASSWORD=ghp_ieOkN
Jika mau, Anda dapat menulis kredensial GitHub Anda di file gradle.properties Anda
# gradle.properties
githubUser=lemire
githubPassword=ghp_ieOkN
Maka yang Anda perlukan hanyalah mengedit file build.gradle Anda seperti:
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 '
}Lihat https://github.com/RoaringBitmap/MavenRoaringBitmapProject untuk contoh lengkap.
Java tidak memiliki bilangan bulat asli yang tidak ditandatangani tetapi bilangan bulat masih dianggap tidak ditandatangani dalam Roaring dan diurutkan berdasarkan Integer.compareUnsigned . Artinya Java akan mengurutkan angka seperti 0, 1, ..., 2147483647, -2147483648, -2147483647,..., -1. Untuk menafsirkan dengan benar, Anda dapat menggunakan Integer.toUnsignedLong dan Integer.toUnsignedString .
Jika Anda ingin bitmap Anda berada di file yang dipetakan memori, Anda dapat menggunakan paket org.roaringbitmap.buffer sebagai gantinya. Ini berisi dua kelas penting, ImmutableRoaringBitmap dan MutableRoaringBitmap. MutableRoaringBitmaps berasal dari ImmutableRoaringBitmap, sehingga Anda dapat mengonversi (melemparkan) MutableRoaringBitmap ke ImmutableRoaringBitmap dalam waktu yang konstan.
ImmutableRoaringBitmap yang bukan merupakan turunan dari MutableRoaringBitmap didukung oleh ByteBuffer yang disertai dengan beberapa overhead kinerja, namun dengan fleksibilitas tambahan sehingga data dapat berada di mana saja (termasuk di luar heap Java).
Terkadang Anda mungkin perlu bekerja dengan bitmap yang berada di disk (contoh ImmutableRoaringBitmap) dan bitmap yang berada di memori Java. Jika Anda tahu bahwa bitmap akan berada di memori Java, yang terbaik adalah menggunakan instance MutableRoaringBitmap, tidak hanya dapat dimodifikasi, tetapi juga akan lebih cepat. Selain itu, karena instance MutableRoaringBitmap juga merupakan instance ImmutableRoaringBitmap, Anda dapat menulis sebagian besar kode Anda dengan mengharapkan ImmutableRoaringBitmap.
Jika Anda menulis kode dengan mengharapkan instance ImmutableRoaringBitmap, tanpa mencoba mentransmisikan instance tersebut, maka objek Anda akan benar-benar tidak dapat diubah. MutableRoaringBitmap memiliki metode praktis (toImmutableRoaringBitmap) yang merupakan pengembalian sederhana ke instance ImmutableRoaringBitmap. Dari sudut pandang desain bahasa, instance kelas ImmutableRoaringBitmap hanya dapat diubah bila digunakan sesuai antarmuka kelas ImmutableRoaringBitmap. Mengingat bahwa kelas tersebut belum final, dimungkinkan untuk memodifikasi instance melalui antarmuka lain. Oleh karena itu, kami tidak mengartikan istilah “kekal” dalam arti yang murni, melainkan dalam arti praktis.
Salah satu motivasi kami untuk desain ini di mana instance MutableRoaringBitmap dapat diturunkan ke instance ImmutableRoaringBitmap adalah karena bitmap sering kali berukuran besar, atau digunakan dalam konteks di mana alokasi memori harus dihindari, sehingga kami menghindari pemaksaan penyalinan. Salinan dapat diharapkan jika seseorang perlu memadupadankan instance ImmutableRoaringBitmap dan MutableRoaringBitmap.
Contoh kode berikut mengilustrasikan cara membuat ImmutableRoaringBitmap dari ByteBuffer. Dalam kasus seperti itu, konstruktor hanya memuat metadata dalam RAM sementara data sebenarnya diakses dari ByteBuffer sesuai permintaan.
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 ); Alternatifnya, kita dapat membuat serial langsung ke ByteBuffer dengan metode serialize(ByteBuffer) .
Operasi pada ImmutableRoaringBitmap seperti dan, atau, xor, flip, akan menghasilkan RoaringBitmap yang terletak di RAM. Seperti namanya, ImmutableRoaringBitmap sendiri tidak dapat diubah.
Desain ini terinspirasi oleh Apache Druid.
Contoh kerja lengkap dapat ditemukan di file pengujian TestMemoryMapping.java.
Perhatikan bahwa Anda tidak boleh mencampur kelas dari paket org.roaringbitmap dengan kelas dari paket org.roaringbitmap.buffer. Mereka tidak cocok. Namun mereka membuat serial ke output yang sama. Performa kode dalam paket org.roaringbitmap umumnya lebih unggul karena tidak ada overhead akibat penggunaan instance ByteBuffer.
Secara umum, tidak aman untuk mengakses bitmap yang sama menggunakan thread yang berbeda--bitmap tidak disinkronkan untuk kinerjanya. Jika Anda ingin mengakses Bitmap dari lebih dari satu thread, Anda harus menyediakan sinkronisasi. Namun, Anda dapat mengakses bitmap yang tidak dapat diubah dari beberapa thread, selama Anda mematuhi antarmuka ImmutableBitmapDataProvider .
Banyak aplikasi menggunakan Kryo untuk serialisasi/deserialisasi. Seseorang dapat menggunakan bitmap Roaring dengan Kryo secara efisien berkat serializer khusus (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 ;
}
} Meskipun Roaring Bitmap dirancang dengan mempertimbangkan kasus 32-bit, kami memiliki ekstensi hingga bilangan bulat 64-bit. Kami menawarkan dua kelas untuk tujuan ini: Roaring64NavigableMap dan Roaring64Bitmap .
Roaring64NavigableMap mengandalkan pohon merah-hitam konvensional. Kuncinya adalah bilangan bulat 32-bit yang mewakili 32~bit elemen paling signifikan sedangkan nilai pohonnya adalah bitmap Roaring 32-bit. Bitmap Roaring 32-bit mewakili bit paling tidak signifikan dari sekumpulan elemen.
Pendekatan Roaring64Bitmap yang lebih baru mengandalkan struktur data ART untuk menampung pasangan kunci/nilai. Kuncinya terbuat dari elemen 48~bit paling signifikan sedangkan nilainya adalah wadah Roaring 16-bit. Ini terinspirasi oleh The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases oleh Leis dkk. (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 );Serialisasi bitmap Roaring 64-bit ditentukan: lihat https://github.com/RoaringBitmap/RoaringFormatSpec#extention-for-64-bit-implementations
Namun, ini hanya diterapkan oleh Roaring64NavigableMap , dengan beralih:
Roaring64NavigableMap.SERIALIZATION_MODE = Roaring64NavigableMap.SERIALIZATION_MODE_PORTABLE
RangeBitmap adalah struktur data ringkas yang mendukung kueri rentang. Setiap nilai yang ditambahkan ke bitmap dikaitkan dengan pengidentifikasi tambahan, dan kueri menghasilkan RoaringBitmap dari pengidentifikasi yang terkait dengan nilai yang memenuhi kueri. Setiap nilai yang ditambahkan ke bitmap disimpan secara terpisah, sehingga jika suatu nilai ditambahkan dua kali, nilai tersebut akan disimpan dua kali, dan jika nilai tersebut kurang dari ambang batas tertentu, akan ada setidaknya dua bilangan bulat dalam RoaringBitmap yang dihasilkan.
Lebih efisien – baik dari segi waktu maupun ruang – untuk memberikan nilai yang maksimal. Jika Anda tidak mengetahui nilai maksimumnya, berikan Long.MAX_VALUE . Pesanan yang tidak ditandatangani digunakan seperti di tempat lain di perpustakaan.
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 dapat ditulis ke disk dan dipetakan ke memori:
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 );Format serialisasi menggunakan urutan byte little endian.
Dapatkan java
./gradlew assemble akan dikompilasi
./gradlew build akan mengkompilasi dan menjalankan pengujian unit
./gradlew test akan menjalankan pengujian
./gradlew :roaringbitmap:test --tests TestIterators.testIndexIterator4 hanya menjalankan pengujian TestIterators.testIndexIterator4 ; ./gradlew -i :roaringbitmap:test --tests TestRoaringBitmap.issue623 hanya menjalankan pengujian issue623 di kelas TestRoaringBitmap sambil mencetak ke konsol.
./gradlew bsi:test --tests BufferBSITest.testEQ jalankan tes BufferBSITest.testEQ di submodul bsi
Jika Anda berencana berkontribusi pada RoaringBitmap, Anda dapat memuatnya di IDE favorit Anda.
Kontribusi diundang. Kami menggunakan gaya Google Java (lihat roaring_google_checks.xml ). Ini dapat diterapkan secara otomatis ke kode Anda dengan ./gradlew spotlessApply
Harap jangan memformat ulang kode jika tidak perlu (terutama pada komentar/javadoc).
Dalam file serial, bagian dari 4 byte pertama didedikasikan untuk "cookie" yang berfungsi untuk menunjukkan format file.
Jika Anda mencoba melakukan deserialisasi atau memetakan bitmap dari data yang memiliki "cookie" yang tidak dikenal, kode akan membatalkan proses dan melaporkan kesalahan.
Masalah ini akan terjadi pada semua pengguna yang membuat serial bitmap Roaring menggunakan versi sebelum 0.4.x saat mereka meningkatkan ke versi 0.4.x atau lebih baik. Para pengguna ini perlu menyegarkan bitmap serial mereka.
Mengingat N bilangan bulat dalam [0,x), maka ukuran serial dalam byte bitmap Roaring tidak boleh melebihi batas ini:
8 + 9 * ((long)x+65535)/65536 + 2 * N
Artinya, dengan overhead tetap untuk ukuran semesta (x), bitmap Roaring tidak pernah menggunakan lebih dari 2 byte per bilangan bulat. Anda dapat menghubungi RoaringBitmap.maximumSerializedSize untuk perkiraan yang lebih tepat.
Tidak ada struktur data yang selalu ideal. Anda harus memastikan bahwa bitmap Roaring sesuai dengan profil aplikasi Anda. Setidaknya ada dua kasus di mana bitmap Roaring dapat dengan mudah digantikan oleh alternatif kompresi yang lebih unggul:
Anda memiliki beberapa nilai acak yang terbentang dalam interval yang besar (yaitu, Anda memiliki himpunan yang sangat jarang). Misalnya, ambil set 0, 65536, 131072, 196608, 262144 ... Jika ini tipikal aplikasi Anda, Anda mungkin mempertimbangkan untuk menggunakan HashSet atau array terurut sederhana.
Anda memiliki kumpulan nilai acak padat yang tidak pernah membentuk rangkaian nilai berkelanjutan. Misalnya, perhatikan himpunan 0,2,4,...,10000. Jika ini tipikal aplikasi Anda, Anda mungkin lebih baik menggunakan bitset konvensional (misalnya, kelas BitSet Java).
Bagaimana cara memilih elemen secara acak?
Random random = new Random();
bitmap.select(random.nextInt(bitmap.getCardinality()));
Untuk menjalankan benchmark JMH, gunakan perintah berikut:
$ ./gradlew jmh::shadowJar
$ java -jar jmh/build/libs/benchmarks.jar
Anda juga dapat menjalankan benchmark tertentu:
$ java -jar jmh/build/libs/benchmarks.jar 'org.roaringbitmap.aggregation.and.identical.*'
Jika Anda memiliki bash shell, Anda juga dapat menjalankan skrip kami yang secara otomatis membuat dan menjalankan pengujian khusus...
$ ./jmh/run.sh 'org.roaringbitmap.aggregation.and.identical.*'
https://groups.google.com/forum/#!forum/roaringbitmaps
Pekerjaan ini didukung oleh hibah NSERC nomor 26143.
