Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
+ Collaboration diagram for Algorithms:

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

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.

References gen_data::value.

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

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

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
begin1Begin iterator of first sequence.
end1End iterator of first sequence.
begin2Begin iterator of second sequence.
end2End iterator of second sequence.
targetTarget begin iterator.
max_sizeMaximum number of elements to merge.
compComparator.
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().

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
begin1Begin iterator of first sequence.
end1End iterator of first sequence.
begin2Begin iterator of second sequence.
end2End iterator of second sequence.
targetTarget begin iterator.
max_sizeMaximum number of elements to merge.
compComparator.
Returns
Output end iterator.

Definition at line 94 of file merge_advance.hpp.

Referenced by tlx::merge_advance().

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
begin1Begin iterator of first sequence.
end1End iterator of first sequence.
begin2Begin iterator of second sequence.
end2End iterator of second sequence.
targetTarget begin iterator.
max_sizeMaximum number of elements to merge.
compComparator.
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.

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

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_seqsBegin of the sequence of iterator pairs.
end_seqsEnd of the sequence of iterator pairs.
rankThe global rank to partition at.
begin_offsetsA 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.
compThe ordering functor, defaults to std::less<T>.

Definition at line 109 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().

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_seqsBegin of the sequence of iterator pairs.
end_seqsEnd of the sequence of iterator pairs.
rankThe global rank to partition at.
offsetThe 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.
compThe ordering functor, defaults to std::less.

Definition at line 103 of file multisequence_selection.hpp.

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

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_beginBegin iterator of iterator pair input sequence.
seqs_endEnd iterator of iterator pair input sequence.
targetBegin iterator out output sequence.
sizeMaximum size to merge.
compComparator.
mwmaMultiwayMergeAlgorithm set to use.
Returns
End iterator of output sequence.

Definition at line 1324 of file multiway_merge.hpp.

References tlx::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_beginBegin iterator of iterator pair input sequence.
seqs_endEnd iterator of iterator pair input sequence.
targetBegin iterator out output sequence.
sizeMaximum size to merge.
compComparator.
mwmaMultiwayMergeAlgorithm set to use.
Template Parameters
StableStable merging incurs a performance penalty.
SentinelsThe 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::stable_multiway_merge(), tlx::stable_multiway_merge_sentinels(), tlx::stable_parallel_multiway_merge(), and tlx::stable_parallel_multiway_merge_sentinels().

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_beginBegin iterator of iterator pair input sequence.
seqs_endEnd iterator of iterator pair input sequence.
sizeMaximum size to merge.
total_sizeTotal size of all sequences combined.
compComparator.
chunksOutput subsequences for num_threads.
num_threadsSplit the sequences into for num_threads.
Template Parameters
StableStable merging incurs a performance penalty.
Returns
End iterator of output sequence.

Definition at line 188 of file multiway_merge_splitting.hpp.

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

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_beginBegin iterator of iterator pair input sequence.
seqs_endEnd iterator of iterator pair input sequence.
sizeMaximum size to merge.
total_sizeTotal size of all sequences combined.
compComparator.
chunksOutput subsequences for num_threads.
num_threadsSplit the sequences into for num_threads.
merge_oversamplingoversampling factor
Template Parameters
StableStable merging incurs a performance penalty.
Returns
End iterator of output sequence.

Definition at line 92 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_beginBegin iterator of iterator pair input sequence.
seqs_endEnd iterator of iterator pair input sequence.
targetBegin iterator out output sequence.
sizeMaximum size to merge.
compComparator.
mwmaMultiwayMergeAlgorithm set to use.
Returns
End iterator of output sequence.

Definition at line 1390 of file multiway_merge.hpp.

