Namespaces
	tlx::multisequence_partition_detail

	tlx::multisequence_selection_detail

	tlx::multiway_merge_detail

Enumerations
enum	MultiwayMergeAlgorithm { MWMA_LOSER_TREE, MWMA_LOSER_TREE_COMBINED, MWMA_LOSER_TREE_SENTINEL, MWMA_BUBBLE, MWMA_ALGORITHM_LAST, MWMA_ALGORITHM_DEFAULT = MWMA_LOSER_TREE_COMBINED }
	Different merging algorithms: bubblesort-alike, loser-tree variants, enum sentinel. More...

enum	MultiwayMergeSplittingAlgorithm { MWMSA_SAMPLING, MWMSA_EXACT, MWMSA_LAST, MWMSA_DEFAULT = MWMSA_EXACT }
	Different splitting strategies for sorting/merging: by sampling, exact. More...

Functions
template<typename InputIterator , typename OutputIterator , typename T , typename BinaryOperation = std::plus<T>>
OutputIterator	exclusive_scan (InputIterator first, InputIterator last, OutputIterator result, T init, BinaryOperation binary_op=BinaryOperation())
	Computes an exclusive prefix sum operation using binary_op the range [first, last), using init as the initial value, and writes the results to the range beginning at result. More...

template<typename ForwardIterator , typename Comparator >
bool	is_sorted_cmp (ForwardIterator first, ForwardIterator last, Comparator cmp)
	Checks if a range is sorted using a three-way Comparator (with memcmp() semantics). More...

template<typename ForwardIterator , typename Comparator >
ForwardIterator	is_sorted_until_cmp (ForwardIterator first, ForwardIterator last, Comparator cmp)
	Checks if a range is sorted using a three-way Comparator (with memcmp() semantics). More...

template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename OutputIterator , typename DiffType , typename Comparator >
OutputIterator	merge_advance (RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, DiffType max_size, Comparator comp)
	Merge routine being able to merge only the `max_size` smallest elements. More...

template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename OutputIterator , typename DiffType , typename Comparator >
OutputIterator	merge_advance_movc (RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, DiffType max_size, Comparator comp)
	Merge routine being able to merge only the `max_size` smallest elements. More...

template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename OutputIterator , typename DiffType , typename Comparator >
OutputIterator	merge_advance_usual (RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, DiffType max_size, Comparator comp)
	Merge routine being able to merge only the `max_size` smallest elements. More...

template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename Comparator , typename Combine = std::plus< typename std::iterator_traits<InputIterator1>::value_type>>
OutputIterator	merge_combine (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Comparator cmp=Comparator(), Combine combine=Combine())
	Merge two sorted ranges and add all items comparing equal. More...

template<typename RanSeqs , typename RankType , typename RankIterator , typename Comparator = std::less< typename std::iterator_traits< typename std::iterator_traits<RanSeqs> ::value_type::first_type>::value_type>>
void	multisequence_partition (const RanSeqs &begin_seqs, const RanSeqs &end_seqs, const RankType &rank, RankIterator begin_offsets, Comparator comp=Comparator())
	Splits several sorted sequences at a certain global rank, resulting in a splitting point for each sequence. More...

template<typename ValueType , typename RanSeqs , typename RankType , typename Comparator = std::less<ValueType>>
ValueType	multisequence_selection (const RanSeqs &begin_seqs, const RanSeqs &end_seqs, const RankType &rank, RankType &offset, Comparator comp=Comparator())
	Selects the element at a certain global rank from several sorted sequences. More...

template<typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename Comparator = std::less< typename std::iterator_traits< typename std::iterator_traits<RandomAccessIteratorIterator> ::value_type::first_type>::value_type>>
RandomAccessIterator3	multiway_merge (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, Comparator comp=Comparator(), MultiwayMergeAlgorithm mwma=MWMA_ALGORITHM_DEFAULT)
	Sequential multi-way merge. More...

