конвертировать bitarray в set
Как конвертировать 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}
Набор представляет собой массив присвоенных 32-битных целых чисел (uint32_t). Оба вида набора являются приемлемыми.
Bitarray является непрерывным в памяти. Первый бит bitarray имеет правильное выравнивание для simd. Сейчас я использую пользовательский распределитель памяти с std :: vector для хранения bitarray. 1 бит в памяти на 1 бит в битарре.
Благодарю.
Обновить:
Как определить и работать с массивом битов в C?
gmpy использует функцию scan1 библиотека gmp. Scan1, кажется, найти первый набор, как в Википедии Вот
Решение
Если я понимаю ваш вопрос:
for (int i = 0; i < 750000; ++i) {
if (bitarray_has(bitarray, i)) {
set_of_numbers.push_back(i);
}
}
Я не верю в ходьбу bitarray будет особенно медленным, но push_back() можно сделать быстрее, если вы знаете, сколько элементов будет создано. Тогда вы можете использовать reserve() предварительно выделить память.
Другие решения
код:
#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 -O3 code.cpp -lrt)
...
timing per cycle: 0.000739613
print result
0,0008 секунд для преобразования 768000 бит для установки. Но в каждом цикле есть как минимум 10 000 массивов по 768 000 бит. Это 8 секунд за цикл. Это медленно.