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

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

6 голосов
/ 18 ноября 2009

Я искал многогранный поиск с 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;
    }

Ответы [ 2 ]

11 голосов
/ 18 ноября 2009

Массив _bitsSetArray256 инициализируется такими значениями, что _bitsSetArray256[n] содержит количество битов, заданных в двоичном представлении n, для n в 0..255.

Например, _bitsSetArray256[13] равно 3, потому что 13 в двоичном виде это 1101, который содержит 3 1 с.

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

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

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

5 голосов
/ 27 февраля 2010

Я просто хотел опубликовать полезную статью о 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;
}
...