template<bool Stable, bool Sentinels, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename Comparator = std::less< typename std::iterator_traits< typename std::iterator_traits<RandomAccessIteratorIterator> ::value_type::first_type>::value_type>>
RandomAccessIterator3	multiway_merge_base (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, Comparator comp=Comparator(), MultiwayMergeAlgorithm mwma=MWMA_ALGORITHM_DEFAULT)
	Sequential multi-way merging switch. More...

template<bool Stable, typename RandomAccessIteratorIterator , typename Comparator >
void	multiway_merge_exact_splitting (const RandomAccessIteratorIterator &seqs_begin, const RandomAccessIteratorIterator &seqs_end, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type total_size, Comparator comp, std::vector< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type > *chunks, const size_t num_threads)
	Splitting method for parallel multi-way merge routine: use multisequence selection for exact splitting. More...

template<bool Stable, typename RandomAccessIteratorIterator , typename Comparator >
void	multiway_merge_sampling_splitting (const RandomAccessIteratorIterator &seqs_begin, const RandomAccessIteratorIterator &seqs_end, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type total_size, Comparator comp, std::vector< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type > *chunks, const size_t num_threads, const size_t merge_oversampling)
	Splitting method for parallel multi-way merge routine: use sampling and binary search for in-exact splitting. More...

template<typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename Comparator = std::less< typename std::iterator_traits< typename std::iterator_traits<RandomAccessIteratorIterator> ::value_type::first_type>::value_type>>
RandomAccessIterator3	multiway_merge_sentinels (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, Comparator comp=Comparator(), MultiwayMergeAlgorithm mwma=MWMA_ALGORITHM_DEFAULT)
	Sequential multi-way merge with sentinels in sequences. More...

template<typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename Comparator = std::less< typename std::iterator_traits< typename std::iterator_traits<RandomAccessIteratorIterator> ::value_type::first_type>::value_type>>
RandomAccessIterator3	parallel_multiway_merge (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, Comparator comp=Comparator(), MultiwayMergeAlgorithm mwma=MWMA_ALGORITHM_DEFAULT, MultiwayMergeSplittingAlgorithm mwmsa=MWMSA_DEFAULT, size_t num_threads=std::thread::hardware_concurrency())
	Parallel multi-way merge routine. More...

template<bool Stable, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename Comparator = std::less< typename std::iterator_traits< typename std::iterator_traits<RandomAccessIteratorIterator> ::value_type::first_type>::value_type>>
RandomAccessIterator3	parallel_multiway_merge_base (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, Comparator comp=Comparator(), MultiwayMergeAlgorithm mwma=MWMA_ALGORITHM_DEFAULT, MultiwayMergeSplittingAlgorithm mwmsa=MWMSA_DEFAULT, size_t num_threads=std::thread::hardware_concurrency())
	Parallel multi-way merge routine. More...

template<typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename Comparator = std::less< typename std::iterator_traits< typename std::iterator_traits<RandomAccessIteratorIterator> ::value_type::first_type>::value_type>>
RandomAccessIterator3	parallel_multiway_merge_sentinels (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, Comparator comp=Comparator(), MultiwayMergeAlgorithm mwma=MWMA_ALGORITHM_DEFAULT, MultiwayMergeSplittingAlgorithm mwmsa=MWMSA_DEFAULT, size_t num_threads=std::thread::hardware_concurrency())
	Parallel multi-way merge routine with sentinels. More...

template<typename RandomAccessIt , typename RandomBits >
void	random_bipartition_shuffle (RandomAccessIt begin, RandomAccessIt end, size_t size_left_partition, RandomBits &urng)
	Similar to std::shuffle, but only generates a random bi-partition. More...

template<typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename Comparator = std::less< typename std::iterator_traits< typename std::iterator_traits<RandomAccessIteratorIterator> ::value_type::first_type>::value_type>>
RandomAccessIterator3	stable_multiway_merge (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, Comparator comp=Comparator(), MultiwayMergeAlgorithm mwma=MWMA_ALGORITHM_DEFAULT)
	Stable sequential multi-way merge. More...

template<typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename Comparator = std::less< typename std::iterator_traits< typename std::iterator_traits<RandomAccessIteratorIterator> ::value_type::first_type>::value_type>>
RandomAccessIterator3	stable_multiway_merge_sentinels (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, Comparator comp=Comparator(), MultiwayMergeAlgorithm mwma=MWMA_ALGORITHM_DEFAULT)
	Stable sequential multi-way merge with sentinels in sequences. More...

