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

StackOverflow https://stackoverflow.com/questions/1754560

  •  20-09-2019
  •  | 
  •  

Вопрос

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

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

Решение

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

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

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

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

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

Другие советы

Я просто хотел опубликовать полезную статью о битмассивах для тех из нас, кто разрабатывает собственные версии 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;
}
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top