Может кто-нибудь объяснить мне, что делает этот метод GetCardinality?

Question

Я искал грандиозный поиск с Lucene.NET, я нашел блестящий пример here, который объясняет справедливую сумму, кроме того, что он полностью игнорирует функцию, которая проверяет мощность элементов в бит-массиве.

Может ли кто-нибудь дать мне сбежать от того, что он делает? Основные вещи, которые я не понимаю, - это то, почему bitSetArray создается как есть, для чего он используется и как все операторы if работают в цикле for.

Это может быть большой вопрос, но я должен понять, как это работает, прежде чем я могу даже подумать об использовании его в своем собственном коде.

Благодаря

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 s.

Причина этого заключается в том, что намного быстрее предварительно вычислить эти значения и сохранить их, вместо того, чтобы каждый раз выполнять их (или по требованию). Это не так, как число 1 с в двоичном представлении 13 когда-либо изменится, после того, как все :)

В цикле for мы перекручивание через массив uint с. A C# uint - это 32-битное количество, то есть составленное на 4 байта. Наша таблица поиска сообщает нам, сколько бит задано в байте, поэтому мы должны обработать каждый из четырех байтов. Бит-манипуляция в строке count += извлекает каждый из четырех байтов, а затем получает счетчик бит из массива поиска. Добавляя вместе количество бит для всех четырех байтов, подсчитывает количество бит для uint в целом.

Так дан в BitArray, эта функция выкапывает в uint[] m_array члена, а затем возвращает общее число бит, установленных в двоичном представлении uint с нем.

Answer 2

Я просто хотел опубликовать полезную статью о bitArrays для тех из нас, кто разрабатывает наши собственные версии Faceting с Lucene.net. См.: http://dotnetperls.com/precomputed-bitcount

Это хорошее объяснение на быстром пути, чтобы получить мощность бит на двоичном разряде в целочисленном размере (что является большой частью того, что делает вышеприведенный пример кода).

Изменив метод в статье в моем гранговом поиске и некоторые другие простые изменения, я смог сократить время, затраченное на получение счета на ~ 65%. Различия где:

1. декларирующих _bitcount глобального (поэтому его не создали за вызов)
2. Изменения для к Еогеаспу (ANT Profiler показал прирост на 25% здесь)

3. Implementening в 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; 
   }