template<typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename Comparator = std::less< typename std::iterator_traits< typename std::iterator_traits<RandomAccessIteratorIterator> ::value_type::first_type>::value_type>>
RandomAccessIterator3	stable_parallel_multiway_merge (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, Comparator comp=Comparator(), MultiwayMergeAlgorithm mwma=MWMA_ALGORITHM_DEFAULT, MultiwayMergeSplittingAlgorithm mwmsa=MWMSA_DEFAULT, size_t num_threads=std::thread::hardware_concurrency())
	Stable parallel multi-way merge routine. More...

template<typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename Comparator = std::less< typename std::iterator_traits< typename std::iterator_traits<RandomAccessIteratorIterator> ::value_type::first_type>::value_type>>
RandomAccessIterator3	stable_parallel_multiway_merge_sentinels (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, Comparator comp=Comparator(), MultiwayMergeAlgorithm mwma=MWMA_ALGORITHM_DEFAULT, MultiwayMergeSplittingAlgorithm mwmsa=MWMSA_DEFAULT, size_t num_threads=std::thread::hardware_concurrency())
	Stable parallel multi-way merge routine with sentinels. More...

Variables
bool	parallel_multiway_merge_force_parallel = false
	setting to force parallel_multiway_merge() calls to run with parallel code More...

bool	parallel_multiway_merge_force_sequential = false
	setting to force all parallel_multiway_merge() calls to run sequentially More...

size_t	parallel_multiway_merge_minimal_k = 2
	minimal number of sequences for switching to parallel merging More...

size_t	parallel_multiway_merge_minimal_n = 1000
	minimal number of items for switching to parallel merging More...

size_t	parallel_multiway_merge_oversampling = 10
	default oversampling factor for parallel_multiway_merge More...

Detailed Description

Algorithms for iterators and ranges

Enumeration Type Documentation

◆ MultiwayMergeAlgorithm

enum MultiwayMergeAlgorithm

Different merging algorithms: bubblesort-alike, loser-tree variants, enum sentinel.

Enumerator
MWMA_LOSER_TREE
MWMA_LOSER_TREE_COMBINED
MWMA_LOSER_TREE_SENTINEL
MWMA_BUBBLE
MWMA_ALGORITHM_LAST
MWMA_ALGORITHM_DEFAULT

Definition at line 1165 of file multiway_merge.hpp.

◆ MultiwayMergeSplittingAlgorithm

enum MultiwayMergeSplittingAlgorithm

Different splitting strategies for sorting/merging: by sampling, exact.

Enumerator
MWMSA_SAMPLING
MWMSA_EXACT
MWMSA_LAST
MWMSA_DEFAULT

Definition at line 35 of file multiway_merge_splitting.hpp.

Function Documentation

◆ exclusive_scan()

OutputIterator tlx::exclusive_scan	(	InputIterator	first,
		InputIterator	last,
		OutputIterator	result,
		T	init,
		BinaryOperation	binary_op = `BinaryOperation()`
	)

Computes an exclusive prefix sum operation using binary_op the range [first, last), using init as the initial value, and writes the results to the range beginning at result.

The term "exclusive" means that the i-th input element is not included in the i-th sum.

Definition at line 30 of file exclusive_scan.hpp.

References gen_data::value.

◆ is_sorted_cmp()

bool tlx::is_sorted_cmp	(	ForwardIterator	first,
		ForwardIterator	last,
		Comparator	cmp
	)

Checks if a range is sorted using a three-way Comparator (with memcmp() semantics).

Definition at line 44 of file is_sorted_cmp.hpp.

References tlx::is_sorted_until_cmp().

◆ is_sorted_until_cmp()

ForwardIterator tlx::is_sorted_until_cmp	(	ForwardIterator	first,
		ForwardIterator	last,
		Comparator	cmp
	)

Checks if a range is sorted using a three-way Comparator (with memcmp() semantics).

Returns an iterator to the first items not in order.

