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;
112 simple_vector<std::vector<RandomAccessIteratorPair> > chunks(num_threads);
114 for (
size_t s = 0; s < num_threads; ++s)
115 chunks[s].resize(num_seqs);
119 multiway_merge_sampling_splitting<Stable>(
120 seqs_ne.begin(), seqs_ne.end(),
121 static_cast<DiffType
>(size), total_size, comp,
122 chunks.data(), num_threads,
127 multiway_merge_exact_splitting<Stable>(
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;
146 multiway_merge_base<Stable, false>(
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;
166 multiway_merge_base<Stable, false>(
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);
436 #endif // !TLX_ALGORITHM_PARALLEL_MULTIWAY_MERGE_HEADER