References tlx::multiway_merge_base().

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_beginBegin iterator of iterator pair input sequence.
seqs_endEnd iterator of iterator pair input sequence.
targetBegin iterator out output sequence.
sizeMaximum size to merge.
compComparator.
mwmaMultiwayMergeAlgorithm set to use.
mwmsaMultiwayMergeSplittingAlgorithm to use.
num_threadsNumber of threads to use (defaults to all cores)
Template Parameters
StableStable 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(), tlx::parallel_multiway_merge_base(), tlx::parallel_multiway_merge_force_parallel, tlx::parallel_multiway_merge_force_sequential, tlx::parallel_multiway_merge_minimal_k, and tlx::parallel_multiway_merge_minimal_n.

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_beginBegin iterator of iterator pair input sequence.
seqs_endEnd iterator of iterator pair input sequence.
targetBegin iterator out output sequence.
sizeMaximum size to merge.
compComparator.
mwmaMultiwayMergeAlgorithm set to use.
mwmsaMultiwayMergeSplittingAlgorithm to use.
num_threadsNumber of threads to use (defaults to all cores)
Template Parameters
StableStable 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, 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().

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_beginBegin iterator of iterator pair input sequence.
seqs_endEnd iterator of iterator pair input sequence.
targetBegin iterator out output sequence.
sizeMaximum size to merge.
compComparator.
mwmaMultiwayMergeAlgorithm set to use.
mwmsaMultiwayMergeSplittingAlgorithm to use.
num_threadsNumber of threads to use (defaults to all cores)
Template Parameters
StableStable 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(), tlx::parallel_multiway_merge_base(), tlx::parallel_multiway_merge_force_parallel, tlx::parallel_multiway_merge_force_sequential, tlx::parallel_multiway_merge_minimal_k, and tlx::parallel_multiway_merge_minimal_n.

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
beginIterator to the begin of the data frame
endIterator to the end of the data frame
size_left_partitionNumber of elements to be put into the left partition: 0 <= size_left_partition <= n
urngRandom 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.

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_beginBegin iterator of iterator pair input sequence.
seqs_endEnd iterator of iterator pair input sequence.
targetBegin iterator out output sequence.
sizeMaximum size to merge.
compComparator.
mwmaMultiwayMergeAlgorithm set to use.
Returns
End iterator of output sequence.

Definition at line 1357 of file multiway_merge.hpp.

References tlx::multiway_merge_base().

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_beginBegin iterator of iterator pair input sequence.
seqs_endEnd iterator of iterator pair input sequence.
targetBegin iterator out output sequence.
sizeMaximum size to merge.
compComparator.
mwmaMultiwayMergeAlgorithm set to use.
Returns
End iterator of output sequence.

Definition at line 1423 of file multiway_merge.hpp.

References tlx::multiway_merge_base().

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_beginBegin iterator of iterator pair input sequence.
seqs_endEnd iterator of iterator pair input sequence.
targetBegin iterator out output sequence.
sizeMaximum size to merge.
compComparator.
mwmaMultiwayMergeAlgorithm set to use.
mwmsaMultiwayMergeSplittingAlgorithm to use.
num_threadsNumber of threads to use (defaults to all cores)
Template Parameters
StableStable 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(), tlx::parallel_multiway_merge_base(), tlx::parallel_multiway_merge_force_parallel, tlx::parallel_multiway_merge_force_sequential, tlx::parallel_multiway_merge_minimal_k, and tlx::parallel_multiway_merge_minimal_n.

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_beginBegin iterator of iterator pair input sequence.
seqs_endEnd iterator of iterator pair input sequence.
targetBegin iterator out output sequence.
sizeMaximum size to merge.
compComparator.
mwmaMultiwayMergeAlgorithm set to use.
mwmsaMultiwayMergeSplittingAlgorithm to use.
num_threadsNumber of threads to use (defaults to all cores)
Template Parameters
StableStable merging incurs a performance penalty.
Returns
End iterator of output sequence.

Definition at line 400 of file parallel_multiway_merge.hpp.

References tlx::multiway_merge_base(), tlx::parallel_multiway_merge_base(), tlx::parallel_multiway_merge_force_parallel, tlx::parallel_multiway_merge_force_sequential, tlx::parallel_multiway_merge_minimal_k, and tlx::parallel_multiway_merge_minimal_n.

Variable Documentation

bool parallel_multiway_merge_force_parallel = false
bool parallel_multiway_merge_force_sequential = false
size_t parallel_multiway_merge_minimal_k = 2
size_t parallel_multiway_merge_minimal_n = 1000
size_t parallel_multiway_merge_oversampling = 10

default oversampling factor for parallel_multiway_merge

Definition at line 35 of file parallel_multiway_merge.cpp.

Referenced by tlx::parallel_multiway_merge_base().