strsvsample09.cpp File Reference

Example: str_sparse_vector<> sorting example. More...

#include <iostream>
#include <string>
#include <vector>
#include <random>
#include <algorithm>
#include "bm.h"
#include "bmstrsparsevec.h"
#include "bmsparsevec_algo.h"
#include "bmdbg.h"
#include "bmtimer.h"
#include "bmundef.h"

Include dependency graph for strsvsample09.cpp:

Go to the source code of this file.

Typedefs
typedef bm::str_sparse_vector< char, bvector_type, 16 >	str_sv_type

Functions
static void	generate_string_set (vector< string > &str_vec, const unsigned max_coll=850000, unsigned repeat=220)
	generate collection of strings from integers with common prefixes ... and shuffle it
void	quicksort (str_sv_type &strsv, int first, int last)
	quick-sort
void	quicksort2 (str_sv_type &strsv, int first, int last)
	Faster variant of quicksort, uses different variant of pivot compare, with decompressed argument.
static void	insertion_sort (str_sv_type &str_sv, const vector< string > &str_vec)
	insertion sort for performance comnparison
int	main (void)

Variables
bm::chrono_taker ::duration_map_type	timing_map

Detailed Description

Example: str_sparse_vector<> sorting example.

Definition in file strsvsample09.cpp.

Typedef Documentation

str_sv_type

typedef bm::str_sparse_vector<char, bvector_type, 16> str_sv_type

Definition at line 54 of file strsvsample09.cpp.

Function Documentation

generate_string_set()

void generate_string_set ( vector< string > & str_vec, const unsigned max_coll = 850000, unsigned repeat = 220 )

static

generate collection of strings from integers with common prefixes ... and shuffle it

Definition at line 60 of file strsvsample09.cpp.

Referenced by main().

insertion_sort()

void insertion_sort ( str_sv_type & str_sv, const vector< string > & str_vec )

static

insertion sort for performance comnparison

Definition at line 155 of file strsvsample09.cpp.

References bm::str_sparse_vector< CharType, BV, STR_SIZE >::insert(), and bm::sparse_vector_scanner< SV, S_FACTOR >::lower_bound_str().

Referenced by main().

main()

int main

(

void

)

Definition at line 177 of file strsvsample09.cpp.

References bm::str_sparse_vector< CharType, BV, STR_SIZE >::begin(), BM_DECLARE_TEMP_BLOCK, bm::str_sparse_vector< CharType, BV, STR_SIZE >::calc_stat(), bm::chrono_taker< TOut >::ct_time, bm::str_sparse_vector< CharType, BV, STR_SIZE >::end(), bm::str_sparse_vector< CharType, BV, STR_SIZE >::equal(), generate_string_set(), bm::str_sparse_vector< CharType, BV, STR_SIZE >::get_back_inserter(), insertion_sort(), bm::str_sparse_vector< CharType, BV, STR_SIZE >::optimize(), bm::chrono_taker< TOut >::print_duration_map(), quicksort(), quicksort2(), bm::str_sparse_vector< CharType, BV, STR_SIZE >::remap(), bm::str_sparse_vector< CharType, BV, STR_SIZE >::size(), and timing_map.

quicksort()

void quicksort	(	str_sv_type &	strsv,
		int	first,
		int	last )

quick-sort

Examples

strsvsample09.cpp.

Definition at line 89 of file strsvsample09.cpp.

References bm::str_sparse_vector< CharType, BV, STR_SIZE >::compare(), quicksort(), and bm::str_sparse_vector< CharType, BV, STR_SIZE >::swap().

Referenced by main(), and quicksort().

quicksort2()

void quicksort2	(	str_sv_type &	strsv,
		int	first,
		int	last )

Faster variant of quicksort, uses different variant of pivot compare, with decompressed argument.

optimizations:

1. use of bm::str_sparse_vector<>::compare() function friendly for re-use of pivot element
2. tail call recursion eleimination

Examples

strsvsample09.cpp.

Definition at line 120 of file strsvsample09.cpp.

References bm::str_sparse_vector< CharType, BV, STR_SIZE >::compare(), bm::str_sparse_vector< CharType, BV, STR_SIZE >::get(), quicksort2(), and bm::str_sparse_vector< CharType, BV, STR_SIZE >::swap().

Referenced by main(), and quicksort2().

Variable Documentation

timing_map

bm::chrono_taker ::duration_map_type timing_map

Definition at line 175 of file strsvsample09.cpp.