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>
typedef std::map<unsigned, unsigned>
map_u32;
static
void sort_map(map_u32& hmap,
const std::vector<unsigned>& vin)
{
for (auto v : vin)
{
hmap[v]++;
}
}
static
{
for (auto v : vin)
{
auto count = sv_out.
get(v);
sv_out.
set(v, count + 1);
}
}
static
void counting_sort(sparse_vector_u32& sv_out,
const std::vector<unsigned>& vin)
{
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
void build_histogram(sparse_vector_u32& sv_out,
const std::vector<unsigned>& vin)
{
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} ;
map_u32 h_map;
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;
map_u32 h_map;
{
}
{
}
{
}
{
}
{
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;
}