Counting sort using bit-vector and sparse vector to build histogram of unsigned ints.Benchmark compares different histogram buiding techniques using BitMagic and std::sort()
Histogram construction, based on integer events is a common problem, this demo studies different approaches, potential for parallelization and other aspects.
#include <iostream>
#include <memory>
#include <map>
#include <vector>
#include <chrono>
#include <algorithm>
#include <random>
#include <stdexcept>
#include <future>
#include <thread>
using namespace std;
typedef std::map<unsigned, unsigned>
map_u32;
static
{
for (auto v : vin)
{
hmap[v]++;
}
}
static
{
for (auto v : vin)
{
auto count = sv_out.
get(v);
sv_out.
set(v, count + 1);
}
}
static
{
for(auto v : vin)
}
inline
{
for (size_t i = 0; i < vin->size(); i++)
{
auto v = (*vin)[i];
if ((v & 1) == 0)
}
return 0;
}
static
{
for (size_t i = 0; i < vin.size(); i++)
{
auto v = vin[i];
if (v & 1)
}
f1.wait();
}
static
{
for (; en.valid(); ++en)
{
unsigned v = *en;
unsigned cnt = sv.
get(v);
for (unsigned j = 0; j < cnt; ++j)
{
std::cout << v << ", ";
}
}
std::cout << std::endl;
}
static
{
map_u32::const_iterator it = hmap.begin();
map_u32::const_iterator it_end = hmap.end();
for (; it != it_end; ++it)
{
unsigned v = it->first;
unsigned cnt = it->second;
for (unsigned j = 0; j < cnt; ++j)
{
std::cout << v << ", ";
}
}
std::cout << std::endl;
}
static
{
if (vin.empty())
return;
unsigned start = vin[0];
unsigned count = 0;
for (auto v : vin)
{
if (v == start)
{
++count;
}
else
{
sv_out.
set(start, count);
start = v; count = 1;
}
}
if (count)
{
sv_out.
set(start, count);
}
}
{
try
{
{
std::vector<unsigned> v {10, 1, 5, 4, 8, 8, 8} ;
std::sort(v.begin(), v.end());
if (!r_sv.equal(h_sv))
{
std::cerr << "Error: Histogram comparison failed!" << std::endl;
return 1;
}
}
std::vector<unsigned> v;
{
}
std::cout << "test vector generation ok" << std::endl;
{
}
{
}
{
}
{
}
{
std::sort(v.begin(), v.end());
}
if (!r_sv.equal(h_sv) || !n_sv.equal(h_sv))
{
std::cerr << "Error: Histogram comparison failed!" << std::endl;
return 1;
}
if (!r_sv.equal(p_sv))
{
std::cerr << "Error: Histogram comparison failed for parallel sort!" << std::endl;
return 1;
}
{
std::cout << std::endl;
sparse_vector_u32::statistics st;
std::cout << "Sparse vector memory usage:" << st.memory_used / (1024*1024)<< "MB" << std::endl;
std::cout << "vector<unsigned> usage:" << v.size() * sizeof(v[0]) / (1024 * 1024) << "MB" << std::endl << std::endl;
}
}
catch(std::exception& ex)
{
std::cerr << ex.what() << std::endl;
return 1;
}
return 0;
}
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
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(),...
@ 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)