C++ : 반복자를 비트로 구성하기

Question

비트 맵을 가지고 있고 설정 비트 위치의 반복자를 반환하고 싶습니다. 지금은 전체 비트 맵을 걸 으면 비트가 설정되면 다음 위치를 제공합니다. 나는 이것이 더 효과적으로 수행 될 수 있다고 믿는다. 예를 들어, 비트의 각 조합에 대해 정적으로 배열을 만들고 싱글 바이트로 반환하고 위치 벡터를 반환한다. 배열이 너무 클 수 있기 때문에 이것은 전체 int에 대해 수행 될 수 없습니다. 그러나 더 좋은 해결책이있을 수 있습니까? 이것에 대한 스마트 알고리즘을 알고 있습니까?

Answer 1

몇 가지 아이디어를 제안 할 수 있습니다.

• 최신 CPU는 32 비트 또는 64 비트 워드에서 다음으로 설정된 비트를 찾는 데 필요한 지침을 제공합니다.
• 미리 준비된 효율적인 바이트 단위 미니 반복기에서 전체 비트 맵에 대한 반복기를 만드는 것에 대한 아이디어가 마음에 들었습니다. 이것은 정말 멋지 며 이전에는 본 적이 없었습니다.
• 비트 맵이 매우 희박한 경우 균형 트리와 같은 다른 형식으로 표현할 수 있습니다.이 트리에서는 반복 알고리즘이 잘 알려져 있습니다.
• 비트 맵이 드문 드문 있지만 밀도가 높은 영역 (이국적으로 들리지만이 상황이 발생한 상황이 발생했습니다)이있는 경우 작은 (32 비트 또는 64 비트) 비트 맵의 ​​균형 잡힌 트리를 사용하고 트리 및 단어의 비트에 대한 반복 알고리즘을 결합한 것입니다.
• 명시 적 트리의 메모리 오버 헤드를 피하려면 표준 힙 톱 알고리즘과 같이 암시적인 트리를 사용하십시오. 당신의 비트셋이 준비되고 돌연변이가 없을 것입니다. 레벨 (N + 1) [i] = 레벨 (N) [2 * i] | 레벨 (N) [2 * i + 1]이다. 이렇게하면 비트셋의 무인 영역을 빠르게 건너 뛸 수 있으며 반복은 일반 이진 트리를 반복하는 것과 비슷한 방식으로 수행됩니다. 당신은 바이트 등에서 시작하여 거주의 피라미드를 만들 수도 있습니다. 그것은 모두 당신의 비트셋이 얼마나 희소 한가에 달려 있습니다.
• 단어의 앞에 오는 0의 수를 찾기위한 잘 알려진 비트 트릭이 있습니다. 예를 들어 java 표준 라이브러리의 code을 참조하십시오.
• t.i 대신 수동 반복기를 사용하면 많은 성능을 얻을 수 있습니다. begin()과 operator ++() 대신에 F가 operator()를 갖는 비트 셋에 foreach (F) 함수를 제공하십시오. 조기 종료가있는 패시브 반복이 필요한 경우 F의 operator()를 종료가 요청되었는지 여부를 나타내는 부울 값을 반환합니다.

EDIT : 바이트에 대한 반복자를 준비하는 방법을 시도하는 것을 거부 할 수 없습니다. I는 다음과 같은 형태의 코드를 생성 C# 2.0로 코드 생성기를 썼다 I가 수행 코드의 성능을 갖는 임의의 50 % 채워진 바이트 배열 (10M 바이트)의 비트 카운트 성능을 비교

IEnumerable<int> bits(byte[] bytes) { 
    for(int i=0; i<bytes.Length; ++i) { 
     int oi=8*i; 
     switch(bytes[i]) { 
      .... 
      case 74: yield return oi+1; yield return oi+4; yield return oi+6; break; 
      .... 
     } 
    } 
} 

모두의 반복자를 사용하여 두 개의 루프로 구성하지 :

for (int i = 0; i < bytes.Length; ++i) { 
    byte b = bytes[i]; 
    for (int j = 7; j >= 0; --j) { 
     if (((int)b & (1 << j)) != 0) s++; 
    } 
} 

두 번째 코드는 그냥 1.66 배 빠른 첫 번째보다 (~ 1.5 초 대 ~ 2.5s). 제 생각에 좀 더 좁은 비트 배열은 첫 번째 코드가 두 번째 코드보다 성능이 우수 할 수도 있습니다.