누군가이 GetCardinality 메서드가하는 일을 설명 할 수 있습니까?

Question

나는 Lucene.NET으로 패싯 검색을 조사 해왔다. 비트 배열의 항목의 카디널리티를 완전히 검사하는 기능을 제외하고는 상당한 양을 설명하는 화려한 예제 인 here을 발견했다.

누구든지 저에게 무엇을하고 있는지 알려 줄 수 있습니까? 내가 이해하지 못하는 주된 이유는 bitsSetArray가 그대로 만들어진 이유, 사용되는 대상 및 for 문에서 모든 if 문이 작동하는 이유입니다.

이것은 큰 질문 일지 모르지만이 코드가 내 자신의 코드에서 사용되기 전에 어떻게 작동하는지 이해해야합니다.

감사

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]가 0..255n에 대한 n의 바이너리 표현에 설정된 비트 수를 포함하도록 값으로 초기화된다.

예를 들어 _bitsSetArray256[13]은 3과 같습니다. 이진수 13은 1101이고 3은입니다.

이렇게하는 이유는 매번 (또는 주문형) 작업을 수행하지 않고 이러한 값을 미리 계산하여 저장하는 것이 훨씬 빠르기 때문입니다. 결국 의 수가 13의 2 진수 표현에서 변경되는 것처럼 보이지 않습니다.

루프는 의 배열 내에서의 배열로 반복됩니다. C# uint은 32 비트 수량으로, 즉 4 바이트로 구성됩니다. 조회 테이블은 바이트에 몇 비트가 설정되어 있는지 알려주므로 4 바이트 각각을 처리해야합니다. count += 행의 비트 조작은 4 바이트 각각을 추출한 다음 조회 배열에서 비트 수를 가져옵니다. 4 바이트 모두에 대한 비트 수를 합하면 uint의 비트 수를 전체적으로 나타냅니다.

따라서이 함수는 uint[] m_array 멤버를 파고 uint의 이진 표현에 설정된 총 비트 수를 반환합니다.

Answer 2

Lucene.net으로 Faceting의 자체 버전을 개발중인 사람들을 위해 bitArrays에 대한 유용한 기사를 게시하고 싶습니다. 다음을 참조하십시오 : http://dotnetperls.com/precomputed-bitcount

위의 코드 샘플에서와 같이 정수로 온 비트의 카디널리티를 얻는 방법은 좋은 방법입니다.

내면 검색과 몇 가지 다른 간단한 변경 사항에 대한 기사에서 방법을 구현하면 시간을 단축 할 수 있었고 ~ 65 % 가량을 얻었습니다. 에 차이 :

1. 변경 _bitcount (그래서 호출 당 생성되지는) 글로벌
2. 선언 foreach 문에 65535 표를 Implementening

3. (ANT 프로파일 러는 25 % 여기에 이득을 보여 주었다)에 대한 vs는 16 비트 씩 8 비트가 아닌 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; 
   }