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);
194 for (
unsigned j = 1; j < vect.size(); ++j)
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();
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;
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;
376 unsigned count = bvp->
count();
387 sizeof(vect_index::buffer_type::value_type) * vect.size() +
388 sizeof(vect_index::buffer_type::size_type);
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;
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())
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;
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();
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())
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.
#define BM_DECLARE_TEMP_BLOCK(x)
Algorithms for bvector<> (main include)
Serialization / compression of bvector<>. Set theoretical operations on compressed BLOBs.
Sparse constainer sparse_vector<> for integer types using bit-transposition transform.
Algorithms for bm::sparse_vector.
Serialization for sparse_vector<>
Timing utilities for benchmarking (internal)
Constant iterator designed to enumerate "ON" bits.
bool valid() const BMNOEXCEPT
Checks if iterator is still valid.
Bitvector Bit-vector container with runtime compression of bits.
@ opt_compress
compress blocks when possible (GAP/prefix sum)
size_type count() const BMNOEXCEPT
population cout (count of ON bits)
void resize(size_type new_size)
Change size of the bvector.
void optimize(bm::word_t *temp_block=0, optmode opt_mode=opt_compress, statistics *stat=0)
Optimize memory bitvector's memory allocation.
bool set_bit(size_type n, bool val=true)
Sets bit n.
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
enumerator end() const
Returns enumerator pointing on the next bit after the last.
void clear(const size_type *ids, size_type ids_size, bm::sort_order so=bm::BM_UNKNOWN)
clear list of bits in this bitset
int compare(const bvector< Alloc > &bvect) const BMNOEXCEPT
Lexicographical comparison with a bitvector.
void calc_stat(struct bm::bvector< Alloc >::statistics *st) const BMNOEXCEPT
Calculates bitvector statistics.
Utility class to collect performance measurements and statistics.
static void print_duration_map(const duration_map_type &dmap, format fmt=ct_time)
void add_repeats(unsigned inc)
std::map< std::string, statistics > duration_map_type
test name to duration map
Deserializer, performs logical operations between bit-vector and serialized bit-vector.
size_type deserialize(bvector_type &bv, const unsigned char *buf, set_operation op, bool exit_on_one=false)
Deserialize bvector using buffer as set operation argument.
Bit-vector serialization class.
void gap_length_serialization(bool value) BMNOEXCEPT
Set GAP length serialization (serializes GAP levels of the original vector)
void set_compression_level(unsigned clevel) BMNOEXCEPT
Set compression level.
void byte_order_serialization(bool value) BMNOEXCEPT
Set byte-order serialization (for cross platform compatibility)
size_type serialize(const BV &bv, unsigned char *buf, size_t buf_size)
Bitvector serialization into memory block.
sparse vector with runtime compression using bit transposition method
value_type get(size_type idx) const BMNOEXCEPT
get specified element without bounds checking
void set(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
void import(const value_type *arr, size_type arr_size, size_type offset=0, bool set_not_null=true)
Import list of elements from a C-style array.
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
@ BM_GAP
GAP compression is ON.
size_t deserialize(BV &bv, const unsigned char *buf, bm::word_t *temp_block=0, const bm::bv_ref_vector< BV > *ref_vect=0)
Bitvector deserialization from a memory BLOB.
void combine_or(BV &bv, It first, It last)
OR Combine bitvector and the iterable sequence.
const unsigned gap_levels
unsigned short gap_word_t
bm::chrono_taker::duration_map_type timing_map
size_t max_serialize_mem
estimated maximum memory for serialization
size_t memory_used
memory usage for all blocks and service tables
Statistical information about bitset's memory allocation details.
std::map< unsigned, TBVector * > map_type
std::map< unsigned, buffer_type > map_type
std::vector< unsigned char > buffer_type
static const bm::gap_word_t _len[bm::gap_levels]
sparse_vector_type sv_storage1_
bm::sparse_vector< unsigned, bm::bvector<> > sparse_vector_type
std::map< unsigned, vect_addr > map_type
std::vector< std::pair< uint64_t, unsigned > > delta_sum_map_type
void get_vector(unsigned id, std::vector< unsigned > &vect) const
sparse_vector_type sv_storage_
std::map< unsigned, buffer_type > map_type
std::vector< unsigned int > buffer_type
static void generate_random_vector(TBVector *bv)
static void generate_bv_index(bv_index &bvi)
const unsigned index_size
static void speed_test_vect_index(const vect_index &vecti)
const unsigned benchmark_ops
const unsigned bits_per_vect
static void speed_test_bv_index(const bv_index &bvi)
static size_t calc_memory_footprint(const bv_index &bvi)
static void bv2delta(const TBVector &bv, std::vector< unsigned > &vect)
static size_t convert_bv2bvs(const bv_index &bvi, bvs_index &bvs)
void destroy_map(TM &id_map)
const unsigned result_set_cnt
static void speed_test_sv_index(const sparse_vect_index &svi)
static size_t convert_bv2vect(const bv_index &bvi, vect_index &vidx)
const unsigned sample_cnt
static size_t convert_bv2sv(const bv_index &bvi, sparse_vect_index &sv_idx)
static TBVector * construct_bvector()
static void speed_test_bvs_index(const bvs_index &bvs)