有人能解释一下这个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 1秒.

这样做的原因是预先计算这些值并存储它们要快得多,而不是每次(或按需)必须解决它们.这不像1是13的二进制表示中的s 的数量永远会改变,毕竟:)

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

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

Answer 2

我只想发布一篇关于bitArrays的有用文章给我们这些正在开发我们自己版本的Faceting with 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;
   }