18#ifndef TLX_ALGORITHM_PARALLEL_MULTIWAY_MERGE_HEADER
19#define TLX_ALGORITHM_PARALLEL_MULTIWAY_MERGE_HEADER
62 typename RandomAccessIteratorIterator,
63 typename RandomAccessIterator3,
64 typename Comparator = std::less<
65 typename std::iterator_traits<
66 typename std::iterator_traits<RandomAccessIteratorIterator>
67 ::value_type::first_type>::value_type> >
69 RandomAccessIteratorIterator seqs_begin,
70 RandomAccessIteratorIterator seqs_end,
71 RandomAccessIterator3 target,
72 const typename std::iterator_traits<
73 typename std::iterator_traits<
74 RandomAccessIteratorIterator>::value_type::first_type>::
76 Comparator comp = Comparator(),
79 size_t num_threads = std::thread::hardware_concurrency()) {
81 using RandomAccessIteratorPair =
82 typename std::iterator_traits<RandomAccessIteratorIterator>
84 using RandomAccessIterator =
85 typename RandomAccessIteratorPair::first_type;
86 using DiffType =
typename std::iterator_traits<RandomAccessIterator>
90 std::vector<RandomAccessIteratorPair> seqs_ne;
91 seqs_ne.reserve(
static_cast<size_t>(seqs_end - seqs_begin));
92 DiffType total_size = 0;
94 for (RandomAccessIteratorIterator ii = seqs_begin; ii != seqs_end; ++ii)
96 if (ii->first != ii->second) {
97 total_size += ii->second - ii->first;
98 seqs_ne.push_back(*ii);
102 size_t num_seqs = seqs_ne.size();
104 if (total_size == 0 || num_seqs == 0)
107 if (
static_cast<DiffType
>(num_threads) > total_size)
108 num_threads = total_size;
114 for (
size_t s = 0; s < num_threads; ++s)
115 chunks[s].resize(num_seqs);
120 seqs_ne.begin(), seqs_ne.end(),
121 static_cast<DiffType
>(size), total_size, comp,
122 chunks.
data(), num_threads,
128 seqs_ne.begin(), seqs_ne.end(),
129 static_cast<DiffType
>(size), total_size, comp,
130 chunks.
data(), num_threads);
134#pragma omp parallel num_threads(num_threads)
136 size_t iam = omp_get_thread_num();
138 DiffType target_position = 0, local_size = 0;
140 for (
size_t s = 0; s < num_seqs; ++s)
142 target_position += chunks[iam][s].first - seqs_ne[s].first;
143 local_size += chunks[iam][s].second - chunks[iam][s].first;
147 chunks[iam].begin(), chunks[iam].end(),
148 target + target_position,
149 std::min(local_size,
static_cast<DiffType
>(size) - target_position),
153 std::vector<std::thread> threads(num_threads);
155 for (
size_t iam = 0; iam < num_threads; ++iam) {
156 threads[iam] = std::thread(
158 DiffType target_position = 0, local_size = 0;
160 for (
size_t s = 0; s < num_seqs; ++s)
162 target_position += chunks[iam][s].first - seqs_ne[s].first;
163 local_size += chunks[iam][s].second - chunks[iam][s].first;
167 chunks[iam].begin(), chunks[iam].end(),
168 target + target_position,
169 std::min(local_size,
static_cast<DiffType
>(size) - target_position),
174 for (
size_t i = 0; i < num_threads; ++i)
179 size_t count_seqs = 0;
180 for (RandomAccessIteratorIterator ii = seqs_begin; ii != seqs_end; ++ii)
182 if (ii->first != ii->second)
183 ii->first = chunks[num_threads - 1][count_seqs++].second;
186 return target + size;
223 typename RandomAccessIteratorIterator,
224 typename RandomAccessIterator3,
225 typename Comparator = std::less<
226 typename std::iterator_traits<
227 typename std::iterator_traits<RandomAccessIteratorIterator>
228 ::value_type::first_type>::value_type> >
230 RandomAccessIteratorIterator seqs_begin,
231 RandomAccessIteratorIterator seqs_end,
232 RandomAccessIterator3 target,
233 const typename std::iterator_traits<
234 typename std::iterator_traits<
235 RandomAccessIteratorIterator>::value_type::first_type>::
236 difference_type size,
237 Comparator comp = Comparator(),
240 size_t num_threads = std::thread::hardware_concurrency()) {
242 if (seqs_begin == seqs_end)
248 (
static_cast<size_t>(seqs_end - seqs_begin)
252 seqs_begin, seqs_end, target, size, comp,
253 mwma, mwmsa, num_threads);
257 seqs_begin, seqs_end, target, size, comp, mwma);
280 typename RandomAccessIteratorIterator,
281 typename RandomAccessIterator3,
282 typename Comparator = std::less<
283 typename std::iterator_traits<
284 typename std::iterator_traits<RandomAccessIteratorIterator>
285 ::value_type::first_type>::value_type> >
287 RandomAccessIteratorIterator seqs_begin,
288 RandomAccessIteratorIterator seqs_end,
289 RandomAccessIterator3 target,
290 const typename std::iterator_traits<
291 typename std::iterator_traits<
292 RandomAccessIteratorIterator>::value_type::first_type>::
293 difference_type size,
294 Comparator comp = Comparator(),
297 size_t num_threads = std::thread::hardware_concurrency()) {
299 if (seqs_begin == seqs_end)
305 (
static_cast<size_t>(seqs_end - seqs_begin)
309 seqs_begin, seqs_end, target, size, comp,
310 mwma, mwmsa, num_threads);
314 seqs_begin, seqs_end, target, size, comp, mwma);
337 typename RandomAccessIteratorIterator,
338 typename RandomAccessIterator3,
339 typename Comparator = std::less<
340 typename std::iterator_traits<
341 typename std::iterator_traits<RandomAccessIteratorIterator>
342 ::value_type::first_type>::value_type> >
344 RandomAccessIteratorIterator seqs_begin,
345 RandomAccessIteratorIterator seqs_end,
346 RandomAccessIterator3 target,
347 const typename std::iterator_traits<
348 typename std::iterator_traits<
349 RandomAccessIteratorIterator>::value_type::first_type>::
350 difference_type size,
351 Comparator comp = Comparator(),
354 size_t num_threads = std::thread::hardware_concurrency()) {
356 if (seqs_begin == seqs_end)
362 (
static_cast<size_t>(seqs_end - seqs_begin)
366 seqs_begin, seqs_end, target, size, comp,
367 mwma, mwmsa, num_threads);
371 seqs_begin, seqs_end, target, size, comp, mwma);
394 typename RandomAccessIteratorIterator,
395 typename RandomAccessIterator3,
396 typename Comparator = std::less<
397 typename std::iterator_traits<
398 typename std::iterator_traits<RandomAccessIteratorIterator>
399 ::value_type::first_type>::value_type> >
401 RandomAccessIteratorIterator seqs_begin,
402 RandomAccessIteratorIterator seqs_end,
403 RandomAccessIterator3 target,
404 const typename std::iterator_traits<
405 typename std::iterator_traits<
406 RandomAccessIteratorIterator>::value_type::first_type>::
407 difference_type size,
408 Comparator comp = Comparator(),
411 size_t num_threads = std::thread::hardware_concurrency()) {
413 if (seqs_begin == seqs_end)
419 (
static_cast<size_t>(seqs_end - seqs_begin)
423 seqs_begin, seqs_end, target, size, comp,
424 mwma, mwmsa, num_threads);
428 seqs_begin, seqs_end, target, size, comp, mwma);
iterator data() noexcept
return iterator to beginning of vector
size_t parallel_multiway_merge_oversampling
default oversampling factor for parallel_multiway_merge
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.
size_t parallel_multiway_merge_minimal_n
minimal number of items for switching to parallel merging
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 sp...
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.
size_t parallel_multiway_merge_minimal_k
minimal number of sequences for switching to parallel merging
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.
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.
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.
bool parallel_multiway_merge_force_parallel
setting to force parallel_multiway_merge() calls to run with parallel code
MultiwayMergeSplittingAlgorithm
Different splitting strategies for sorting/merging: by sampling, exact.
MultiwayMergeAlgorithm
Different merging algorithms: bubblesort-alike, loser-tree variants, enum sentinel.
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.
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 splittin...
bool parallel_multiway_merge_force_sequential
setting to force all parallel_multiway_merge() calls to run sequentially
SimpleVector< T > simple_vector
make template alias due to similarity with std::vector
std::string join(char glue, const std::vector< std::string > &parts)
Join a vector of strings by some glue character between each pair from the sequence.