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，对于nin 0..255。

例如，_bitsSetArray256[13]等于 3，因为二进制中的 131101包含 3 个1。

这样做的原因是预先计算这些值并存储它们要快得多，而不是每次都（或按需）计算它们。1毕竟，13 的二进制表示中的 s 的数量永远不会改变:)

在for循环中，我们正在循环一个 s 数组uint。AC#uint是一个 32 位的数量，即由 4 个字节组成。我们的查找表告诉我们在一个字节中设置了多少位，因此我们必须处理这四个字节中的每一个。行中的位操作count +=提取四个字节中的每一个，然后从查找数组中获取其位计数。将所有四个字节的位计数相加得到uint整体的位计数。

因此，给定 a BitArray，此函数挖掘uint[] m_array成员，然后返回其中 s 的二进制表示中设置的总位数uint。

于 2009-11-18T09:07:12.073 回答
5

我只是想为我们这些正在使用 Lucene.net 开发自己的 Faceting 版本的人发布一篇关于 bitArrays 的有用文章。请参阅：http ://dotnetperls.com/precomputed-bitcount

这是对获取整数中 on 位的基数的快速方法的一个很好的解释（这是上述代码示例的大部分内容）。

在我的分面搜索和其他一些简单的更改中实施文章中的方法，我能够将获取计数的时间减少约 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;
}
于 2010-02-27T00:23:28.867 回答