Definition at line 26 of file is_sorted_cmp.hpp.

Referenced by tlx::is_sorted_cmp().

◆ merge_advance()

OutputIterator tlx::merge_advance	(	RandomAccessIterator1 &	begin1,
		RandomAccessIterator1	end1,
		RandomAccessIterator2 &	begin2,
		RandomAccessIterator2	end2,
		OutputIterator	target,
		DiffType	max_size,
		Comparator	comp
	)

Merge routine being able to merge only the max_size smallest elements.

The begin iterators are advanced accordingly, they might not reach end, in contrast to the usual variant. Static switch on whether to use the conditional-move variant.

Parameters

begin1	Begin iterator of first sequence.
end1	End iterator of first sequence.
begin2	Begin iterator of second sequence.
end2	End iterator of second sequence.
target	Target begin iterator.
max_size	Maximum number of elements to merge.
comp	Comparator.

Returns: Output end iterator.

Definition at line 158 of file merge_advance.hpp.

References tlx::merge_advance_movc().

Referenced by tlx::multiway_merge_detail::multiway_merge_3_combined(), and tlx::multiway_merge_base().

◆ merge_advance_movc()

OutputIterator tlx::merge_advance_movc	(	RandomAccessIterator1 &	begin1,
		RandomAccessIterator1	end1,
		RandomAccessIterator2 &	begin2,
		RandomAccessIterator2	end2,
		OutputIterator	target,
		DiffType	max_size,
		Comparator	comp
	)

Merge routine being able to merge only the max_size smallest elements.

The begin iterators are advanced accordingly, they might not reach end, in contrast to the usual variant. Specially designed code should allow the compiler to generate conditional moves instead of branches.

Parameters

begin1	Begin iterator of first sequence.
end1	End iterator of first sequence.
begin2	Begin iterator of second sequence.
end2	End iterator of second sequence.
target	Target begin iterator.
max_size	Maximum number of elements to merge.
comp	Comparator.

Returns: Output end iterator.

Definition at line 94 of file merge_advance.hpp.

Referenced by tlx::merge_advance().

◆ merge_advance_usual()

OutputIterator tlx::merge_advance_usual	(	RandomAccessIterator1 &	begin1,
		RandomAccessIterator1	end1,
		RandomAccessIterator2 &	begin2,
		RandomAccessIterator2	end2,
		OutputIterator	target,
		DiffType	max_size,
		Comparator	comp
	)

Merge routine being able to merge only the max_size smallest elements.

The begin iterators are advanced accordingly, they might not reach end, in contrast to the usual variant.

Parameters

begin1	Begin iterator of first sequence.
end1	End iterator of first sequence.
begin2	Begin iterator of second sequence.
end2	End iterator of second sequence.
target	Target begin iterator.
max_size	Maximum number of elements to merge.
comp	Comparator.

Returns: Output end iterator.

Definition at line 47 of file merge_advance.hpp.

◆ merge_combine()

OutputIterator tlx::merge_combine	(	InputIterator1	first1,
		InputIterator1	last1,
		InputIterator2	first2,
		InputIterator2	last2,
		OutputIterator	result,
		Comparator	cmp = `Comparator()`,
		Combine	combine = `Combine()`
	)

Merge two sorted ranges and add all items comparing equal.

Both ranges must be sorted using the three-way Comparator (with memcmp() semantics). Item pairs comparing equal (cmp returns 0) are combined together using a combine operator.

Warning: This method does not check if the ranges are sorted. Also make sure that the comparator does not work with unsigned types.

Definition at line 37 of file merge_combine.hpp.

Referenced by stats_data::operator+(), and stats_data::operator-().

◆ multisequence_partition()

void tlx::multisequence_partition	(	const RanSeqs &	begin_seqs,
		const RanSeqs &	end_seqs,
		const RankType &	rank,
		RankIterator	begin_offsets,
		Comparator	comp = `Comparator()`
	)

Splits several sorted sequences at a certain global rank, resulting in a splitting point for each sequence.

The sequences are passed via a sequence of random-access iterator pairs, none of the sequences may be empty. If there are several equal elements across the split, the ones on the left side will be chosen from sequences with smaller number.

