¿Puede alguien explicarme qué está haciendo este método GetCardinality?

Question

He estado buscando en la búsqueda facetada con Lucene.NET, he encontrado un ejemplo brillante here que explica una cantidad justa, aparte del hecho de que pasa por alto completamente la función que verifica la cardinalidad de los elementos en una matriz de bits.

¿Alguien puede darme un resumen de lo que está haciendo? Las principales cosas que no entiendo es por qué se crea el bitsSetArray tal como es, para qué se utiliza y cómo funcionan todas las sentencias if en el ciclo for.

Esto puede ser una gran pregunta, pero tengo que entender cómo funciona esto antes de que pueda siquiera pensar en usarlo en mi propio código.

Gracias

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

La matriz _bitsSetArray256 se inicializa con valores tales que _bitsSetArray256[n] contiene el número de bits puestos en la representación binaria de n, por n en 0..255.

Por ejemplo, _bitsSetArray256[13] es igual a 3, porque 13 en binario es 1101 que contiene 3 1 s.

La razón para hacer esto es que es mucho más rápido precomputar estos valores y almacenarlos, en lugar de tener que resolverlos cada vez (o bajo demanda). No es como el número de 1 s en la representación binaria de 13 es cada vez va a cambiar, después de todo :)

dentro del bucle for, que se recorre una serie de uint s. Una C# uint es una cantidad de 32 bits, es decir, compuesta por 4 bytes. Nuestra tabla de búsqueda nos dice cuántos bits se establecen en un byte, por lo que debemos procesar cada uno de los cuatro bytes. La manipulación de bits en la línea count += extrae cada uno de los cuatro bytes, luego obtiene su número de bits de la matriz de búsqueda. Si se suman los recuentos de bits para los cuatro bytes, se obtiene el recuento de bits del uint como un todo.

Así dado un BitArray, esta función se clava en el miembro uint[] m_array, a continuación, devuelve el número total de bits establecidos en la representación binaria de los uint s en el mismo.

Answer 2

Solo quería publicar un artículo útil sobre bitArrays para aquellos de nosotros que estamos desarrollando nuestras propias versiones de Faceting con Lucene.net. Ver: http://dotnetperls.com/precomputed-bitcount

Esta es una buena explicación sobre la manera más rápida de obtener la cardinalidad de los bits en un entero (que es una gran parte de lo que hace la muestra del código anterior).

Imlementando el método en el artículo en mi búsqueda facetada y algunos otros cambios simples, pude reducir el tiempo que tardó en obtener el conteo en ~ 65%. Las diferencias en qué:

1. Declaración de lo global _bitcount (así que no es creado por llamada)
2. Cambio de la de a foreach (ANT Profiler mostró un aumento de 25% aquí)

3. Implementening la mesa 65535 frente al 256 para desplazar 16 bits a la vez en lugar de 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; 
   }