有人可以向我解释一下这个 GetCardinality 方法在做什么吗？

Question

我一直在研究 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;
    }

Answer 1

在_bitsSetArray256阵列被初始化与值，使得_bitsSetArray256[n]包含n的二进制表示设定的比特数，对于n 0..255。

例如，_bitsSetArray256[13]等于3，因为13在二进制是1101它含有3- 1s。

在这样做的目的是，它的速度远远预先计算这些值，并将其储存，而不是每次（或按需）给他们锻炼身体。它不象中的13二进制表示1s的数量正在不断将改变，毕竟：）

在for循环中，我们通过uints的阵列循环。 A C＃uint是一个32位的数量，即，由4个字节。我们的查找表告诉我们有多少位在字节中设定的，所以我们必须处理四个字节。在count +=线的位操作提取每个的四个字节，然后从查找阵列获取其比特计数。对于所有四个字节相加的比特计数给出了uint作为一个整体的比特计数。

于是给定一个BitArray，此函数挖入uint[] m_array构件，然后返回在其中的uints的二进制表示设置的位的总数量。

Answer 2

我只是想为我们这些使用 Lucene.net 开发我们自己的 Faceting 版本的人发布一篇关于 bitArrays 的有用文章。看： http://dotnetperls.com/precompulated-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;
   }