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

Question

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

Может кто-нибудь подсказать мне, что он делает? Главное, чего я не понимаю, - это почему битовый набор создан таким, какой он есть, для чего он используется и как все операторы 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 1s.

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

В пределах for цикл, мы перебираем массив uints. 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. Изменение for на foreach (ANT Profiler показал здесь 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;
   }