67typedef std::map<unsigned, unsigned>
map_u32;
100 auto count = sv_out.
get(v);
101 sv_out.
set(v, count + 1);
130 for (
size_t i = 0; i < vin->size(); i++)
152 for (
size_t i = 0; i < vin.size(); i++)
164 sv_out.
merge(sv_out2);
173 sparse_vector_u32::bvector_type::enumerator en = bv_null->
first();
175 for (; en.valid(); ++en)
178 unsigned cnt = sv.
get(v);
179 for (
unsigned j = 0; j < cnt; ++j)
181 std::cout << v <<
", ";
184 std::cout << std::endl;
192 map_u32::const_iterator it = hmap.begin();
193 map_u32::const_iterator it_end = hmap.end();
195 for (; it != it_end; ++it)
197 unsigned v = it->first;
198 unsigned cnt = it->second;
199 for (
unsigned j = 0; j < cnt; ++j)
201 std::cout << v <<
", ";
204 std::cout << std::endl;
215 unsigned start = vin[0];
225 sv_out.
set(start, count);
226 start = v; count = 1;
231 sv_out.
set(start, count);
245 std::vector<unsigned> v {10, 1, 5, 4, 8, 8, 8} ;
261 std::sort(v.begin(), v.end());
264 if (!r_sv.
equal(h_sv))
266 std::cerr <<
"Error: Histogram comparison failed!" << std::endl;
275 std::vector<unsigned> v;
282 std::cout <<
"test vector generation ok" << std::endl;
312 std::sort(v.begin(), v.end());
321 std::cerr <<
"Error: Histogram comparison failed!" << std::endl;
324 if (!r_sv.
equal(p_sv))
326 std::cerr <<
"Error: Histogram comparison failed for parallel sort!" << std::endl;
332 std::cout << std::endl;
335 sparse_vector_u32::statistics st;
336 r_sv.
optimize(tb, sparse_vector_u32::bvector_type::opt_compress, &st);
338 std::cout <<
"Sparse vector memory usage:" << st.memory_used / (1024*1024)<<
"MB" << std::endl;
339 std::cout <<
"vector<unsigned> usage:" << v.size() *
sizeof(v[0]) / (1024 * 1024) <<
"MB" << std::endl << std::endl;
346 catch(std::exception& ex)
348 std::cerr << ex.what() << std::endl;
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
#define BM_DECLARE_TEMP_BLOCK(x)
Sparse constainer sparse_vector<> for integer types using bit-transposition transform.
Timing utilities for benchmarking (internal)
const bvector_type * get_null_bvector() const BMNOEXCEPT
Get bit-vector of assigned values or NULL (if not constructed that way)
Bitvector Bit-vector container with runtime compression of bits.
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
Utility class to collect performance measurements and statistics.
static void print_duration_map(const duration_map_type &dmap, format fmt=ct_time)
std::map< std::string, statistics > duration_map_type
test name to duration map
sparse vector with runtime compression using bit transposition method
void inc(size_type idx)
increment specified element by one
value_type get(size_type idx) const BMNOEXCEPT
get specified element without bounds checking
bool equal(const sparse_vector< Val, BV > &sv, bm::null_support null_able=bm::use_null) const BMNOEXCEPT
check if another sparse vector has the same content and size
void set(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
sparse_vector< Val, BV > & merge(sparse_vector< Val, BV > &sv)
merge with another sparse vector using OR operation Merge is different from join(),...
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
@ use_null
support "non-assigned" or "NULL" logic
std::random_device rand_dev
bm::chrono_taker::duration_map_type timing_map
std::uniform_int_distribution rand_dis(1, int(vector_max))
std::mt19937 gen(rand_dev())
static void counting_sort_parallel(sparse_vector_u32 &sv_out, const std::vector< unsigned > &vin)
std::map< unsigned, unsigned > map_u32
static void counting_sort(sparse_vector_u32 &sv_out, const std::vector< unsigned > &vin)
static void build_histogram(sparse_vector_u32 &sv_out, const std::vector< unsigned > &vin)
bm::sparse_vector< unsigned, bm::bvector<> > sparse_vector_u32
static void counting_sort_naive(sparse_vector_u32 &sv_out, const std::vector< unsigned > &vin)
static void sort_map(map_u32 &hmap, const std::vector< unsigned > &vin)
unsigned counting_sort_subbatch(sparse_vector_u32 *sv_out, const std::vector< unsigned > *vin)
static void print_sorted(const sparse_vector_u32 &sv)