tlx

Algorithms for iterators and ranges. More...

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
}
Different merging algorithms: bubblesort-alike, loser-tree variants, enum sentinel. More...

enum  MultiwayMergeSplittingAlgorithm { MWMSA_SAMPLING, MWMSA_EXACT, MWMSA_LAST, MWMSA_DEFAULT }
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 >
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 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 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 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 (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<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<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<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 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 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<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<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 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 (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 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 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 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...

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

Variables

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

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

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

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

size_t parallel_multiway_merge_oversampling
default oversampling factor for parallel_multiway_merge More...

Detailed Description

Algorithms for iterators and ranges.

Enumeration Type Documentation

 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.

 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

 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.

 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.

 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.

 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.

 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.

 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.

 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.

 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.

Definition at line 106 of file multisequence_partition.hpp.

 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.

 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.

 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.

 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.

 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.

 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.

 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.

 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.

 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.

 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.

 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.

 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.

 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.

 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)
Template Parameters
 Stable Stable merging incurs a performance penalty.
Returns
End iterator of output sequence.

Definition at line 400 of file parallel_multiway_merge.hpp.

Variable Documentation

 bool parallel_multiway_merge_force_parallel

setting to force parallel_multiway_merge() calls to run with parallel code

Definition at line 29 of file parallel_multiway_merge.cpp.

 bool parallel_multiway_merge_force_sequential

setting to force all parallel_multiway_merge() calls to run sequentially

Definition at line 27 of file parallel_multiway_merge.cpp.

 size_t parallel_multiway_merge_minimal_k

minimal number of sequences for switching to parallel merging

Definition at line 31 of file parallel_multiway_merge.cpp.

 size_t parallel_multiway_merge_minimal_n

minimal number of items for switching to parallel merging

Definition at line 33 of file parallel_multiway_merge.cpp.

 size_t parallel_multiway_merge_oversampling

default oversampling factor for parallel_multiway_merge

Definition at line 35 of file parallel_multiway_merge.cpp.