Czy ktoś może mi wyjaśnić, co robi ta metoda GetCardinality?

Question

Zajmuję się wyszukiwaniem fasetkowym przy pomocy Lucene.NET, znalazłem genialny przykład here, który wyjaśnia sporą ilość, z wyjątkiem tego, że całkowicie pomija funkcję sprawdzającą liczność elementów w tablicy bitów.

Czy ktoś może mi dać spokój z tym, co robi? Najważniejsze rzeczy, których nie rozumiem, to dlaczego bitsSetArray jest tworzony tak jak jest, do czego jest używany i jak wszystkie instrukcje if działają w pętli for.

To może być duże pytanie, ale muszę zrozumieć, jak to działa, zanim będę mógł pomyśleć o użyciu go w moim własnym kodzie.

Dzięki

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

Tablica _bitsSetArray256 jest inicjalizowany tak, że z wartości _bitsSetArray256[n] zawiera liczby bitów ustawionych na binarnej reprezentacji n, na n w 0..255.

Na przykład: _bitsSetArray256[13] jest równy 3, ponieważ 13 w systemie binarnym to 1101, który zawiera 3 1 s.

Powodem tego jest to, że znacznie szybciej jest wstępnie obliczyć te wartości i przechowywać je, zamiast przerabiać je za każdym razem (lub na żądanie). To nie jest tak, numer 1 S w binarnej reprezentacji 13 to kiedykolwiek się zmieni, po tym wszystkim :)

Wewnątrz pętli for jesteśmy zapętlenie poprzez szereg uint s. C# uint jest 32-bitową ilością, czyli składa się z 4 bajtów. Nasza tablica przeglądowa mówi nam, ile bitów jest ustawionych w bajcie, więc musimy przetworzyć każdy z czterech bajtów. Manipulacja bitami w linii count += wyodrębnia każdy z czterech bajtów, a następnie pobiera liczbę bitów z tablicy odnośników. Łączenie liczby bitów dla wszystkich czterech bajtów daje liczbę bitów dla całości uint.

Wziąwszy pod uwagę w BitArray, funkcja kopie do członu uint[] m_array, a następnie powraca do całkowitej liczby bitów ustawionych na binarnej reprezentacji uint s w nich.

Answer 2

Po prostu chciałem opublikować pomocny artykuł na temat bitArrays dla tych z nas, którzy opracowują nasze własne wersje Faceting z Lucene.net. Zobacz: http://dotnetperls.com/precomputed-bitcount

To jest dobre wytłumaczenie na sposób fastet, aby uzyskać liczność na bitach w liczbie całkowitej (co jest większość tego, co robi powyższy przykładowy kod).

Zastanawiając się nad metodą w artykule w moim fasetowanym wyszukiwaniu i kilku innych prostych zmianach udało mi się skrócić czas potrzebny do uzyskania liczby o ~ 65%. Różnice gdzie:

1. deklarowania _bitcount globalny (tak jej nie stworzył za połączenie)
2. Zmiana na do foreach (ANT Profiler wykazało 25% zysku tutaj)

3. Implementening tabelę 65535 vs 256, aby przesuwać 16 bitów naraz, a nie 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; 
   }