جافا: متجه بت ضئيل

Question

هل هناك أي مكتبات معروفة في جافا لمتجهات البت المتفرقة؟

(وهل هناك إرشادات حول مدى تفوقها لاستخدامها مقابل. java.util.bitset?)

Answer 1

ال مكتبة كولت لديه مصفوفات متناثرة (1D ، 2D و 3D). كما أن لديها bitvector فعال ، مع 1 بت لكل قيمة ، بدلاً من 8 بتات boolean[] يفعل.

ومع ذلك ، فإن المصفوفات المتفرقة لا تدعم البتات مباشرة - فقط الزوجي والأشياء. يمكنك لف المصفوفة المزدوجة المتفرقة 1D عن طريق فهرس بتات إلى مؤشرات طويلة (bitIndex>>6) منذ كل فترة طويلة لديها 64 بت ، يتحول تم استرجاعها مزدوجة إلى قيمة طويلة خام ، واستخدم معالجة بت للوصول إلى أجزاء من الاسترداد لفترة طويلة. القليل من العمل ، ولكن في أي مكان بالقرب من تنفيذ المتجه المتفرق بنفسك. بمجرد أن يعمل Wrapper الخاص بك ، يمكنك تجنب تحويل الزوجي إلى Longs ، وتنفيذ مصفوفة 1D طويلة المتفرقة باستخدام رمز مصدر Colt المتاح للمصفوفة المتفرقة المزدوجة 1D كنقطة انطلاق.

تحرير: مزيد من المعلومات. لا تتطلب ناقلات/مصفوفات COLT أي ذاكرة في البداية للتخزين ، على افتراض أن جميع البتات (Longs) هي في البداية 0. تعيين قيمة لغير صفري تستهلك الذاكرة. يستمر تعيين القيمة إلى 0 في استهلاك الذاكرة ، على الرغم من أن الذاكرة لقيم الصفر يتم استردادها بشكل دوري.

إذا كانت البتات متفرقًا حقًا ، بحيث يكون لكل قيمة طويلة قيمة طويلة فقط مجموعة بت واحدة فقط ، فإن النفقات العامة للتخزين ستكون سيئة للغاية ، والتي تتطلب 64 بت لكل بتة حقيقية مخزنة. ولكن كما ذكرت أن الحالة النموذجية هي 20-40 ٪ متناثرة ، فإن النفقات العامة ستكون أقل بكثير ، مع عدم وجود تخزين ضائع إذا تم تجميع البتات في نطاقات ، على سبيل المثال من 0-100 ، ثم 1000-1100 ، و 2000-2200 ( القيم في Hex.) بشكل عام ، يتم تعيين 1/16 فقط من المنطقة إلى البتات ، ولكن التجميع يعني أن البتات مخزنة بدون مساحة ضائعة.

Answer 2

tl ؛ د. اذهب هنا تنفيذ bitset متناثر فعال في جافا

أعلم أن هذا سؤال "قديم" ، لكن لدي نفس السؤال الذي تعثرت فيه عبر هذا المنشور. في حين أن الإجابات جيدة ، لم أكن راضية في النهاية. بعد مزيد من الحفر ، أعتقد أنني صادفت الإجابة "النهائية" على مسألة bitsets المتناثرة في جافا.

في هذا العرض يناقش المؤلف ، الدكتور بروس هادون ، جهود الباحثين لإنشاء بديل عالي الكفاءة في الذاكرة وعالي الأداء لـ Java Bitset القياسي.

لقد ماتت الروابط الأصلية لعرضه التقديمي ، لكنني اتصلت بالدكتور هادون وحافظت على كل من الكود والعرض التقديمي هنا:

https://github.com/brettwooldridge/sparsebitset

لا أستطيع أن أوصي بقراءة هذا العرض التقديمي أكثر. إنها قراءة رائعة حتى لو لم تكن لديك مصلحة في مجموعات البتات المتفرقة ، فإن الأمر يتعلق بالطبيعة الحقيقية لحل المشكلات ...

الشرائح: هل هي علوم الكمبيوتر أو هندسة البرمجيات أو القرصنة؟

Answer 3

إذا كان ذلك متناثرًا حقًا (على سبيل المثال ، أقل من 1 ٪ من التحميل) ، فإن استخدام جدول التجزئة المفهرس بواسطة فهرس Bit ربما يكون جيدًا ؛ مجرد وجود أو عدم وجود الفهرس في الجدول هو كل ما تحتاج إلى معرفته إذا كان البت واحد أو صفر على التوالي.

إذا كانت الكثافة تزيد عن بضعة في المائة ، فيمكنك استخدام جدول التجزئة المفهرس بواسطة فهرس بت مقسومة على 64 ، وتخزين طويل الكلمات في جدول التجزئة الذي يحتوي على أجزاء فعلية. قليل ن تم تعيينه إذا كان جدول التجزئة يحتوي على قيمة الخامس ل int (n/64) و (V >> (N Mod 64)) و 1 صحيح.

تفترض كل من هذه الإجابات أنك تريد تحسين الوصول العشوائي إلى البتات. إذا كنت ترغب في تحسين التسلسل (أو أي وصول آخر) إلى البتات حسب الفهرس ، فقد ترغب في بنية مصفوفة متناثرة ، باستخدام نفس النوع من تمثيل متجه بتات منخفضة المستوى اعتمادًا على الكثافة المتوقعة. يرى مصفوفات متناثرة

Answer 4

بامكانك ان تحاول خريطة شجرة AVL Fastutil.

Answer 5

يستخدم Cern Colt على نطاق واسع لحساب المتجه والمصفوفة ، وله مصفوفات متناثرة ، ولكنه لا يستخدم على وجه التحديد لمتجهات بت.

http://acs.lbl.gov/software/colt/api/cern/colt/matrix/impl/sparseobjectmatrix1d.html

Answer 6

جدول التجزئة حيث يخبرك مجرد وجود أو غياب المفتاح بشيء؟ سيكون ذلك مجموعة هاش ثم! أنا متشكك في أداء مجموعة (حتى واحدة) على bitset. يعتمد الأمر حقًا على ما إذا كانت السرعة أو الذاكرة هي برنامج التشغيل الأساسي.

Answer 7

يمكنك تجربة مكتبة Javaewah.

https://code.google.com/p/javaewah/

اعتمادًا على مشكلتك ، قد يكون ذلك مناسبًا.

(يتم استخدامه بواسطة Apache Hive وغيرها.)