هل يمكن لأحد أن يشرح لي ما هي طريقة getCardinality هذه؟

Question

لقد كنت أبحث في البحث مع Lucene.net ، لقد وجدت مثالًا رائعًا هنا وهو ما يفسر مبلغًا لا بأس به ، بصرف النظر عن حقيقة أنه يتجاهل تمامًا الوظيفة التي تتحقق من Cardinality للعناصر في مجموعة صغيرة.

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

قد يكون هذا أمرًا كبيرًا ، لكن يجب أن أفهم كيف يعمل هذا قبل أن أتمكن من التفكير في استخدامه في الكود الخاص بي.

شكرًا

public static int GetCardinality(BitArray bitArray)
    {
        var _bitsSetArray256 = new byte[] {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
        var array = (uint[])bitArray.GetType().GetField("m_array", BindingFlags.NonPublic | BindingFlags.Instance).GetValue(bitArray);
        int count = 0;

        for (int index = 0; index < array.Length; index ++)
            count += _bitsSetArray256[array[index] & 0xFF] + _bitsSetArray256[(array[index] >> 8) & 0xFF] + _bitsSetArray256[(array[index] >> 16) & 0xFF] + _bitsSetArray256[(array[index] >> 24) & 0xFF];

        return count;
    }

Answer 1

ال _bitsSetArray256 يتم تهيئة الصفيف بقيم مثل _bitsSetArray256[n] يحتوي على عدد البتات المحددة في التمثيل الثنائي لـ n, ، ل n في 0..255.

علي سبيل المثال، _bitsSetArray256[13] يساوي 3 ، لأن 13 في الثنائي هو 1101 الذي يحتوي على 3 1س.

والسبب في ذلك هو أنه من الأسرع بكثير أن يتمثل هذه القيم مسبقًا وتخزينها ، بدلاً من الاضطرار إلى العمل عليها في كل مرة (أو عند الطلب). ليس مثل عدد 1S في التمثيل الثنائي لـ 13 سيتغير ، بعد كل شيء :)

في حدود for حلقة ، نحن نحلق من خلال مجموعة من uintس. ac# uint هي كمية 32 بت ، أي مكونة لمدة 4 بايت. يخبرنا جدول البحث الخاص بنا عن عدد البتات التي يتم تعيينها في بايت ، لذلك يجب علينا معالجة كل من البايتات الأربعة. التلاعب بت في count += يستخلص الخط من كل من البايتات الأربعة ، ثم يحصل على عدد البتات من صفيف البحث. إضافة معا تعداد البت لجميع البايتات الأربعة يعطي عدد البتات ل uint ككل.

لذلك أعطى أ BitArray, ، هذه الوظيفة تحفر في uint[] m_array العضو ، ثم يعيد إجمالي عدد البتات المحددة في التمثيل الثنائي ل uintق.

Answer 2

أردت فقط أن أنشر مقالًا مفيدًا حول Bitarrays لأولئك منا الذين يقومون بتطوير إصداراتنا الخاصة من الوجه مع Lucene.net. يرى: http://dotnetperls.com/proced-bitcount

هذا استكشاف جيد على طريقة Fastet للحصول على Cardinality of On Bits في عدد صحيح (وهو الجزء الأكبر مما تفعله عينة الكود أعلاه).

إنني أرفع الطريقة في المقالة في بحثي المطبوخ وبعض التغييرات البسيطة الأخرى التي تمكنت من خفض الوقت الذي استغرقته في الحصول على العد بنسبة 65 ٪ تقريبًا. الاختلافات حيث في:

1. إعلان _bitcount Global (لذلك لم يتم إنشاؤه لكل مكالمة)
2. تغيير ل foreach (أظهرت النمل البذيئة زيادة بنسبة 25 ٪ هنا)

3. تنفيذ جدول 65535 مقابل 256 لتغيير 16 بت في وقت واحد بدلاً من 8.

   private static int[] _bitcounts = InitializeBitcounts();
   
   private static int GetCardinality(BitArray bitArray)
   {
       uint[] array = (uint[])bitArray.GetType().GetField("m_array", BindingFlags.NonPublic | BindingFlags.Instance).GetValue(bitArray);
   
       int count = 0;
       foreach (uint value in array)
       {
           count += _bitcounts[value & 65535] + _bitcounts[(value >> 16) & 65535];           
       }
       return count;
   }
   
   private static int[] InitializeBitcounts()
   {
       int[] bitcounts = new int[65536];
       int position1 = -1;
       int position2 = -1;
       //
       // Loop through all the elements and assign them.
       //
       for (int i = 1; i < 65536; i++, position1++)
       {
           //
           // Adjust the positions we read from.
           //
           if (position1 == position2)
           {
               position1 = 0;
               position2 = i;
           }
           bitcounts[i] = bitcounts[position1] + 1;
       }
       return bitcounts;
   }