Parameters

begin_seqs	Begin of the sequence of iterator pairs.
end_seqs	End of the sequence of iterator pairs.
rank	The global rank to partition at.
begin_offsets	A random-access sequence begin where the result will be stored in. Each element of the sequence is an iterator that points to the first element on the greater part of the respective sequence.
comp	The ordering functor, defaults to std::less<T>.

Definition at line 106 of file multisequence_partition.hpp.

References max(), min(), gen_data::N, and tlx::round_up_to_power_of_two().

Referenced by tlx::multiway_merge_exact_splitting(), and tlx::parallel_mergesort_detail::parallel_sort_mwms_pu().

◆ multisequence_selection()

ValueType tlx::multisequence_selection	(	const RanSeqs &	begin_seqs,
		const RanSeqs &	end_seqs,
		const RankType &	rank,
		RankType &	offset,
		Comparator	comp = `Comparator()`
	)

Selects the element at a certain global rank from several sorted sequences.

The sequences are passed via a sequence of random-access iterator pairs, none of the sequences may be empty.

Parameters

begin_seqs	Begin of the sequence of iterator pairs.
end_seqs	End of the sequence of iterator pairs.
rank	The global rank to partition at.
offset	The rank of the selected element in the global subsequence of elements equal to the selected element. If the selected element is unique, this number is 0.
comp	The ordering functor, defaults to std::less.

Definition at line 100 of file multisequence_selection.hpp.

References max(), min(), gen_data::N, and tlx::round_up_to_power_of_two().

◆ multiway_merge()

RandomAccessIterator3 tlx::multiway_merge	(	RandomAccessIteratorIterator	seqs_begin,
		RandomAccessIteratorIterator	seqs_end,
		RandomAccessIterator3	target,
		typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type	size,
		Comparator	comp = `Comparator()`,
		MultiwayMergeAlgorithm	mwma = `MWMA_ALGORITHM_DEFAULT`
	)

Sequential multi-way merge.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
target	Begin iterator out output sequence.
size	Maximum size to merge.
comp	Comparator.
mwma	MultiwayMergeAlgorithm set to use.

Returns: End iterator of output sequence.

Definition at line 1324 of file multiway_merge.hpp.

References tlx::multiway_merge_base().

◆ multiway_merge_base()

RandomAccessIterator3 tlx::multiway_merge_base	(	RandomAccessIteratorIterator	seqs_begin,
		RandomAccessIteratorIterator	seqs_end,
		RandomAccessIterator3	target,
		typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type	size,
		Comparator	comp = `Comparator()`,
		MultiwayMergeAlgorithm	mwma = `MWMA_ALGORITHM_DEFAULT`
	)

Sequential multi-way merging switch.

The decision if based on the branching factor and runtime settings.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
target	Begin iterator out output sequence.
size	Maximum size to merge.
comp	Comparator.
mwma	MultiwayMergeAlgorithm set to use.

Template Parameters

Stable	Stable merging incurs a performance penalty.
Sentinels	The sequences have a sentinel element.

Returns: End iterator of output sequence.

Definition at line 1198 of file multiway_merge.hpp.

References tlx::merge_advance(), tlx::multiway_merge_detail::multiway_merge_3_combined(), tlx::multiway_merge_detail::multiway_merge_4_combined(), tlx::multiway_merge_detail::multiway_merge_loser_tree(), tlx::MWMA_BUBBLE, tlx::MWMA_LOSER_TREE, tlx::MWMA_LOSER_TREE_COMBINED, and tlx::MWMA_LOSER_TREE_SENTINEL.

Referenced by tlx::multiway_merge(), tlx::multiway_merge_sentinels(), tlx::parallel_multiway_merge(), tlx::parallel_multiway_merge_sentinels(), tlx::parallel_mergesort_detail::parallel_sort_mwms_pu(), tlx::stable_multiway_merge(), tlx::stable_multiway_merge_sentinels(), tlx::stable_parallel_multiway_merge(), and tlx::stable_parallel_multiway_merge_sentinels().

◆ multiway_merge_exact_splitting()

