누군가 나 에게이 getcardinality 방법이 무엇을하고 있는지 설명 할 수 있습니까?

StackOverflow https://stackoverflow.com/questions/1754560

  •  20-09-2019
  •  | 
  •  

문제

나는 Lucene.net과의 Faceted Search를 조사하고 있습니다. 훌륭한 예를 찾았습니다. 여기 비트 배열에서 항목의 카디널리티를 확인하는 기능을 완전히 간과한다는 사실 외에도 상당한 금액을 설명합니다.

누구든지 나에게하는 일을 줄 수 있습니까? 내가 이해하지 못하는 주요 사항은 BitssetArray가 그대로 생성되는 이유, 사용 된 내용 및 For Loop에서 모든 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;
    }
도움이 되었습니까?

해결책

그만큼 _bitsSetArray256 배열은 값으로 초기화됩니다 _bitsSetArray256[n] 이진 표현에 설정된 비트 수를 포함합니다. n, 을 위한 n 안에 0..255.

예를 들어, _bitsSetArray256[13] 이진의 13은 13과 같습니다 1101 3이 포함되어 있습니다 1에스.

이를 수행하는 이유는 매번 (또는 주문형) 작업을 수행하지 않고 이러한 값을 미리 컴퓨팅하고 저장하는 것이 훨씬 빠르기 때문입니다. 수와는 다릅니다 113의 이진 표현에서 S는 결국 변화 할 것입니다. :)

내 for 루프, 우리는 배열을 통해 반복됩니다 uint에스. AC# uint 32 비트 수량이며, 즉 4 바이트로 구성됩니다. 우리의 조회 테이블은 바이트에 몇 개의 비트가 설정되어 있는지 알려주므로 4 바이트 각각을 처리해야합니다. 비트 조작 count += 라인은 4 바이트 각각을 추출한 다음 조회 배열에서 비트 수를 얻습니다. 4 바이트 모두에 대한 비트 카운트를 함께 추가하면 비트 수가 uint 전체적으로.

그래서 BitArray,이 기능은 uint[] m_array 회원은 이진 표현에 설정된 총 비트 수를 반환합니다. uint거기에.

다른 팁

나는 단지 Lucene.net과 함께 우리 자신의 패싯 버전을 개발하는 사람들을위한 BitArray에 대한 유용한 기사를 게시하고 싶었습니다. 보다: http://dotnetperls.com/precomputed-bitcount

이것은 정수 (위의 코드 샘플이하는 것의 대부분)에서 ON 비트의 카디널리티를 얻는 패킷 방법에 대한 좋은 설명입니다.

내 측면 검색에서 기사의 방법을 모방하고 다른 간단한 변경 사항을 통해 ~ 65%의 수를 얻는 시간을 줄일 수있었습니다. 다음의 차이점 :

  1. _BITCOUNT Global 선언 (통화 당 생성되지 않음)
  2. Foreach를 변경합니다 (Ant Profiler는 여기서 25% 이득을 보여주었습니다)

  3. 65535 테이블을 구현 대 256에서 8 개보다 16 비트를 이동합니다.

    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;
}
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top