비트 맵을 변환하여

Question

변환하는 방법 bitarray를 C++로 빠르게 변환하는 방법은 무엇입니까? 실제 비트 배열에는 각각 750,000 비트가 있습니다.

예 1

bitarray: 01011111 
set: {0,1,2,3,4,5,7} 
or set: {1,3,4,5,6,7} 

예 2 :

bitarray: 0101 1111 0001 0001 
set: {0,4,8,9,10,11,12,14} 
or set: {1,3,4,5,6,7,11,15} 

세트 usigned 32 개 비트 정수 (uint32_t) 배열이다. 두 종류의 세트 모두 허용됩니다.

비트 배열은 메모리에서 연속적입니다. 비트 배열의 첫 번째 비트는 simd의 올바른 정렬을가집니다. 지금은 std :: vector와 함께 사용자 정의 메모리 할당자를 사용하여 비트 배열을 유지합니다. 비트 배열의 1 비트 당 1 비트의 메모리

감사합니다.

업데이트 :

this so question does the reverse

loop through bits in c

How to define and work with an array of bits in C?

gmpy는 gmp library SCAN1의 함수를 사용한다. SCAN1 내가 당신의 질문을 이해하면 위키 피 디아 here

Answer 1

에서와 같이 첫 세트를 찾을 것 : 나는 bitarray 도보 생각하지 않는다

for (int i = 0; i < 750000; ++i) { 
    if (bitarray_has(bitarray, i)) { 
     set_of_numbers.push_back(i); 
    } 
} 

특히 느린 것입니다,하지만 당신은 방법을 알고있는 경우 push_back() 빠르게 만들 수 있습니다 많은 요소가 생성됩니다. 그런 다음 reserve()을 사용하여 메모리를 사전 할당 할 수 있습니다.

Answer 2

번호 :

#include <iostream> 
#include <vector> 
#include <time.h> 

using namespace std; 

template <typename T> 
uint32_t bitarray2set(T& v, uint32_t * ptr_set){ 
    uint32_t i; 
    uint32_t base = 0; 
    uint32_t * ptr_set_new = ptr_set; 
    uint32_t size = v.capacity(); 
    for(i = 0; i < size; i++){ 
     find_set_bit(v[i], ptr_set_new, base); 
     base += 8*sizeof(uint32_t); 
    } 
    return (ptr_set_new - ptr_set); 
} 

inline void find_set_bit(uint32_t n, uint32_t*& ptr_set, uint32_t base){ 
    // Find the set bits in a uint32_t 
    int k = base; 
    while(n){ 
     if (n & 1){ 
      *(ptr_set) = k; 
      ptr_set++; 
     } 
     n = n >> 1; 
     k++; 
    } 
} 

template <typename T> 
void rand_vector(T& v){ 
    srand(time(NULL)); 
    int i; 
    int size = v.capacity(); 
    for (i=0;i<size;i++){ 
     v[i] = rand(); 
    } 
} 

template <typename T> 
void print_vector(T& v, int size_in = 0){ 
    int i; 

    int size; 
    if (size_in == 0){ 
     size = v.capacity(); 
    } else { 
     size = size_in; 
    } 
    for (i=0;i<size;i++){ 
     cout << v[i] << ' '; 
    } 
    cout << endl; 
} 

int main(void){ 
    const int test_size = 6000; 
    vector<uint32_t> vec(test_size); 
    vector<uint32_t> set(test_size*sizeof(uint32_t)*8); 
    rand_vector(vec); 
    //for (int i; i < 64; i++) vec[i] = -1; 
    //cout << "input" << endl; 
    print_vector(vec); 
    //cout << "calculate result" << endl; 

    int i; 
    int rep = 10000; 
    uint32_t res_size; 

    struct timespec tp_start, tp_end; 
    clock_gettime(CLOCK_MONOTONIC, &tp_start); 
    for (i=0;i<rep;i++){ 
     res_size = bitarray2set(vec, set.data()); 
    } 
    clock_gettime(CLOCK_MONOTONIC, &tp_end); 
    double timing; 
    const double nano = 0.000000001; 

    timing = ((double)(tp_end.tv_sec - tp_start.tv_sec) 
      + (tp_end.tv_nsec - tp_start.tv_nsec) * nano) /(rep); 

    cout << "timing per cycle: " << timing << endl; 
    cout << "print result" << endl; 
    //print_vector(set, res_size); 
} 

결과 (ICC -03 code.cpp의 -lrt 컴파일)

... 
timing per cycle: 0.000739613 
print result 

0.0008 초 768,000 비트 설정을 전환한다. 그러나 각주기에는 최소 10,000 개의 768,000 비트 어레이가 있습니다. 그것은 사이클 당 8 초입니다. 느리다.