6

私は 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;
    }
4

2 に答える 2

11

_bitsSetArray256配列は、 のバイナリ表現で設定されたビット数を含むような値で初期化_bitsSetArray256[n]さnれnます0..255。

たとえば、2 進数の 13 には 3 が含まれて_bitsSetArray256[13]いるため、3 に等しくなります。11011

これを行う理由は、毎回 (またはオンデマンドで) 計算するよりも、これらの値を事前に計算して保存する方がはるかに高速だからです。1結局のところ、13 の 2 進数表現の s の数が変わるわけではありません:)

forループ内では、 uints の配列をループしています。AC#uintは 32 ビット量、つまり 4 バイトで構成されます。ルックアップ テーブルは、1 バイトに設定されているビット数を示しているため、4 バイトのそれぞれを処理する必要があります。この行のビット操作はcount +=、4 バイトのそれぞれを抽出し、ルックアップ配列からそのビット カウントを取得します。4 バイトすべてのビット カウントを合計するuintと、全体のビット カウントが得られます。

したがって、 a が与えられたBitArray場合、この関数はメンバーを掘り下げ、その中の s のuint[] m_arrayバイナリ表現で設定されたビットの総数を返します。uint

于 2009-11-18T09:07:12.073 に答える
5

Lucene.net を使用して独自のバージョンの Faceting を開発している私たちのために、bitArray に関する役立つ記事を投稿したかっただけです。参照: http://dotnetperls.com/precomputed-bitcount

これは、整数内のオン ビットのカーディナリティを取得するための最速の方法に関する適切な説明です (これは、上記のコード サンプルが行うことの大部分です)。

ファセット検索で記事のメソッドを実装し、その他のいくつかの簡単な変更を加えることで、カウントを取得するのにかかる時間を最大 65% 短縮することができました。違いは次のとおりです。

  1. _bitcount グローバルを宣言する (呼び出しごとに作成されないため)
  2. for を foreach に変更 (ANT プロファイラーはここで 25% の増加を示しました)

  3. 一度に 8 ビットではなく 16 ビットをシフトするために、256 テーブルに対して 65535 テーブルを実装します。

    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;
}
于 2010-02-27T00:23:28.867 に答える