Вопрос по faceted-search, lucene.net, c# – Может кто-нибудь объяснить мне, что делает этот метод GetCardinality?

6

Я искал многогранный поиск с 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   ответа
5

кто разрабатывает наши собственные версии Faceting с Lucene.net. Видеть:http://dotnetperls.com/precomputed-bitcount

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

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

Объявление глобального _bitcount (поэтому он не создается за вызов)Изменение for для foreach (ANT Profiler показал здесь 25% прирост)

Реализация таблицы 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;
}
11

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

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

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

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

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

Молодец, спасибо АакашМ. Часть этого все еще идет мне на ум, но, по крайней мере, я понимаю концепцию метода и то, что он делает. John_

Похожие вопросы