Birisi GetCardinality yönteminin ne yaptığını bana açıklayabilir mi?

Question

Lucene.NET ile çok yönlü bir araştırmayı inceledim, bir bit dizisindeki öğelerin ana hatlarını kontrol eden işleve tamamen göz ardı ettiğinden, makul bir miktarı açıklayan mükemmel bir örnek olan here'u buldum.

Herkes bana ne yaptığını anlatabilir mi? Anlamadığım ana şey, bitsSetArray'ın neden olduğu, niçin kullanıldığının ve for ifadelerinin for döngüsünde nasıl çalıştığıdır.

Bu büyük bir sorun olabilir, ancak bunu kendi kodumda kullanmayı düşünmeden önce bunun nasıl çalıştığını anlamanız gerekir.

sayesinde

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 dizi _bitsSetArray256[n]0..255 içinde n için n ikili gösterimi yer bit sayısını içerir, öyle ki değerleri ile başlatılır. Örneğin, _bitsSetArray256[13], 3 1 s içeren 1101 ikili olduğu için _bitsSetArray256[13], 3'e eşittir,.

Bunu yapmanın nedeni, her seferinde (veya isteğe bağlı olarak) çalışmak yerine, bu değerleri önceden hesaplamak ve depolamak için çok daha hızlı olmasıdır. Bu 13 ikili gösteriminde 1 s sayısını benzemiyor hiç for döngü içinde tüm :)

sonra değişecek, biz uint s bir dizi içinde döngü. Bir C# uint, 32 bitlik bir miktardır, yani 4 bayttır. Arama tablomuzda baytta kaç tane bit bulunduğumuzu bize söyleriz, bu yüzden dört bayttan her birini işlemeliz. count += satırındaki bit manipülasyonu, dört baytın her birini ayıklar ve ardından bit sayımını arama dizisinden alır. Dört bayt için bit sayılarının toplanması, bir bütün olarak uint için bit sayısını verir.

Yani BitArray önüne alındığında, bu fonksiyon daha sonra, içinde uint s ikili gösterimi yer toplam bit sayısını verir, uint[] m_array üyesinin karıştırmaya başlar.

Answer 2

Sadece Lucare.net ile kendi Facising sürümlerimizi geliştirenler için bitArrays hakkında yardımcı bir makale yayınlamak istedim. Bkz: http://dotnetperls.com/precomputed-bitcount

Bu, tamsayı üzerinde bitlerin asallığını (yukarıdaki kod örneğinin yaptıklarının büyük bir kısmı) elde etmek için hızlı yolun iyi bir açıklamasını ifade eder.

Makaledeki yöntemle yaptığım eşlemeli aramada ve diğer bazı basit değişikliklerde, sayımı% 65 oranında azalttı. içinde farklar:

1. değiştirilmesi _bitcount (böylece çağrı başına oluşturulmamış onun) küresel
2. bildirme foreach 65535 tabloyu Implementening

3. (ANT Profiler% 25 burada kazancı gösterdi) için vs 256'dan 16 bit yerine 8 bit vardiya.Parlak

   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; 
   }