svsample06.cpp
Go to the documentation of this file.
/*
Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
For more information please visit: http://bitmagic.io
*/
/** \example svsample06.cpp
Search/scan for elements in unordered, non-unique sparse vector
\sa bm::sparse_vector<>::const_iterator
\sa bm::sparse_vector<>::back_insert_iterator
\sa bm::sparse_vector_scanner
*/
/*! \file svsample06.cpp
\brief Example: sparse_vector<> scan search (non-ordered set functionality)
*/
#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm>
#include <random>
#include <stdexcept>
#include "bm.h"
#include "bmsparsevec.h"
#include "bmsparsevec_algo.h"
#include "bmtimer.h"
#include "bmundef.h" /* clear the pre-proc defines from BM */
using namespace std;
typedef bm::sparse_vector<bm::id_t, bm::bvector<> > sparse_vector_u32;
// ----------------------------------------------------
// Global parameters and types
// ----------------------------------------------------
const unsigned value_max = 1250000; // range of variants of events [0..max]
const unsigned test_size = 250000000; // vector size to generate
// -------------------------------------------
// Random generator
// -------------------------------------------
std::random_device rand_dev;
std::mt19937 gen(rand_dev());
std::uniform_int_distribution<> rand_dis(1, value_max); // generate uniform numebrs for [1, vector_max]
// timing storage for benchmarking
bm::chrono_taker<>::duration_map_type timing_map;
// Function to generate test vector set with some NULL values stored as a
// separate bit-bector
//
static
void generate_test_set(std::vector<unsigned>& vect,
bm::bvector<>& bv_null,
sparse_vector_u32& sv)
{
// back insert iterator is faster than random element access for sparse vector
//
sparse_vector_u32::back_insert_iterator bi(sv.get_back_inserter());
vect.resize(test_size);
bv_null.reset();
for (unsigned i = 0; i < test_size; ++i)
{
unsigned v = unsigned(rand_dis(gen));
vect[i] = v;
bv_null[i] = true; // not NULL(assigned) element
*bi = v; // push back an element to sparse vector
if (i % 64 == 0)
{
bi.add_null(5); // add 5 unassigned elements using back inserter
i += 5; // insert a small NULL plate (unassigned values)
}
} // for
}
// plain scan in std::vector<>, matching values are indexed
// in result bit-vector (subset projection)
// values are added, so multiple calls result in subset addition
static
void vector_search(const std::vector<unsigned>& vect,
const bm::bvector<>& bv_null,
unsigned value,
bm::bvector<>& bv_res)
{
bv_res.init(); // always use init() if set_bit_no_check()
for (size_t i = 0; i < vect.size(); ++i)
{
if (vect[i] == value)
bv_res.set_bit_no_check((bm::id_t)i);
} // for
bv_res &= bv_null; // correct results to only include non-NULL values
}
inline
void print_bvector(const bm::bvector<>& bv)
{
cout << "( count = " << bv.count() << ")" << ": [";
bm::bvector<>::enumerator en = bv.first();
for (; en.valid(); ++en)
cout << *en << ", ";
cout << "]" << endl;
}
int main(void)
{
try
{
// First, lets run, simple (printable) search case
//
{
sparse_vector_u32 sv(bm::use_null);
sv.set(2, 25);
sv.set(3, 35);
sv.set(7, 75);
sv.set(1000, 2000);
sv.set(256, 2001);
sv.set(77, 25);
bm::bvector<> bv_found; // search results vector
bm::sparse_vector_scanner<sparse_vector_u32> scanner; // scanner class
scanner.find_eq(sv, 25, bv_found); // seach for all values == 25
print_bvector(bv_found); // print results
scanner.invert(sv, bv_found); // invert search results to NOT EQ
print_bvector(bv_found); // print all != 25
}
std::vector<unsigned> vect;
bm::bvector<> bv_null;
sparse_vector_u32 sv(bm::use_null);
{
bm::chrono_taker<> tt1(cout, "0. test set generate ", 1, &timing_map);
generate_test_set(vect, bv_null, sv);
}
unsigned search_repeats = 500;
// generate a search vector for benchmarking
//
std::vector<unsigned> search_vect;
{
bm::bvector<> bv_tmp;
search_vect.reserve(search_repeats);
for (unsigned i = 0; i < search_repeats;)
{
bm::id_t idx = bm::id_t(rand_dis(gen));
if (!bv_tmp.test(idx)) // check if number is unique
{
search_vect.push_back(idx);
bv_tmp[idx] = 1;
++i;
}
}
}
// run benchmarks
//
bm::bvector<> bv_res1;
bm::bvector<> bv_res2;
bm::bvector<> bv_res3;
{
bm::chrono_taker tt1(cout, "1. std::vector<> scan ", search_repeats, &timing_map);
for (unsigned i = 0; i < search_repeats; ++i)
{
unsigned vs = search_vect[i];
vector_search(vect, bv_null, vs, bv_res1);
} // for
}
{
bm::chrono_taker tt1(cout, "2. sparse_vector<> scan ", search_repeats, &timing_map);
bm::sparse_vector_scanner<sparse_vector_u32> scanner;
scanner.find_eq(sv, search_vect.begin(), search_vect.end(), bv_res2);
}
// check jus in case if results look correct
if (bv_res1.compare(bv_res2) != 0)
{
std::cerr << "2. Search result mismatch!" << std::endl;
}
{
bv_res3.init(); // always init before calling "set_bit_no_check()"
bm::chrono_taker tt1(cout, "3. sparse_vector<>::const_iterator search ", search_repeats, &timing_map);
// prepare a unique search set
bm::bvector<> bv_search(bm::BM_GAP);
bm::combine_or(bv_search, search_vect.begin(), search_vect.end());
sparse_vector_u32::const_iterator it = sv.begin();
sparse_vector_u32::const_iterator it_end = sv.end();
for (; it != it_end; ++it)
{
unsigned v = *it;
if (bv_search.test(v))
{
bv_res3.set_bit_no_check(it.pos());
}
} // for
}
// paranoiya check
if (bv_res1.compare(bv_res3) != 0)
{
std::cerr << "3. Search result mismatch!" << std::endl;
}
bm::chrono_taker<>::print_duration_map(cout, timing_map, bm::chrono_taker<>::ct_ops_per_sec);
}
catch(std::exception& ex)
{
std::cerr << ex.what() << std::endl;
return 1;
}
return 0;
}
bm.h
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
bmsparsevec.h
Sparse constainer sparse_vector<> for integer types using bit-transposition transform.
bmsparsevec_algo.h
Algorithms for bm::sparse_vector.
bmtimer.h
Timing utilities for benchmarking (internal).
bmundef.h
pre-processor un-defines to avoid global space pollution (internal)
bm::bvector::enumerator
Constant iterator designed to enumerate "ON" bits.
Definition bm.h:603
bm::bvector::iterator_base::valid
bool valid() const BMNOEXCEPT
Checks if iterator is still valid.
Definition bm.h:283
bm::bvector
Bitvector Bit-vector container with runtime compression of bits.
Definition bm.h:115
bm::bvector::test
bool test(size_type n) const BMNOEXCEPT
returns true if bit n is set and false is bit n is 0.
Definition bm.h:1502
bm::bvector::count
size_type count() const BMNOEXCEPT
population count (count of ON bits)
Definition bm.h:2401
bm::bvector::reset
bvector< Alloc > & reset() BMNOEXCEPT
Clears every bit in the bitvector.
Definition bm.h:1267
bm::bvector::first
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
Definition bm.h:1871
bm::bvector::init
void init()
Explicit post-construction initialization. Must be caled to make sure safe use of *_no_check() method...
Definition bm.h:2280
bm::bvector::compare
int compare(const bvector< Alloc > &bvect) const BMNOEXCEPT
Lexicographical comparison with a bitvector.
Definition bm.h:3744
bm::bvector::end
enumerator end() const
Returns enumerator pointing on the next bit after the last.
Definition bm.h:1877
bm::bvector::set_bit_no_check
void set_bit_no_check(size_type n)
Set bit without checking preconditions (size, etc).
Definition bm.h:4646
bm::chrono_taker
Utility class to collect performance measurements and statistics.
Definition bmtimer.h:41
bm::chrono_taker::duration_map_type
std::map< std::string, statistics > duration_map_type
test name to duration map
Definition bmtimer.h:66
bm::chrono_taker::ct_ops_per_sec
@ ct_ops_per_sec
Definition bmtimer.h:60
bm::chrono_taker::print_duration_map
static void print_duration_map(TOut &tout, const duration_map_type &dmap, format fmt=ct_time)
Definition bmtimer.h:150
bm::sparse_vector_scanner
algorithms for sparse_vector scan/search
Definition bmsparsevec_algo.h:582
bm::sparse_vector_scanner::find_eq
void find_eq(const SV &sv, value_type value, bvector_type &bv_out)
find all sparse vector elements EQ to search value
Definition bmsparsevec_algo.h:3071
bm::sparse_vector_scanner::invert
void invert(const SV &sv, bvector_type &bv_out)
invert search result ("EQ" to "not EQ")
Definition bmsparsevec_algo.h:1661
bm::sparse_vector
succinct sparse vector with runtime compression using bit-slicing / transposition method
Definition bmsparsevec.h:87
bm::sparse_vector::set
void set(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
Definition bmsparsevec.h:1849
bm::sparse_vector::end
const_iterator end() const BMNOEXCEPT
Provide const iterator access to the end.
Definition bmsparsevec.h:575
bm::sparse_vector::get_back_inserter
back_insert_iterator get_back_inserter()
Provide back insert iterator Back insert iterator implements buffered insertion, which is faster,...
Definition bmsparsevec.h:588
bm::sparse_vector::begin
const_iterator begin() const BMNOEXCEPT
Provide const iterator access to container content.
Definition bmsparsevec.h:2310
bm::use_null
@ use_null
support "non-assigned" or "NULL" logic
Definition bmconst.h:230
bm::BM_GAP
@ BM_GAP
GAP compression is ON.
Definition bmconst.h:148
bm::combine_or
void combine_or(BV &bv, It first, It last)
OR Combine bitvector and the iterable sequence.
Definition bmalgo_impl.h:1080
bm::id_t
unsigned int id_t
Definition bmconst.h:38
rand_dev
std::random_device rand_dev
Definition sample11.cpp:51
timing_map
bm::chrono_taker ::duration_map_type timing_map
Definition sample11.cpp:46
gen
std::mt19937 gen(rand_dev())
rand_dev
std::random_device rand_dev
Definition svsample06.cpp:60
vector_search
static void vector_search(const std::vector< unsigned > &vect, const bm::bvector<> &bv_null, unsigned value, bm::bvector<> &bv_res)
Definition svsample06.cpp:106
main
int main(void)
Definition svsample06.cpp:133
print_bvector
void print_bvector(const bm::bvector<> &bv)
Definition svsample06.cpp:122
gen
std::mt19937 gen(rand_dev())
rand_dis
std::uniform_int_distribution rand_dis(1, value_max)
generate_test_set
static void generate_test_set(std::vector< unsigned > &vect, bm::bvector<> &bv_null, sparse_vector_u32 &sv)
Definition svsample06.cpp:73
test_size
const unsigned test_size
Definition xsample02.cpp:57
sparse_vector_u32
bm::sparse_vector< unsigned, bm::bvector<> > sparse_vector_u32
Definition xsample02.cpp:68
value_max
const unsigned value_max
Definition xsample02.cpp:56