void tlx::multiway_merge_exact_splitting	(	const RandomAccessIteratorIterator &	seqs_begin,
		const RandomAccessIteratorIterator &	seqs_end,
		typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type	size,
		typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type	total_size,
		Comparator	comp,
		std::vector< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type > *	chunks,
		const size_t	num_threads
	)

Splitting method for parallel multi-way merge routine: use multisequence selection for exact splitting.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
size	Maximum size to merge.
total_size	Total size of all sequences combined.
comp	Comparator.
chunks	Output subsequences for num_threads.
num_threads	Split the sequences into for num_threads.

Template Parameters

Stable Stable merging incurs a performance penalty.

Returns: End iterator of output sequence.

Definition at line 190 of file multiway_merge_splitting.hpp.

References tlx::multiway_merge_detail::equally_split(), tlx::multisequence_partition(), and SimpleVector< ValueType, Mode >::resize().

◆ multiway_merge_sampling_splitting()

void tlx::multiway_merge_sampling_splitting	(	const RandomAccessIteratorIterator &	seqs_begin,
		const RandomAccessIteratorIterator &	seqs_end,
		typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type	size,
		typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type	total_size,
		Comparator	comp,
		std::vector< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type > *	chunks,
		const size_t	num_threads,
		const size_t	merge_oversampling
	)

Splitting method for parallel multi-way merge routine: use sampling and binary search for in-exact splitting.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
size	Maximum size to merge.
total_size	Total size of all sequences combined.
comp	Comparator.
chunks	Output subsequences for num_threads.
num_threads	Split the sequences into for num_threads.
merge_oversampling	oversampling factor

Template Parameters

Stable Stable merging incurs a performance penalty.

Returns: End iterator of output sequence.

Definition at line 94 of file multiway_merge_splitting.hpp.

◆ multiway_merge_sentinels()

RandomAccessIterator3 tlx::multiway_merge_sentinels	(	RandomAccessIteratorIterator	seqs_begin,
		RandomAccessIteratorIterator	seqs_end,
		RandomAccessIterator3	target,
		typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type	size,
		Comparator	comp = `Comparator()`,
		MultiwayMergeAlgorithm	mwma = `MWMA_ALGORITHM_DEFAULT`
	)

Sequential multi-way merge with sentinels in sequences.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
target	Begin iterator out output sequence.
size	Maximum size to merge.
comp	Comparator.
mwma	MultiwayMergeAlgorithm set to use.

Returns: End iterator of output sequence.

Definition at line 1390 of file multiway_merge.hpp.

References tlx::multiway_merge_base().

◆ parallel_multiway_merge()

RandomAccessIterator3 tlx::parallel_multiway_merge	(	RandomAccessIteratorIterator	seqs_begin,
		RandomAccessIteratorIterator	seqs_end,
		RandomAccessIterator3	target,
		const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type	size,
		Comparator	comp = `Comparator()`,
		MultiwayMergeAlgorithm	mwma = `MWMA_ALGORITHM_DEFAULT`,
		MultiwayMergeSplittingAlgorithm	mwmsa = `MWMSA_DEFAULT`,
		size_t	num_threads = `std::thread::hardware_concurrency()`
	)

Parallel multi-way merge routine.

Implemented either using OpenMP or with std::threads, depending on if compiled with -fopenmp or not. The OpenMP version uses the implicit thread pool, which is faster when using this method often.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
target	Begin iterator out output sequence.
size	Maximum size to merge.
comp	Comparator.
mwma	MultiwayMergeAlgorithm set to use.
mwmsa	MultiwayMergeSplittingAlgorithm to use.
num_threads	Number of threads to use (defaults to all cores)

Template Parameters

Stable Stable merging incurs a performance penalty.

Returns: End iterator of output sequence.

Definition at line 229 of file parallel_multiway_merge.hpp.

References tlx::multiway_merge_base(), and tlx::parallel_multiway_merge_base().

◆ parallel_multiway_merge_base()

