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().