113 template<
typename TM>
116 for (
typename TM::iterator it = id_map.begin();
120 typename TM::mapped_type mp = it->second;
178 void get_vector(
unsigned id, std::vector<unsigned>& vect)
const;
188 map_type::const_iterator it = idx_.find(
id);
189 if (it != idx_.end())
192 vect.resize(vaddr.
size+1);
193 vect[0] = sv_storage1_.get(
id);
194 for (
unsigned j = 1; j < vect.size(); ++j)
196 unsigned a = sv_storage_.get(j + vaddr.
offset - 1);
197 a += (vect[j-1] + 1);
219 unsigned method = rand() % 5;
222 unsigned seed_id = unsigned(rand()) %
max_size;
233 unsigned seed_id = unsigned(rand()) %
max_size;
234 unsigned id = seed_id;
249 unsigned id = unsigned(rand()) %
max_size;
271 std::cerr <<
"Warning. Empty vector generated!" << std::endl;
274 bvi.
idx_[i] = ap.release();
283 size_t mem_total = 0;
284 for (bv_index::map_type::const_iterator it = bvi.
idx_.begin();
285 it != bvi.
idx_.end();
288 const TBVector* mp = it->second;
294 mem_total +=
sizeof(
void*);
305 size_t mem_total = 0;
306 std::vector<unsigned char> buf;
317 for (bv_index::map_type::const_iterator it = bvi.
idx_.begin();
318 it != bvi.
idx_.end();
321 unsigned id = it->first;
322 const TBVector* bvp = it->second;
336 vbuf.resize(bvs_size);
337 ::memcpy(vbuf.data(), buf.data(), bvs_size);
339 mem_total += bvs_size;
341 mem_total +=
sizeof(std::vector<unsigned char>::size_type);
352 throw std::runtime_error(
"deserialization check failed");
367 size_t mem_total = 0;
369 for (bv_index::map_type::const_iterator it = bvi.
idx_.begin();
370 it != bvi.
idx_.end();
373 unsigned id = it->first;
374 const TBVector* bvp = it->second;
376 unsigned count = bvp->
count();
387 sizeof(vect_index::buffer_type::value_type) * vect.size() +
388 sizeof(vect_index::buffer_type::size_type);
395 void bv2delta(
const TBVector& bv, std::vector<unsigned>& vect)
408 for (
size_t k = vect.size()-1; k >= 1; --k)
410 vect[k] -= vect[k-1];
421 size_t mem_total = 0;
423 std::vector<unsigned> vect;
427 for (bv_index::map_type::const_iterator it = bvi.
idx_.begin();
428 it != bvi.
idx_.end();
431 unsigned id = it->first;
432 const TBVector* bvp = it->second;
439 for (
unsigned k = 1; k < vect.size(); ++k)
443 delta_map.push_back(std::make_pair(sum,
id));
450 std::sort(delta_map.begin(), delta_map.end());
451 if (delta_map.size() != bvi.
idx_.size())
453 throw std::runtime_error(
"delta map size is incorrect");
457 for (
unsigned j = 0; j < delta_map.size(); ++j)
459 unsigned id = delta_map[j].second;
461 bv_index::map_type::const_iterator it = bvi.
idx_.find(
id);
462 if (it == bvi.
idx_.end())
464 const TBVector& bv = *(it->second);
471 vaddr.
size = (unsigned)(vect.size() - 1);
478 sv_pos += vaddr.
size;
481 sv_idx.
idx_[id] = vaddr;
487 sparse_vect_index::sparse_vector_type::statistics st;
491 mem_total += st.memory_used;
493 mem_total += st.memory_used;
497 for (bv_index::map_type::const_iterator it = bvi.
idx_.begin();
498 it != bvi.
idx_.end();
501 unsigned id = it->first;
502 const TBVector* bvp = it->second;
513 std::vector<unsigned> svect;
515 if (svect.size() != vect.size())
517 std::cerr <<
"Size check failed! id = " <<
id 518 <<
"size() = " << svect.size()
520 throw std::runtime_error(
"sparse vector content check failed");
523 for (
unsigned k = 0; k < vect.size(); ++k)
525 if (vect[k] != svect[k])
527 std::cerr <<
"SV content check failed! id = " <<
id 528 <<
" i=" << k << std::endl;
529 for (
unsigned h = 0; h < vect.size(); ++h)
531 std::cout <<
"[" << vect[h] <<
"=" << svect[h] <<
"], ";
533 std::cout << std::endl;
534 throw std::runtime_error(
"sparse vector content check failed");
560 for (bv_index::map_type::const_iterator it = bvi.
idx_.begin();
561 it != bvi.
idx_.end();
564 const TBVector* bvp = it->second;
573 std::vector<unsigned> result_set;
579 result_set.resize(0);
584 bv_index::map_type::const_iterator it = bvi.
idx_.find(
id);
585 if (it == bvi.
idx_.end())
587 const TBVector& bv = *(it->second);
598 result_set.push_back(*en);
623 for (bvs_index::map_type::const_iterator it = bvs.
idx_.begin();
624 it != bvs.
idx_.end();
628 if (svect.size() == 0)
630 throw std::runtime_error(
"empty buffer error");
632 const unsigned char* buf = it->second.data();
642 std::vector<unsigned> result_set;
648 result_set.resize(0);
653 bvs_index::map_type::const_iterator it = bvs.
idx_.find(
id);
654 if (it == bvs.
idx_.end())
657 const unsigned char* buf = it->second.data();
668 result_set.push_back(*en);
683 for (vect_index::map_type::const_iterator it = vecti.
idx_.begin();
684 it != vecti.
idx_.end();
688 if (vect.size() == 0)
690 throw std::runtime_error(
"empty buffer error");
702 std::vector<unsigned> result_set;
708 result_set.resize(0);
713 vect_index::map_type::const_iterator it = vecti.
idx_.find(
id);
714 if (it == vecti.
idx_.end())
729 result_set.push_back(*en);
744 std::vector<unsigned> vect;
747 for (sparse_vect_index::map_type::const_iterator it = svi.
idx_.begin();
748 it != svi.
idx_.end();
751 unsigned id = it->first;
763 std::vector<unsigned> result_set;
769 result_set.resize(0);
775 if (vect.size() == 0)
788 result_set.push_back(*en);
812 size_t bv_mem_total_MB = bv_mem_total / (1024*1024);
814 std::cout <<
"bm::bvector<> memory footprint = " 815 << bv_mem_total <<
" (" << bv_mem_total_MB <<
"MB)" 819 size_t bvs_mem_total_MB = bvs_mem_total / (1024*1024);
821 std::cout <<
"bm::bvector<> BLOB memory footprint = " 822 << bvs_mem_total <<
" (" << bvs_mem_total_MB <<
"MB)" 826 size_t vecti_mem_total_MB = vecti_mem_total / (1024*1024);
828 std::cout <<
"std::vector<unsigned> memory footprint = " 829 << vecti_mem_total <<
" (" << vecti_mem_total_MB <<
"MB)" 833 size_t svi_mem_total_MB = svi_mem_total / (1024*1024);
835 std::cout <<
"bm::sparse_vector<> memory footprint = " 836 << svi_mem_total <<
" (" << svi_mem_total_MB <<
"MB)" 848 std::cout << std::endl <<
"Performance (ops/sec):" << std::endl;
854 catch(std::exception& ex)
856 std::cerr << ex.what() << std::endl;
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
const unsigned result_set_cnt
static TBVector * construct_bvector()
static void speed_test_bv_index(const bv_index &bvi)
static size_t convert_bv2sv(const bv_index &bvi, sparse_vect_index &sv_idx)
size_t deserialize(BV &bv, const unsigned char *buf, bm::word_t *temp_block=0)
Bitvector deserialization from memory.
std::vector< unsigned char > buffer_type
static size_t convert_bv2bvs(const bv_index &bvi, bvs_index &bvs)
static size_t convert_bv2vect(const bv_index &bvi, vect_index &vidx)
void optimize(bm::word_t *temp_block=0, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, typename sparse_vector< Val, BV >::statistics *stat=0)
run memory optimization for all vector plains
const unsigned index_size
Sparse constainer sparse_vector<> for integer types using bit-transposition transform.
const unsigned bits_per_vect
void optimize(bm::word_t *temp_block=0, optmode opt_mode=opt_compress, statistics *stat=0)
Optimize memory bitvector's memory allocation.
Timing utilities for benchmarking (internal)
size_t max_serialize_mem
estimated maximum memory for serialization
const unsigned sample_cnt
Bit-vector serialization class.
void combine_or(BV &bv, It first, It last)
OR Combine bitvector and the iterable sequence.
compress blocks when possible (GAP/prefix sum)
void set(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
void clear(const size_type *ids, size_type ids_size, bm::sort_order so=bm::BM_UNKNOWN)
clear list of bits in this bitset
std::map< unsigned, buffer_type > map_type
int compare(const bvector< Alloc > &bvect) const
Lexicographical comparison with a bitvector.
void import(const value_type *arr, size_type arr_size, size_type offset=0)
Import list of elements from a C-style array.
#define BM_DECLARE_TEMP_BLOCK(x)
Statistical information about bitset's memory allocation details.
Algorithms for bvector<> (main include)
static void speed_test_vect_index(const vect_index &vecti)
sparse vector with runtime compression using bit transposition method
void get_vector(unsigned id, std::vector< unsigned > &vect) const
bm::sparse_vector< unsigned, bm::bvector<> > sparse_vector_type
std::vector< std::pair< uint64_t, unsigned > > delta_sum_map_type
size_t memory_used
memory usage for all blocks and service tables
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
static void generate_random_vector(TBVector *bv)
size_type serialize(const BV &bv, unsigned char *buf, size_t buf_size)
Bitvector serialization into memory block.
void byte_order_serialization(bool value)
Set byte-order serialization (for cross platform compatibility)
std::map< std::string, statistics > duration_map_type
test name to duration map
void destroy_map(TM &id_map)
static void generate_bv_index(bv_index &bvi)
const unsigned gap_levels
static void speed_test_bvs_index(const bvs_index &bvs)
static void print_duration_map(const duration_map_type &dmap, format fmt=ct_time)
size_type count() const
population cout (count of ON bits)
unsigned short gap_word_t
std::map< unsigned, TBVector * > map_type
bool valid() const
Checks if iterator is still valid.
std::map< unsigned, buffer_type > map_type
Serialization for sparse_vector<>
static size_type deserialize(bvector_type &bv, const unsigned char *buf, bm::word_t *temp_block, set_operation op=bm::set_OR, bool exit_on_one=false)
Deserialize bvector using buffer as set operation argument.
enumerator end() const
Returns enumerator pointing on the next bit after the last.
Utility class to collect performance measurements and statistics.
void add_repeats(unsigned inc)
static void bv2delta(const TBVector &bv, std::vector< unsigned > &vect)
std::map< unsigned, vect_addr > map_type
void gap_length_serialization(bool value)
Set GAP length serialization (serializes GAP levels of the original vector)
std::vector< unsigned int > buffer_type
void calc_stat(struct bm::bvector< Alloc >::statistics *st) const
Calculates bitvector statistics.
static const bm::gap_word_t _len[bm::gap_levels]
sparse_vector_type sv_storage_
Serialization / compression of bvector<>. Set theoretical operations on compressed BLOBs...
bm::chrono_taker::duration_map_type timing_map
Constant iterator designed to enumerate "ON" bits.
void resize(size_type new_size)
Change size of the bvector.
const unsigned benchmark_ops
sparse_vector_type sv_storage1_
static size_t calc_memory_footprint(const bv_index &bvi)
static void speed_test_sv_index(const sparse_vect_index &svi)
void set_compression_level(unsigned clevel)
Set compression level.
bool set_bit(size_type n, bool val=true)
Sets bit n.
Deserializer, performs logical operations between bit-vector and serialized bit-vector.
Algorithms for sparse_vector<>