69typedef std::map<unsigned, unsigned>
map_u32;
102 auto count = sv_out.
get(v);
103 sv_out.
set(v, count + 1);
132 for (
size_t i = 0; i < vin->size(); i++)
154 for (
size_t i = 0; i < vin.size(); i++)
166 sv_out.
merge(sv_out2);
177 for (; en.valid(); ++en)
180 unsigned cnt = sv.
get(v);
181 for (
unsigned j = 0; j < cnt; ++j)
183 std::cout << v <<
", ";
186 std::cout << std::endl;
194 map_u32::const_iterator it = hmap.begin();
195 map_u32::const_iterator it_end = hmap.end();
197 for (; it != it_end; ++it)
199 unsigned v = it->first;
200 unsigned cnt = it->second;
201 for (
unsigned j = 0; j < cnt; ++j)
203 std::cout << v <<
", ";
206 std::cout << std::endl;
217 unsigned start = vin[0];
227 sv_out.
set(start, count);
228 start = v; count = 1;
233 sv_out.
set(start, count);
247 std::vector<unsigned> v {10, 1, 5, 4, 8, 8, 8} ;
263 std::sort(v.begin(), v.end());
266 if (!r_sv.
equal(h_sv))
268 std::cerr <<
"Error: Histogram comparison failed!" << std::endl;
277 std::vector<unsigned> v;
284 std::cout <<
"test vector generation ok" << std::endl;
314 std::sort(v.begin(), v.end());
323 std::cerr <<
"Error: Histogram comparison failed!" << std::endl;
326 if (!r_sv.
equal(p_sv))
328 std::cerr <<
"Error: Histogram comparison failed for parallel sort!" << std::endl;
334 std::cout << std::endl;
337 sparse_vector_u32::statistics st;
340 std::cout <<
"Sparse vector memory usage:" << st.memory_used / (1024*1024)<<
"MB" << std::endl;
341 std::cout <<
"vector<unsigned> usage:" << v.size() *
sizeof(v[0]) / (1024 * 1024) <<
"MB" << std::endl << std::endl;
348 catch(std::exception& ex)
350 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)
pre-processor un-defines to avoid global space pollution (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.
@ opt_compress
compress blocks when possible (GAP/prefix sum)
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
Utility class to collect performance measurements and statistics.
std::map< std::string, statistics > duration_map_type
test name to duration map
static void print_duration_map(TOut &tout, const duration_map_type &dmap, format fmt=ct_time)
succinct sparse vector with runtime compression using bit-slicing / 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 planes
@ use_null
support "non-assigned" or "NULL" logic
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)
std::random_device rand_dev
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)
bm::chrono_taker ::duration_map_type timing_map
std::mt19937 gen(rand_dev())
static void print_sorted(const sparse_vector_u32 &sv)
std::uniform_int_distribution rand_dis(1, value_max)