RoaringBitmap
1.3.16
บิตเซ็ตหรือที่เรียกว่าบิตแมป มักใช้เป็นโครงสร้างข้อมูลที่รวดเร็ว น่าเสียดายที่พวกเขาใช้หน่วยความจำมากเกินไป เพื่อชดเชย เรามักใช้บิตแมปที่ถูกบีบอัด
บิตแมปคำรามเป็นบิตแมปที่ถูกบีบอัด ซึ่งมีแนวโน้มที่จะมีประสิทธิภาพเหนือกว่าบิตแมปที่ถูกบีบอัดทั่วไป เช่น WAH, EWAH หรือ Concise ในบางกรณี บิตแมปคำรามอาจเร็วขึ้นหลายร้อยเท่า และมักมีการบีบอัดที่ดีกว่ามาก พวกมันยังเร็วกว่าบิตแมปที่ไม่มีการบีบอัดด้วยซ้ำ
บิตแมปคำรามทำงานได้ดีในแอปพลิเคชันที่สำคัญมากมาย:
ใช้ Roaring เพื่อบีบอัดบิตแมปทุกครั้งที่เป็นไปได้ อย่าใช้วิธีการบีบอัดบิตแมปอื่น ๆ (Wang et al., SIGMOD 2017)
ความรุ่งโรจน์ในการทำบางสิ่งที่ทำให้ซอฟต์แวร์ของฉันทำงานเร็วขึ้น 5 เท่า (Charles Parker จาก BigML)
ห้องสมุดนี้ถูกใช้โดย
ห้องสมุดมีความสมบูรณ์และมีการใช้ในการผลิตมาหลายปีแล้ว
Google Procella ซึ่งเป็น YouTube SQL Engine ใช้บิตแมป Roaring สำหรับการจัดทำดัชนี Apache Lucene ใช้บิตแมป Roaring แม้ว่าจะมีการใช้งานที่เป็นอิสระของตัวเองก็ตาม อนุพันธ์ของ Lucene เช่น Solr และ Elastic ก็ใช้บิตแมปคำรามเช่นกัน แพลตฟอร์มอื่นๆ เช่น Whoosh, Microsoft Visual Studio Team Services (VSTS) และ Pilosa ยังใช้บิตแมป Roaring ในการใช้งานของตนเอง คุณพบบิตแมป Roaring ใน InfluxDB, Bleve, Cloud Torrent, Redpanda และอื่นๆ
มีข้อกำหนดรูปแบบต่อเนื่องสำหรับการทำงานร่วมกันระหว่างการใช้งาน เรามีการใช้งาน C/C++, Java และ Go ที่ทำงานร่วมกันได้
(c) 2013-... ผู้เขียน RoaringBitmap
รหัสนี้ได้รับอนุญาตภายใต้ Apache License เวอร์ชัน 2.0 (AL2.0)
ชุดถือเป็นนามธรรมขั้นพื้นฐานในซอฟต์แวร์ สามารถนำไปใช้ได้หลายวิธี เช่น ชุดแฮช ต้นไม้ เป็นต้น ในฐานข้อมูลและเครื่องมือค้นหา ชุดต่างๆ มักจะเป็นส่วนสำคัญของดัชนี ตัวอย่างเช่น เราอาจจำเป็นต้องรักษาชุดของเอกสารหรือแถวทั้งหมด (แสดงด้วยตัวระบุตัวเลข) ที่ตรงตามคุณสมบัติบางอย่าง นอกจากการเพิ่มหรือลบองค์ประกอบออกจากเซตแล้ว เรายังต้องการฟังก์ชันที่รวดเร็วเพื่อคำนวณจุดตัด การรวม ความแตกต่างระหว่างเซต และอื่นๆ
ในการใช้ชุดจำนวนเต็ม กลยุทธ์ที่น่าสนใจอย่างยิ่งคือบิตแมป (เรียกอีกอย่างว่าบิตเซ็ตหรือบิตเวกเตอร์) เมื่อใช้ n บิต เราสามารถแสดงชุดใดๆ ที่สร้างจากจำนวนเต็มจากช่วง [0,n): บิตที่ ith จะถูกตั้งค่าเป็น 1 หากมีจำนวนเต็ม i อยู่ในชุด ตัวประมวลผลสินค้าโภคภัณฑ์ใช้คำ W=32 หรือ W=64 บิต การรวมคำดังกล่าวเข้าด้วยกันทำให้เราสามารถรองรับค่า n ที่มีขนาดใหญ่ได้ ทางแยก สหภาพ และความแตกต่างสามารถนำไปใช้เป็นการดำเนินการระดับบิต AND, OR และ ANDNOT ฟังก์ชั่นการตั้งค่าที่ซับซ้อนมากขึ้นยังสามารถนำไปใช้เป็นการดำเนินการระดับบิตได้
เมื่อใช้วิธีบิตเซ็ต ก็จะมีลำดับความสำคัญได้เร็วกว่าการใช้งานชุดอื่นที่เป็นไปได้ (เช่น เป็นชุดแฮช) ในขณะที่ใช้หน่วยความจำน้อยกว่าหลายเท่า
อย่างไรก็ตาม บิตเซ็ต แม้แต่บิตที่ถูกบีบอัดก็ไม่สามารถใช้ได้เสมอไป ตัวอย่างเช่น หากคุณมีจำนวนเต็มสุ่ม 1,000 ตัว อาร์เรย์แบบธรรมดาอาจเป็นการแสดงได้ดีที่สุด เราเรียกกรณีนี้ว่าเป็นสถานการณ์ "เบาบาง"
BitSet ที่ไม่มีการบีบอัดสามารถใช้หน่วยความจำได้มาก ตัวอย่างเช่น หากคุณใช้ BitSet และตั้งค่าบิตที่ตำแหน่ง 1,000,000 ให้เป็นจริง และคุณมีมากกว่า 100kB นั่นคือเกิน 100kB เพื่อเก็บตำแหน่งหนึ่งบิต นี่เป็นการสิ้นเปลืองแม้ว่าคุณจะไม่สนใจเกี่ยวกับหน่วยความจำ: สมมติว่าคุณต้องคำนวณจุดตัดระหว่าง BitSet นี้กับอีกอันที่มีบิตอยู่ที่ตำแหน่ง 1,000,001 ให้เป็นจริง จากนั้นคุณจะต้องผ่านศูนย์เหล่านี้ทั้งหมด ไม่ว่าคุณจะชอบก็ตาม หรือไม่ นั่นอาจกลายเป็นเรื่องสิ้นเปลืองมาก
ที่ถูกกล่าวว่า มีบางกรณีที่การพยายามใช้บิตแมปที่ถูกบีบอัดนั้นสิ้นเปลือง เช่น หากคุณมีจักรวาลที่มีขนาดเล็ก เช่น บิตแมปของคุณแสดงถึงชุดจำนวนเต็มจาก [0,n) โดยที่ n มีขนาดเล็ก (เช่น n=64 หรือ n=128) หากคุณสามารถใช้ BitSet ที่ไม่มีการบีบอัดได้ และไม่ทำให้การใช้งานหน่วยความจำของคุณเสียหาย แสดงว่าบิตแมปที่ถูกบีบอัดอาจไม่มีประโยชน์สำหรับคุณ ที่จริงแล้ว หากคุณไม่ต้องการการบีบอัด BitSet ก็มีความเร็วที่น่าทึ่ง
สถานการณ์แบบกระจัดกระจายเป็นอีกกรณีการใช้งานที่ไม่ควรใช้บิตแมปที่ถูกบีบอัด โปรดทราบว่าข้อมูลที่ดูแบบสุ่มมักไม่สามารถบีบอัดได้ เช่น หากคุณมีชุดจำนวนเต็มสุ่ม 32 บิตชุดเล็กๆ ในทางคณิตศาสตร์ เป็นไปไม่ได้เลยที่จะใช้จำนวนเต็มน้อยกว่า 32 บิตต่อจำนวนเต็ม และความพยายามในการบีบอัดอาจส่งผลเสียได้
ทางเลือกส่วนใหญ่สำหรับ Roaring เป็นส่วนหนึ่งของกลุ่มบิตแมปที่ถูกบีบอัดขนาดใหญ่กว่าซึ่งเป็นบิตแมปที่เข้ารหัสความยาวรัน พวกเขาระบุการวิ่งระยะยาวของ 1 หรือ 0 และแสดงด้วยคำเครื่องหมาย หากคุณมีการผสมระหว่าง 1 และ 0 คุณจะใช้คำที่ไม่มีการบีบอัด
ตระกูลนี้มีหลายรูปแบบ:
มีปัญหาใหญ่กับรูปแบบเหล่านี้ แต่อาจทำให้คุณเสียหายได้ในบางกรณี: ไม่มีการเข้าถึงแบบสุ่ม หากคุณต้องการตรวจสอบว่ามีค่าที่กำหนดอยู่ในชุดหรือไม่ คุณต้องเริ่มจากจุดเริ่มต้นและ "คลายการบีบอัด" ทั้งหมด ซึ่งหมายความว่า หากคุณต้องการตัดชุดใหญ่กับชุดใหญ่ คุณยังคงต้องคลายการบีบอัดชุดใหญ่ทั้งหมดในกรณีที่แย่ที่สุด...
คำรามแก้ปัญหานี้ได้ มันทำงานในลักษณะดังต่อไปนี้ มันแบ่งข้อมูลออกเป็นส่วนๆ ของจำนวนเต็ม 2 16 (เช่น [0, 2 16 ), [2 16 , 2 x 2 16 ), ...) ภายในกลุ่มข้อมูล สามารถใช้บิตแมปที่ไม่มีการบีบอัด รายการจำนวนเต็มอย่างง่าย หรือรายการรัน ไม่ว่าจะใช้รูปแบบใดก็ตาม ทั้งหมดนี้จะทำให้คุณสามารถตรวจสอบการมีอยู่ของค่าใดค่าหนึ่งได้อย่างรวดเร็ว (เช่น ด้วยการค้นหาแบบไบนารี) ผลลัพธ์สุทธิก็คือ Roaring สามารถคำนวณการดำเนินการหลายอย่างได้เร็วกว่ารูปแบบที่เข้ารหัสความยาวรัน เช่น WAH, EWAH, Concise... อาจน่าแปลกใจที่ Roaring โดยทั่วไปมีอัตราส่วนการบีบอัดที่ดีกว่าด้วย
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 );
}
}
} โปรดดูตัวอย่างเพิ่มเติมในโฟลเดอร์ตัวอย่าง ซึ่งคุณสามารถเรียกใช้ด้วย ./gradlew :examples:runAll หรือเรียกใช้โฟลเดอร์เฉพาะด้วย ./gradlew :examples:runExampleBitmap64 เป็นต้น
http://www.javadoc.io/doc/org.roaringbitmap/RoaringBitmap/
คุณสามารถดาวน์โหลดรุ่นต่างๆ ได้จาก github: https://github.com/RoaringBitmap/RoaringBitmap/releases
เพิ่มการพึ่งพาต่อไปนี้ให้กับไฟล์ pom.xml ของคุณ...
< dependency >
< groupId >com.github.RoaringBitmap.RoaringBitmap</ groupId >
< artifactId >roaringbitmap</ artifactId >
< version >1.3.16</ version >
</ dependency >คุณสามารถปรับหมายเลขเวอร์ชันได้
จากนั้นเพิ่มที่เก็บลงในไฟล์ pom.xml ของคุณ:
< repositories >
< repository >
< id >jitpack.io</ id >
< url >https://jitpack.io</ url >
</ repository >
</ repositories >ดู https://github.com/RoaringBitmap/JitPackRoaringBitmapProject สำหรับตัวอย่างที่สมบูรณ์
เพิ่มการพึ่งพาต่อไปนี้ให้กับไฟล์ pom.xml ของคุณภายในองค์ประกอบ <dependencies> ...
< dependency >
< groupId >org.roaringbitmap</ groupId >
< artifactId >roaringbitmap</ artifactId >
< version >1.3.16</ version >
</ dependency > เพิ่มที่เก็บ GitHub ภายในองค์ประกอบ <repositories> (ไฟล์ 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 >ดู https://github.com/RoaringBitmap/MavenRoaringBitmapProject สำหรับตัวอย่างที่สมบูรณ์
การเข้าถึงรีจิสทรีได้รับการคุ้มครองโดยการอนุญาต ดังนั้นคุณต้องเพิ่มข้อมูลรับรอง GitHub ของคุณไปยัง global settings.xml: $HOME.m2settings.xml
คุณจะต้องมีโทเค็นที่คุณสามารถสร้างได้บน GitHub
GitHub > Settings > Developer Settings > Personal access tokens > Generate new token
โทเค็นต้องได้รับอนุญาตจาก read:packages ตัวระบุโทเค็นเป็นสตริงยาว เช่น ghp_ieOkN
วางสิ่งต่อไปนี้ในไฟล์ settings.xml ภายในองค์ประกอบ <servers>
< server >
< id >github</ id >
< username >lemire</ username >
< password >ghp_ieOkN</ password >
</ server > แทนที่ lemire ด้วยชื่อผู้ใช้ GitHub ของคุณและ ghp_ieOkN ด้วยตัวระบุโทเค็นที่คุณเพิ่งสร้างขึ้น
สิ่งที่คุณต้องมีคือแก้ไขไฟล์ build.gradle ของคุณดังนี้:
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 '
}ดู https://github.com/RoaringBitmap/JitPackRoaringBitmapProject สำหรับตัวอย่างที่สมบูรณ์
คุณต้องมีข้อมูลประจำตัว GitHub ของคุณก่อน ไปที่
GitHub > Settings > Developer Settings > Personal access tokens > Generate new token
และสร้างโทเค็นด้วยสิทธิ์ read:packages
หากชื่อผู้ใช้ GitHub ของคุณคือ lemire และโทเค็นส่วนตัว GitHub ghp_ieOkN ของคุณ คุณสามารถตั้งค่าได้โดยใช้ตัวแปรระบบ ภายใต้ bash คุณสามารถทำได้ดังนี้:
export GITHUB_USER=lemire
export GITHUB_PASSWORD=ghp_ieOkN
หากคุณต้องการ คุณสามารถเขียนข้อมูลรับรอง GitHub ของคุณในไฟล์ gradle.properties
# gradle.properties
githubUser=lemire
githubPassword=ghp_ieOkN
สิ่งที่คุณต้องมีคือแก้ไขไฟล์ build.gradle ของคุณดังนี้:
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 '
}ดู https://github.com/RoaringBitmap/MavenRoaringBitmapProject สำหรับตัวอย่างที่สมบูรณ์
Java ขาดจำนวนเต็มที่ไม่ได้ลงนามดั้งเดิม แต่จำนวนเต็มยังคงถือว่าไม่ได้ลงนามภายใน Roaring และเรียงลำดับตาม Integer.compareUnsigned ซึ่งหมายความว่า Java จะเรียงลำดับตัวเลขเช่น 0, 1, ..., 2147483647, -2147483648, -2147483647,..., -1 หากต้องการตีความอย่างถูกต้อง คุณสามารถใช้ Integer.toUnsignedLong และ Integer.toUnsignedString
หากคุณต้องการให้บิตแมปของคุณอยู่ในไฟล์ที่แมปหน่วยความจำ คุณสามารถใช้แพ็คเกจ org.roaringbitmap.buffer แทน ประกอบด้วยคลาสที่สำคัญสองคลาสคือ ImmutableRoaringBitmap และ MutableRoaringBitmap MutableRoaringBitmaps มาจาก ImmutableRoaringBitmap เพื่อให้คุณสามารถแปลง (ส่ง) MutableRoaringBitmap เป็น ImmutableRoaringBitmap ในเวลาคงที่
ImmutableRoaringBitmap ที่ไม่ใช่อินสแตนซ์ของ MutableRoaringBitmap ได้รับการสนับสนุนโดย ByteBuffer ซึ่งมาพร้อมกับโอเวอร์เฮดด้านประสิทธิภาพบางส่วน แต่มีความยืดหยุ่นเพิ่มเติมที่ข้อมูลสามารถอยู่ที่ใดก็ได้ (รวมถึงภายนอกฮีป Java)
ในบางครั้ง คุณอาจต้องทำงานกับบิตแมปที่อยู่บนดิสก์ (อินสแตนซ์ของ ImmutableRoaringBitmap) และบิตแมปที่อยู่ในหน่วยความจำ Java หากคุณรู้ว่าบิตแมปจะอยู่ในหน่วยความจำ Java วิธีที่ดีที่สุดคือใช้อินสแตนซ์ MutableRoaringBitmap ไม่เพียงแต่สามารถแก้ไขได้เท่านั้น แต่ยังจะเร็วขึ้นอีกด้วย ยิ่งไปกว่านั้น เนื่องจากอินสแตนซ์ MutableRoaringBitmap ก็เป็นอินสแตนซ์ ImmutableRoaringBitmap เช่นกัน คุณจึงสามารถเขียนโค้ดได้มากโดยคาดหวังว่าจะได้รับ ImmutableRoaringBitmap
หากคุณเขียนโค้ดโดยคาดว่าจะมีอินสแตนซ์ ImmutableRoaringBitmap โดยไม่พยายามส่งอินสแตนซ์ อ็อบเจ็กต์ของคุณจะไม่เปลี่ยนรูปอย่างแท้จริง MutableRoaringBitmap มีวิธีการที่สะดวกสบาย (เป็น ImmutableRoaringBitmap) ซึ่งเป็นการส่งกลับไปยังอินสแตนซ์ ImmutableRoaringBitmap อย่างง่าย จากมุมมองการออกแบบภาษา อินสแตนซ์ของคลาส ImmutableRoaringBitmap จะไม่เปลี่ยนรูปเฉพาะเมื่อใช้ตามอินเทอร์เฟซของคลาส ImmutableRoaringBitmap เนื่องจากคลาสไม่ใช่คลาสสุดท้าย จึงเป็นไปได้ที่จะแก้ไขอินสแตนซ์ผ่านอินเทอร์เฟซอื่นๆ ดังนั้นเราจึงไม่ได้ใช้คำว่า "ไม่เปลี่ยนรูป" ในลักษณะที่พิถีพิถัน แต่ใช้ในทางปฏิบัติ
แรงจูงใจประการหนึ่งของเราในการออกแบบนี้ซึ่งสามารถส่งอินสแตนซ์ MutableRoaringBitmap ลงไปที่อินสแตนซ์ ImmutableRoaringBitmap ก็คือบิตแมปมักจะมีขนาดใหญ่ หรือใช้ในบริบทที่ควรหลีกเลี่ยงการจัดสรรหน่วยความจำ ดังนั้นเราจึงหลีกเลี่ยงการบังคับให้ทำสำเนา อาจคาดหวังสำเนาได้หากต้องการผสมและจับคู่อินสแตนซ์ ImmutableRoaringBitmap และ MutableRoaringBitmap
ตัวอย่างโค้ดต่อไปนี้แสดงให้เห็นถึงวิธีการสร้าง ImmutableRoaringBitmap จาก ByteBuffer ในกรณีดังกล่าว ตัวสร้างจะโหลดเฉพาะข้อมูลเมตาใน RAM ในขณะที่ข้อมูลจริงถูกเข้าถึงจาก 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 ); อีกทางหนึ่ง เราสามารถทำให้เป็นอนุกรมโดยตรงไปยัง ByteBuffer ด้วยวิธี serialize(ByteBuffer)
การดำเนินการบน ImmutableRoaringBitmap เช่น และ, หรือ, xor, flip จะสร้าง RoaringBitmap ซึ่งอยู่ใน RAM ตามชื่อที่แนะนำ ImmutableRoaringBitmap เองไม่สามารถแก้ไขได้
การออกแบบนี้ได้รับแรงบันดาลใจจาก Apache Druid
สามารถค้นหาตัวอย่างการทำงานที่สมบูรณ์ได้ในไฟล์ทดสอบ TestMemoryMapping.java
โปรดทราบว่าคุณไม่ควรผสมคลาสจากแพ็คเกจ org.roaringbitmap กับคลาสจากแพ็คเกจ org.roaringbitmap.buffer พวกเขาเข้ากันไม่ได้ อย่างไรก็ตามพวกมันจะซีเรียลไลซ์เป็นเอาต์พุตเดียวกัน โดยทั่วไปประสิทธิภาพของโค้ดในแพ็คเกจ org.roaringbitmap นั้นเหนือกว่า เนื่องจากไม่มีค่าใช้จ่ายใดๆ เนื่องจากการใช้อินสแตนซ์ ByteBuffer
โดยทั่วไป การเข้าถึงบิตแมปเดียวกันโดยใช้เธรดที่แตกต่างกันนั้นไม่ปลอดภัย เนื่องจากบิตแมปจะไม่ซิงโครไนซ์กับประสิทธิภาพการทำงาน หากคุณต้องการเข้าถึงบิตแมปจากมากกว่าหนึ่งเธรด คุณควรจัดให้มีการซิงโครไนซ์ อย่างไรก็ตาม คุณสามารถเข้าถึงบิตแมปที่ไม่เปลี่ยนรูปได้จากหลายเธรด ตราบใดที่คุณปฏิบัติตามอินเทอร์เฟซ ImmutableBitmapDataProvider
แอปพลิเคชันจำนวนมากใช้ Kryo สำหรับการซีเรียลไลซ์/การดีซีเรียลไลซ์ เราสามารถใช้ Roaring bitmaps กับ Kryo ได้อย่างมีประสิทธิภาพด้วย serializer แบบกำหนดเอง (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 ;
}
} แม้ว่า Roaring Bitmap จะได้รับการออกแบบโดยคำนึงถึงขนาดตัวพิมพ์ 32 บิต แต่เราก็มีส่วนขยายเป็นจำนวนเต็ม 64 บิต เรามีคลาสสองคลาสเพื่อจุดประสงค์นี้: Roaring64NavigableMap และ Roaring64Bitmap
Roaring64NavigableMap อาศัยต้นไม้สีแดง-ดำแบบธรรมดา คีย์เป็นจำนวนเต็ม 32 บิตซึ่งแสดงถึงองค์ประกอบ 32~บิตที่สำคัญที่สุด ในขณะที่ค่าของแผนผังเป็นบิตแมป Roaring 32 บิต บิตแมปคำราม 32 บิตแสดงถึงบิตที่มีนัยสำคัญน้อยที่สุดของชุดองค์ประกอบ
วิธีการ Roaring64Bitmap ที่ใหม่กว่าอาศัยโครงสร้างข้อมูล ART เพื่อเก็บคู่คีย์/ค่า คีย์ถูกสร้างขึ้นจากองค์ประกอบ 48 บิตที่สำคัญที่สุด ในขณะที่ค่าเป็นคอนเทนเนอร์ Roaring 16 บิต ได้รับแรงบันดาลใจจาก The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases โดย Leis และคณะ (ไอซีดีอี '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 );มีการระบุการทำให้เป็นอนุกรมของบิตแมป Roaring 64 บิต: ดู https://github.com/RoaringBitmap/RoaringFormatSpec#extention-for-64-bit-implementations
อย่างไรก็ตาม มันถูกนำไปใช้โดย Roaring64NavigableMap เท่านั้น โดยการสลับ:
Roaring64NavigableMap.SERIALIZATION_MODE = Roaring64NavigableMap.SERIALIZATION_MODE_PORTABLE
RangeBitmap เป็นโครงสร้างข้อมูลที่กระชับซึ่งรองรับการสืบค้นช่วง แต่ละค่าที่เพิ่มลงในบิตแมปจะเชื่อมโยงกับตัวระบุส่วนเพิ่ม และแบบสอบถามจะสร้าง RoaringBitmap ของตัวระบุที่เกี่ยวข้องกับค่าที่ตรงกับแบบสอบถาม ทุกค่าที่เพิ่มลงในบิตแมปจะถูกจัดเก็บแยกกัน ดังนั้นหากมีการเพิ่มค่าสองครั้ง ค่านั้นจะถูกเก็บไว้สองครั้ง และหากค่านั้นน้อยกว่าเกณฑ์ที่กำหนด จะมีจำนวนเต็มอย่างน้อยสองตัวในผลลัพธ์ RoaringBitmap
มีประสิทธิภาพมากกว่าทั้งในแง่ของเวลาและพื้นที่เพื่อให้เกิดมูลค่าสูงสุด หากคุณไม่ทราบค่าสูงสุด ให้ระบุ Long.MAX_VALUE มีการใช้คำสั่งที่ไม่ได้ลงนามเหมือนกับที่อื่นๆ ในห้องสมุด
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 สามารถเขียนลงดิสก์และหน่วยความจำที่แมปได้:
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 );รูปแบบการทำให้เป็นอนุกรมใช้ลำดับไบต์ endian เพียงเล็กน้อย
รับจาวา
./gradlew assemble จะทำการคอมไพล์
./gradlew build จะคอมไพล์และรันการทดสอบหน่วย
./gradlew test จะทำการทดสอบ
./gradlew :roaringbitmap:test --tests TestIterators.testIndexIterator4 รันเพียงการทดสอบ Test TestIterators.testIndexIterator4 ; ./gradlew -i :roaringbitmap:test --tests TestRoaringBitmap.issue623 รันเฉพาะการทดสอบ issue623 ในคลาส TestRoaringBitmap ในขณะที่พิมพ์ออกไปยังคอนโซล
./gradlew bsi:test --tests BufferBSITest.testEQ รันเพียงการทดสอบ BufferBSITest.testEQ ในโมดูลย่อย bsi
หากคุณวางแผนที่จะสนับสนุน RoaringBitmap คุณสามารถโหลดมันขึ้นมาใน IDE ที่คุณชื่นชอบได้
ขอเชิญร่วมบริจาค เราใช้สไตล์ Google Java (ดู roaring_google_checks.xml ) สามารถนำไปใช้กับโค้ดของคุณโดยอัตโนมัติด้วย ./gradlew spotlessApply
กรุณาอย่าฟอร์แมตโค้ดใหม่โดยไม่จำเป็น (โดยเฉพาะในความคิดเห็น/javadoc)
ในไฟล์ซีเรียลไลซ์ ส่วนหนึ่งของ 4 ไบต์แรกมีไว้สำหรับ "คุกกี้" ซึ่งทำหน้าที่ระบุรูปแบบไฟล์
หากคุณพยายามดีซีเรียลไลซ์หรือแมปบิตแมปจากข้อมูลที่มี "คุกกี้" ที่ไม่รู้จัก โค้ดจะยกเลิกกระบวนการและรายงานข้อผิดพลาด
ปัญหานี้จะเกิดขึ้นกับผู้ใช้ทุกคนที่จัดลำดับบิตแมป Roaring โดยใช้เวอร์ชันก่อน 0.4.x ขณะที่อัปเกรดเป็นเวอร์ชัน 0.4.x หรือดีกว่า ผู้ใช้เหล่านี้จำเป็นต้องรีเฟรชบิตแมปที่ต่อเนื่องกัน
เมื่อกำหนดจำนวนเต็ม N ใน [0,x) ดังนั้นขนาดซีเรียลไลซ์เป็นไบต์ของบิตแมป Roaring ไม่ควรเกินขอบเขตนี้:
8 + 9 * ((long)x+65535)/65536 + 2 * N
กล่าวคือ เมื่อพิจารณาค่าใช้จ่ายคงที่สำหรับขนาดจักรวาล (x) บิตแมปคำรามจะไม่ใช้เกิน 2 ไบต์ต่อจำนวนเต็ม คุณสามารถเรียก RoaringBitmap.maximumSerializedSize เพื่อการประมาณที่แม่นยำยิ่งขึ้น
ไม่มีโครงสร้างข้อมูลใดที่สมบูรณ์แบบเสมอไป คุณควรตรวจสอบให้แน่ใจว่าบิตแมป Roaring เหมาะสมกับโปรไฟล์แอปพลิเคชันของคุณ มีอย่างน้อยสองกรณีที่บิตแมป Roaring สามารถแทนที่ได้อย่างง่ายดายด้วยการบีบอัดทางเลือกที่เหนือกว่า:
คุณมีค่าสุ่มไม่กี่ค่าที่ทอดในช่วงเวลาขนาดใหญ่ (เช่น คุณมีชุดที่เบาบางมาก) ตัวอย่างเช่น ใช้ชุด 0, 65536, 131072, 196608, 262144 ... หากนี่เป็นเรื่องปกติสำหรับแอปพลิเคชันของคุณ คุณอาจลองใช้ HashSet หรืออาร์เรย์ที่เรียงลำดับอย่างง่าย
คุณมีชุดค่าสุ่มที่หนาแน่นซึ่งไม่เคยสร้างค่าต่อเนื่องกัน ตัวอย่างเช่น พิจารณาเซต 0,2,4,...,10000 หากนี่เป็นเรื่องปกติสำหรับแอปพลิเคชันของคุณ คุณอาจได้รับบริการที่ดีกว่าด้วยบิตเซ็ตทั่วไป (เช่น คลาส BitSet ของ Java)
ฉันจะเลือกองค์ประกอบแบบสุ่มได้อย่างไร
Random random = new Random();
bitmap.select(random.nextInt(bitmap.getCardinality()));
หากต้องการรันการวัดประสิทธิภาพ JMH ให้ใช้คำสั่งต่อไปนี้:
$ ./gradlew jmh::shadowJar
$ java -jar jmh/build/libs/benchmarks.jar
คุณยังสามารถเรียกใช้การวัดประสิทธิภาพเฉพาะได้:
$ java -jar jmh/build/libs/benchmarks.jar 'org.roaringbitmap.aggregation.and.identical.*'
หากคุณมี bash shell คุณยังสามารถเรียกใช้สคริปต์ของเราซึ่งจะสร้างและรันการทดสอบเฉพาะโดยอัตโนมัติ...
$ ./jmh/run.sh 'org.roaringbitmap.aggregation.and.identical.*'
https://groups.google.com/forum/#!forum/roaringbitmaps
งานนี้ได้รับการสนับสนุนจาก NSERC ให้หมายเลข 26143