RandomAccessIterator3 tlx::parallel_multiway_merge_base	(	RandomAccessIteratorIterator	seqs_begin,
		RandomAccessIteratorIterator	seqs_end,
		RandomAccessIterator3	target,
		const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type	size,
		Comparator	comp = `Comparator()`,
		MultiwayMergeAlgorithm	mwma = `MWMA_ALGORITHM_DEFAULT`,
		MultiwayMergeSplittingAlgorithm	mwmsa = `MWMSA_DEFAULT`,
		size_t	num_threads = `std::thread::hardware_concurrency()`
	)

Parallel multi-way merge routine.

Implemented either using OpenMP or with std::threads, depending on if compiled with -fopenmp or not. The OpenMP version uses the implicit thread pool, which is faster when using this method often.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
target	Begin iterator out output sequence.
size	Maximum size to merge.
comp	Comparator.
mwma	MultiwayMergeAlgorithm set to use.
mwmsa	MultiwayMergeSplittingAlgorithm to use.
num_threads	Number of threads to use (defaults to all cores)

Template Parameters

Stable Stable merging incurs a performance penalty.

Returns: End iterator of output sequence.

Definition at line 68 of file parallel_multiway_merge.hpp.

References SimpleVector< ValueType, Mode >::begin(), SimpleVector< ValueType, Mode >::data(), SimpleVector< ValueType, Mode >::end(), tlx::join(), min(), tlx::MWMSA_SAMPLING, tlx::parallel_multiway_merge_force_parallel, tlx::parallel_multiway_merge_force_sequential, tlx::parallel_multiway_merge_minimal_k, tlx::parallel_multiway_merge_minimal_n, and tlx::parallel_multiway_merge_oversampling.

Referenced by tlx::parallel_multiway_merge(), tlx::parallel_multiway_merge_sentinels(), tlx::stable_parallel_multiway_merge(), and tlx::stable_parallel_multiway_merge_sentinels().

◆ parallel_multiway_merge_sentinels()

RandomAccessIterator3 tlx::parallel_multiway_merge_sentinels	(	RandomAccessIteratorIterator	seqs_begin,
		RandomAccessIteratorIterator	seqs_end,
		RandomAccessIterator3	target,
		const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type	size,
		Comparator	comp = `Comparator()`,
		MultiwayMergeAlgorithm	mwma = `MWMA_ALGORITHM_DEFAULT`,
		MultiwayMergeSplittingAlgorithm	mwmsa = `MWMSA_DEFAULT`,
		size_t	num_threads = `std::thread::hardware_concurrency()`
	)

Parallel multi-way merge routine with sentinels.

Implemented either using OpenMP or with std::threads, depending on if compiled with -fopenmp or not. The OpenMP version uses the implicit thread pool, which is faster when using this method often.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
target	Begin iterator out output sequence.
size	Maximum size to merge.
comp	Comparator.
mwma	MultiwayMergeAlgorithm set to use.
mwmsa	MultiwayMergeSplittingAlgorithm to use.
num_threads	Number of threads to use (defaults to all cores)

Template Parameters

Stable Stable merging incurs a performance penalty.

Returns: End iterator of output sequence.

Definition at line 343 of file parallel_multiway_merge.hpp.

References tlx::multiway_merge_base(), and tlx::parallel_multiway_merge_base().

◆ random_bipartition_shuffle()

void tlx::random_bipartition_shuffle	(	RandomAccessIt	begin,
		RandomAccessIt	end,
		size_t	size_left_partition,
		RandomBits &	urng
	)

Similar to std::shuffle, but only generates a random bi-partition.

In the result, the the left partition class is stored at positions 0 to size_left_partition-1 the right partition class is stored at positions size_left_partition to n where n = std::distance(begin, end).

Each element is moved to the left partition with probability (size_left_partition / n). There are no guarantees on the order WITHIN a partition (which makes this function considerable faster than std::shuffle especially if partition sizes are unbalanced). The runtime complexity is linear in the size of the smaller partition class.

Parameters

begin	Iterator to the begin of the data frame
end	Iterator to the end of the data frame
size_left_partition	Number of elements to be put into the left partition: 0 <= size_left_partition <= n
urng	Random number generator compatible with STL interface, e.g. std::mt19937

Definition at line 44 of file random_bipartition_shuffle.hpp.

