RoaringBitmap
1.3.16
تُستخدم مجموعات البت، والتي تسمى أيضًا الصور النقطية، بشكل شائع كهياكل بيانات سريعة. لسوء الحظ، يمكنهم استخدام الكثير من الذاكرة. للتعويض، غالبًا ما نستخدم الصور النقطية المضغوطة.
الصور النقطية الصاخبة هي صور نقطية مضغوطة تميل إلى التفوق على الصور النقطية المضغوطة التقليدية مثل WAH أو EWAH أو Concise. في بعض الحالات، يمكن أن تكون الصور النقطية الصاخبة أسرع بمئات المرات، وغالبًا ما توفر ضغطًا أفضل بشكل ملحوظ. ويمكن أن تكون أسرع من الصور النقطية غير المضغوطة.
تم اكتشاف أن الصور النقطية الهادرة تعمل بشكل جيد في العديد من التطبيقات المهمة:
استخدم Roaring لضغط الصور النقطية كلما أمكن ذلك. لا تستخدم طرقًا أخرى لضغط الصور النقطية (Wang et al., SIGMOD 2017)
مجد لصنع شيء يجعل برنامجي يعمل بشكل أسرع بمقدار 5 مرات (تشارلز باركر من BigML)
يتم استخدام هذه المكتبة من قبل
المكتبة ناضجة وتم استخدامها في الإنتاج لسنوات عديدة.
يستخدم محرك YouTube SQL، Google Procella، الصور النقطية الهادرة للفهرسة. يستخدم Apache Lucene الصور النقطية Roaring، على الرغم من أن لها تطبيقًا مستقلاً خاصًا بها. تستخدم مشتقات Lucene مثل Solr وElastic أيضًا الصور النقطية Roaring. تستخدم الأنظمة الأساسية الأخرى مثل Whoosh وMicrosoft Visual Studio Team Services (VSTS) وPilosa أيضًا الصور النقطية Roaring مع تطبيقاتها الخاصة. يمكنك العثور على الصور النقطية Roaring في InfluxDB، وBleve، وCloud Torrent، وRedpanda، وما إلى ذلك.
توجد مواصفات تنسيق متسلسلة لقابلية التشغيل البيني بين التطبيقات. لدينا تطبيقات C/C++ وJava وGo قابلة للتشغيل المتبادل.
(ج) 2013-... مؤلفو RoaringBitmap
تم ترخيص هذا الرمز بموجب ترخيص Apache، الإصدار 2.0 (AL2.0).
المجموعات هي فكرة تجريدية أساسية في البرمجيات. ويمكن تنفيذها بطرق مختلفة، مثل مجموعات التجزئة، والأشجار، وما إلى ذلك. في قواعد البيانات ومحركات البحث، غالبًا ما تكون المجموعات جزءًا لا يتجزأ من الفهارس. على سبيل المثال، قد نحتاج إلى الاحتفاظ بمجموعة من كافة المستندات أو الصفوف (ممثلة بمعرف رقمي) التي تلبي بعض الخصائص. إلى جانب إضافة أو إزالة عناصر من المجموعة، نحتاج إلى وظائف سريعة لحساب التقاطع والاتحاد والفرق بين المجموعات وما إلى ذلك.
لتنفيذ مجموعة من الأعداد الصحيحة، هناك إستراتيجية جذابة بشكل خاص هي الصورة النقطية (وتسمى أيضًا مجموعة البت أو ناقل البت). باستخدام n بت، يمكننا تمثيل أي مجموعة مكونة من الأعداد الصحيحة من النطاق [0,n): يتم تعيين البت ith على واحد إذا كان العدد الصحيح i موجودًا في المجموعة. تستخدم معالجات السلع كلمات W=32 أو W=64 بت. من خلال الجمع بين العديد من هذه الكلمات، يمكننا دعم القيم الكبيرة لـ n. يمكن بعد ذلك تنفيذ التقاطعات والاتحادات والاختلافات كعمليات AND وOR وANDNOT. يمكن أيضًا تنفيذ وظائف المجموعة الأكثر تعقيدًا كعمليات bitwise.
عندما يكون أسلوب مجموعة البتات قابلاً للتطبيق، فإنه يمكن أن يكون أسرع من التنفيذ المحتمل الآخر لمجموعة (على سبيل المثال، كمجموعة تجزئة) مع استخدام ذاكرة أقل بعدة مرات.
ومع ذلك، فإن مجموعة البتات، حتى تلك المضغوطة، لا تكون قابلة للتطبيق دائمًا. على سبيل المثال، إذا كان لديك 1000 عدد صحيح يبدو عشوائيًا، فقد تكون المصفوفة البسيطة هي أفضل تمثيل. نشير إلى هذه الحالة بالسيناريو "المتفرق".
يمكن لـ BitSet غير المضغوطة استخدام قدر كبير من الذاكرة. على سبيل المثال، إذا أخذت BitSet وقمت بتعيين البت في الموضع 1,000,000 إلى true وكان لديك ما يزيد قليلاً عن 100 كيلو بايت. وهذا يزيد عن 100 كيلو بايت لتخزين موضع بت واحد. يعد هذا إهدارًا حتى لو كنت لا تهتم بالذاكرة: لنفترض أنك بحاجة إلى حساب التقاطع بين مجموعة 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 إلى ملف settings.xml العام الخاص بك: $HOME.m2settings.xml .
ستحتاج إلى رمز مميز يمكنك إنشاؤه على GitHub.
GitHub > Settings > Developer Settings > Personal access tokens > Generate new token
يحتاج الرمز المميز إلى إذن القراءة: الحزم. معرف الرمز المميز عبارة عن سلسلة طويلة مثل 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
وقم بإنشاء رمز مميز مع إذن القراءة: الحزم.
إذا كان اسم مستخدم 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 على طريقة ملائمة (toImmutableRoaringBitmap) وهي عبارة عن إعادة بسيطة إلى مثيل 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 مثل and، أو xor، flip، إلى إنشاء RoaringBitmap الموجودة في ذاكرة الوصول العشوائي (RAM). كما يوحي الاسم، لا يمكن تعديل ImmutableRoaringBitmap نفسها.
هذا التصميم مستوحى من Apache Druid.
يمكن العثور على مثال عملي كامل في ملف الاختبار TestMemoryMapping.java.
لاحظ أنه لا ينبغي عليك خلط الفئات من الحزمة org.roaringbitmap مع الفئات من الحزمة org.roaringbitmap.buffer. إنهم غير متوافقين. ومع ذلك، فإنها تقوم بالتسلسل إلى نفس الإخراج. أداء التعليمات البرمجية في حزمة org.roaringbitmap متفوق بشكل عام لأنه لا يوجد أي حمل بسبب استخدام مثيلات ByteBuffer.
بشكل عام، من غير الآمن الوصول إلى نفس الصور النقطية باستخدام مؤشرات ترابط مختلفة--الصور النقطية غير متزامنة للأداء. إذا كنت تريد الوصول إلى صورة نقطية من أكثر من مؤشر ترابط واحد، فيجب عليك توفير المزامنة. ومع ذلك، يمكنك الوصول إلى صورة نقطية غير قابلة للتغيير من عدة سلاسل رسائل، طالما أنك تلتزم بواجهة ImmutableBitmapDataProvider .
تستخدم العديد من التطبيقات Kryo للتسلسل/إلغاء التسلسل. يمكن للمرء استخدام الصور النقطية Roaring مع Kryo بكفاءة بفضل مُسلسل مخصص (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 Bitmaps قد تم تصميمه مع وضع حالة 32 بت في الاعتبار، إلا أن لدينا امتدادات للأعداد الصحيحة 64 بت. نحن نقدم فئتين لهذا الغرض: Roaring64NavigableMap و Roaring64Bitmap .
تعتمد Roaring64NavigableMap على شجرة تقليدية ذات لون أحمر وأسود. المفاتيح عبارة عن أعداد صحيحة 32 بت تمثل أهم 32 بت من العناصر بينما قيم الشجرة عبارة عن صور نقطية Roaring 32 بت. تمثل الصور النقطية Roaring ذات 32 بت البتات الأقل أهمية لمجموعة من العناصر.
يعتمد أسلوب Roaring64Bitmap الأحدث على بنية بيانات ART للاحتفاظ بزوج المفتاح/القيمة. يتكون المفتاح من أهم 48 بت من العناصر بينما القيم عبارة عن حاويات Roaring ذات 16 بت. وهي مستوحاة من شجرة الجذر التكيفية: الفهرسة الفنية لقواعد بيانات الذاكرة الرئيسية بواسطة 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 );تم تحديد تسلسل الصور النقطية 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 );يستخدم تنسيق التسلسل القليل من ترتيب البايت النهائي.
احصل على جافا
سيتم تجميع ./gradlew assemble
سيقوم ./gradlew build بتجميع اختبارات الوحدة وتشغيلها
./gradlew test سيقوم بإجراء الاختبارات
./gradlew :roaringbitmap:test --tests TestIterators.testIndexIterator4 يقوم بتشغيل الاختبار 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).
في الملفات المتسلسلة، يتم تخصيص جزء من البايتات الأربعة الأولى لـ "ملف تعريف الارتباط" الذي يعمل على الإشارة إلى تنسيق الملف.
إذا حاولت إلغاء تسلسل صورة نقطية أو تعيينها من البيانات التي تحتوي على "ملف تعريف ارتباط" غير معروف، فسيقوم الكود بإحباط العملية والإبلاغ عن خطأ.
سوف تحدث هذه المشكلة لجميع المستخدمين الذين قاموا بإجراء تسلسل للصور النقطية 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.
