xsample02.cpp File Reference

Example: sparse_vector<> used for counting sort / historgam construction. More...

#include <iostream>
#include <memory>
#include <map>
#include <vector>
#include <chrono>
#include <algorithm>
#include <random>
#include <stdexcept>
#include <future>
#include <thread>
#include "bm.h"
#include "bmtimer.h"
#include "bmsparsevec.h"
#include "bmundef.h"

Include dependency graph for xsample02.cpp:

Go to the source code of this file.

Typedefs
typedef bm::sparse_vector< unsigned, bm::bvector<> >	sparse_vector_u32
typedef std::map< unsigned, unsigned >	map_u32

Functions
std::mt19937	gen (rand_dev())
std::uniform_int_distribution	rand_dis (1, value_max)
static void	sort_map (map_u32 &hmap, const std::vector< unsigned > &vin)
static void	counting_sort_naive (sparse_vector_u32 &sv_out, const std::vector< unsigned > &vin)
static void	counting_sort (sparse_vector_u32 &sv_out, const std::vector< unsigned > &vin)
unsigned	counting_sort_subbatch (sparse_vector_u32 *sv_out, const std::vector< unsigned > *vin)
static void	counting_sort_parallel (sparse_vector_u32 &sv_out, const std::vector< unsigned > &vin)
static void	print_sorted (const sparse_vector_u32 &sv)
static void	print_sorted (const map_u32 &hmap)
static void	build_histogram (sparse_vector_u32 &sv_out, const std::vector< unsigned > &vin)
int	main (void)

Variables
const unsigned	value_max = 1250000
const unsigned	test_size = 250000000
std::random_device	rand_dev
bm::chrono_taker ::duration_map_type	timing_map

Detailed Description

Example: sparse_vector<> used for counting sort / historgam construction.

Definition in file xsample02.cpp.

Typedef Documentation

map_u32

typedef std::map<unsigned, unsigned> map_u32

Examples

xsample02.cpp.

Definition at line 69 of file xsample02.cpp.

sparse_vector_u32

typedef bm::sparse_vector<unsigned, bm::bvector<> > sparse_vector_u32

Examples

inv_list.cpp, rscsample01.cpp, rscsample02.cpp, rscsample03.cpp, rscsample04.cpp, rscsample05.cpp, rscsample06.cpp, svsample01.cpp, svsample02.cpp, svsample05.cpp, svsample06.cpp, svsample07.cpp, svsample07a.cpp, xsample02.cpp, xsample03.cpp, xsample07.cpp, and xsample09.cpp.

Definition at line 68 of file xsample02.cpp.

Function Documentation

build_histogram()

void build_histogram ( sparse_vector_u32 & sv_out, const std::vector< unsigned > & vin )

static

Examples

xsample02.cpp.

Definition at line 213 of file xsample02.cpp.

References bm::sparse_vector< Val, BV >::set().

Referenced by main().

counting_sort()

void counting_sort ( sparse_vector_u32 & sv_out, const std::vector< unsigned > & vin )

static

Examples

xsample02.cpp.

Definition at line 118 of file xsample02.cpp.

References bm::sparse_vector< Val, BV >::inc().

Referenced by main().

counting_sort_naive()

void counting_sort_naive ( sparse_vector_u32 & sv_out, const std::vector< unsigned > & vin )

static

Examples

xsample02.cpp.

Definition at line 98 of file xsample02.cpp.

References bm::sparse_vector< Val, BV >::get(), and bm::sparse_vector< Val, BV >::set().

Referenced by main().

counting_sort_parallel()

void counting_sort_parallel ( sparse_vector_u32 & sv_out, const std::vector< unsigned > & vin )

static

Examples

xsample02.cpp.

Definition at line 147 of file xsample02.cpp.

References counting_sort_subbatch(), bm::sparse_vector< Val, BV >::inc(), bm::sparse_vector< Val, BV >::merge(), and bm::use_null.

Referenced by main().

counting_sort_subbatch()

unsigned counting_sort_subbatch ( sparse_vector_u32 * sv_out, const std::vector< unsigned > * vin )

inline

Examples

xsample02.cpp.

Definition at line 130 of file xsample02.cpp.

References bm::sparse_vector< Val, BV >::inc().

Referenced by counting_sort_parallel().

gen()

std::mt19937 gen

(

rand_dev()

)

main()

int main

(

void

)

Definition at line 240 of file xsample02.cpp.

References BM_DECLARE_TEMP_BLOCK, build_histogram(), counting_sort(), counting_sort_naive(), counting_sort_parallel(), bm::chrono_taker< TOut >::ct_ops_per_sec, bm::sparse_vector< Val, BV >::equal(), gen(), bm::sparse_vector< Val, BV >::optimize(), bm::chrono_taker< TOut >::print_duration_map(), print_sorted(), rand_dis(), sort_map(), test_size, timing_map, and bm::use_null.

print_sorted() [1/2]

void print_sorted ( const map_u32 & hmap )

static

Definition at line 192 of file xsample02.cpp.

print_sorted() [2/2]

void print_sorted ( const sparse_vector_u32 & sv )

static

Examples

xsample02.cpp.

Definition at line 172 of file xsample02.cpp.

References bm::bvector< Alloc >::first(), bm::sparse_vector< Val, BV >::get(), and bm::base_sparse_vector< Val, BV, MAX_SIZE >::get_null_bvector().

Referenced by main().

rand_dis()

std::uniform_int_distribution rand_dis	(	1	,
		value_max	)

References value_max.

Referenced by main().

sort_map()

void sort_map ( map_u32 & hmap, const std::vector< unsigned > & vin )

static

Examples

xsample02.cpp.

Definition at line 81 of file xsample02.cpp.

Referenced by main().

Variable Documentation

rand_dev

std::random_device rand_dev

Definition at line 63 of file xsample02.cpp.

test_size

const unsigned test_size = 250000000

Examples

svsample06.cpp, xsample02.cpp, and xsample09.cpp.

Definition at line 57 of file xsample02.cpp.

Referenced by generate_test_set(), and main().

timing_map

bm::chrono_taker ::duration_map_type timing_map

Definition at line 73 of file xsample02.cpp.

value_max

const unsigned value_max = 1250000

Examples

svsample06.cpp, and xsample02.cpp.

Definition at line 56 of file xsample02.cpp.

Referenced by rand_dis().