References tlx::swap(), and gen_data::x.

◆ stable_multiway_merge()

RandomAccessIterator3 tlx::stable_multiway_merge	(	RandomAccessIteratorIterator	seqs_begin,
		RandomAccessIteratorIterator	seqs_end,
		RandomAccessIterator3	target,
		typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type	size,
		Comparator	comp = `Comparator()`,
		MultiwayMergeAlgorithm	mwma = `MWMA_ALGORITHM_DEFAULT`
	)

Stable sequential multi-way merge.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
target	Begin iterator out output sequence.
size	Maximum size to merge.
comp	Comparator.
mwma	MultiwayMergeAlgorithm set to use.

Returns: End iterator of output sequence.

Definition at line 1357 of file multiway_merge.hpp.

References tlx::multiway_merge_base().

◆ stable_multiway_merge_sentinels()

RandomAccessIterator3 tlx::stable_multiway_merge_sentinels	(	RandomAccessIteratorIterator	seqs_begin,
		RandomAccessIteratorIterator	seqs_end,
		RandomAccessIterator3	target,
		typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type	size,
		Comparator	comp = `Comparator()`,
		MultiwayMergeAlgorithm	mwma = `MWMA_ALGORITHM_DEFAULT`
	)

Stable sequential multi-way merge with sentinels in sequences.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
target	Begin iterator out output sequence.
size	Maximum size to merge.
comp	Comparator.
mwma	MultiwayMergeAlgorithm set to use.

Returns: End iterator of output sequence.

Definition at line 1423 of file multiway_merge.hpp.

References tlx::multiway_merge_base().

◆ stable_parallel_multiway_merge()

RandomAccessIterator3 tlx::stable_parallel_multiway_merge	(	RandomAccessIteratorIterator	seqs_begin,
		RandomAccessIteratorIterator	seqs_end,
		RandomAccessIterator3	target,
		const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type	size,
		Comparator	comp = `Comparator()`,
		MultiwayMergeAlgorithm	mwma = `MWMA_ALGORITHM_DEFAULT`,
		MultiwayMergeSplittingAlgorithm	mwmsa = `MWMSA_DEFAULT`,
		size_t	num_threads = `std::thread::hardware_concurrency()`
	)

Stable parallel multi-way merge routine.

Implemented either using OpenMP or with std::threads, depending on if compiled with -fopenmp or not. The OpenMP version uses the implicit thread pool, which is faster when using this method often.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
target	Begin iterator out output sequence.
size	Maximum size to merge.
comp	Comparator.
mwma	MultiwayMergeAlgorithm set to use.
mwmsa	MultiwayMergeSplittingAlgorithm to use.
num_threads	Number of threads to use (defaults to all cores)

Template Parameters

Stable Stable merging incurs a performance penalty.

Returns: End iterator of output sequence.

Definition at line 286 of file parallel_multiway_merge.hpp.

References tlx::multiway_merge_base(), and tlx::parallel_multiway_merge_base().

◆ stable_parallel_multiway_merge_sentinels()

RandomAccessIterator3 tlx::stable_parallel_multiway_merge_sentinels	(	RandomAccessIteratorIterator	seqs_begin,
		RandomAccessIteratorIterator	seqs_end,
		RandomAccessIterator3	target,
		const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type	size,
		Comparator	comp = `Comparator()`,
		MultiwayMergeAlgorithm	mwma = `MWMA_ALGORITHM_DEFAULT`,
		MultiwayMergeSplittingAlgorithm	mwmsa = `MWMSA_DEFAULT`,
		size_t	num_threads = `std::thread::hardware_concurrency()`
	)

Stable parallel multi-way merge routine with sentinels.

Implemented either using OpenMP or with std::threads, depending on if compiled with -fopenmp or not. The OpenMP version uses the implicit thread pool, which is faster when using this method often.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
target	Begin iterator out output sequence.
size	Maximum size to merge.
comp	Comparator.
mwma	MultiwayMergeAlgorithm set to use.
mwmsa	MultiwayMergeSplittingAlgorithm to use.
num_threads	Number of threads to use (defaults to all cores)