Ai đó có thể giải thích cho tôi phương pháp GetCardinality này đang làm gì không?

Question

Tôi đã nhìn vào tìm kiếm mặt với Lucene.NET, tôi đã tìm thấy một ví dụ tuyệt vời here giải thích một số tiền hợp lý, ngoài thực tế là nó hoàn toàn nhìn thấy chức năng kiểm tra cardinality của các mục trong một mảng bit.

Có ai có thể cho tôi chạy trốn khỏi những gì nó đang làm không? Những điều chính tôi không hiểu là lý do tại sao bitSetArray được tạo ra vì nó là gì, nó được sử dụng như thế nào và tất cả các câu lệnh if hoạt động như thế nào trong vòng lặp for.

Đây có thể là một yêu cầu lớn nhưng tôi phải hiểu cách hoạt động này trước khi tôi thậm chí có thể nghĩ đến việc sử dụng nó trong mã của riêng tôi.

Cảm ơn

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

Mảng _bitsSetArray256 được khởi tạo với các giá trị như vậy mà _bitsSetArray256[n] chứa số bit thiết lập trong biểu diễn nhị phân của n, cho n trong 0..255.

Ví dụ: _bitsSetArray256[13] bằng 3, vì 13 trong nhị phân là 1101 có chứa 3 1 s.

Lý do để làm điều này là việc tính trước các giá trị này và lưu trữ chúng nhanh hơn rất nhiều so với việc phải tính toán chúng mỗi lần (hoặc theo yêu cầu). Nó không giống như số lượng của 1 s trong đại diện nhị phân của 13 là bao giờ sẽ thay đổi, sau khi tất cả :)

Trong vòng for vòng lặp, chúng tôi đang lặp qua một mảng uint s. C# uint là số lượng 32 bit, tức là được tạo thành 4 byte. Bảng tra cứu của chúng tôi cho chúng tôi biết có bao nhiêu bit được đặt trong một byte, vì vậy chúng tôi phải xử lý từng byte trong số bốn byte. Thao tác bit trong dòng count += trích xuất từng trong số bốn byte, sau đó lấy số bit của nó từ mảng tra cứu. Việc cộng các số bit cho tất cả bốn byte sẽ cho phép đếm bit cho tổng số uint.

Vì vậy, hãy cho một BitArray, chức năng này khai thác thành viên uint[] m_array, sau đó trả về tổng số bit được đặt trong biểu diễn nhị phân của uint s trong đó.

Answer 2

Tôi chỉ muốn đăng một bài viết hữu ích về bitArrays cho những người trong chúng ta đang phát triển phiên bản Faceting của riêng chúng ta với Lucene.net. Xem: http://dotnetperls.com/precomputed-bitcount

Đây là một giải thích tốt về cách fastet để lấy cardinality của các bit trên một số nguyên (phần lớn là những gì mẫu mã trên làm).

Imlementing phương pháp trong bài viết trong tìm kiếm mặt của tôi và một số thay đổi đơn giản khác tôi đã có thể cắt giảm thời gian nó đã nhận được số bởi ~ 65%. Sự khác biệt nơi ở:

1. Tuyên bố toàn cầu _bitcount (do đó nó không được tạo ra cho mỗi cuộc gọi)
2. Thay đổi cho đến foreach (ANT Profiler cho thấy mức tăng 25% ở đây)

3. Implementening bảng 65535 so với 256 để thay đổi 16 bit tại một thời điểm thay vì 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; 
   }