Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
multiway_merge_splitting.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * tlx/algorithm/multiway_merge_splitting.hpp
3  *
4  * Two splitting variants for balancing parallel multiway merge.
5  *
6  * Copied and modified from STXXL, see http://stxxl.org, which itself extracted
7  * it from MCSTL http://algo2.iti.uni-karlsruhe.de/singler/mcstl/. Both are
8  * distributed under the Boost Software License, Version 1.0.
9  *
10  * Part of tlx - http://panthema.net/tlx
11  *
12  * Copyright (C) 2007 Johannes Singler <[email protected]>
13  * Copyright (C) 2014-2018 Timo Bingmann <[email protected]>
14  *
15  * All rights reserved. Published under the Boost Software License, Version 1.0
16  ******************************************************************************/
17 
18 #ifndef TLX_ALGORITHM_MULTIWAY_MERGE_SPLITTING_HEADER
19 #define TLX_ALGORITHM_MULTIWAY_MERGE_SPLITTING_HEADER
20 
21 #include <algorithm>
22 #include <vector>
23 
25 #include <tlx/simple_vector.hpp>
26 
27 namespace tlx {
28 
29 //! \addtogroup tlx_algorithm
30 //! \{
31 
32 /*!
33  * Different splitting strategies for sorting/merging: by sampling, exact
34 */
40 };
41 
42 namespace multiway_merge_detail {
43 
44 /*!
45  * Split a sequence into parts of almost equal size.
46  *
47  * The resulting sequence s of length p+1 contains the splitting positions when
48  * splitting the range [0,n) into parts of almost equal size (plus minus 1).
49  * The first entry is 0, the last one n. There may result empty parts.
50  *
51  * \param n Number of elements
52  * \param p Number of parts
53  * \param s Splitters
54  * \returns End of splitter sequence, i. e. \c s+p+1
55  */
56 template <typename DiffType, typename DiffTypeOutputIterator>
57 DiffTypeOutputIterator equally_split(
58  DiffType n, size_t p, DiffTypeOutputIterator s) {
59 
60  DiffType chunk_length = n / p, split = n % p, start = 0;
61  for (size_t i = 0; i < p; i++)
62  {
63  *s++ = start;
64  start += (static_cast<DiffType>(i) < split) ? (chunk_length + 1) : chunk_length;
65  }
66  *s++ = n;
67 
68  return s;
69 }
70 
71 } // namespace multiway_merge_detail
72 
73 /*!
74  * Splitting method for parallel multi-way merge routine: use sampling and
75  * binary search for in-exact splitting.
76  *
77  * \param seqs_begin Begin iterator of iterator pair input sequence.
78  * \param seqs_end End iterator of iterator pair input sequence.
79  * \param size Maximum size to merge.
80  * \param total_size Total size of all sequences combined.
81  * \param comp Comparator.
82  * \param chunks Output subsequences for num_threads.
83  * \param num_threads Split the sequences into for num_threads.
84  * \param merge_oversampling oversampling factor
85  * \tparam Stable Stable merging incurs a performance penalty.
86  * \return End iterator of output sequence.
87  */
88 template <
89  bool Stable,
90  typename RandomAccessIteratorIterator,
91  typename Comparator>
93  const RandomAccessIteratorIterator& seqs_begin,
94  const RandomAccessIteratorIterator& seqs_end,
95  typename std::iterator_traits<
96  typename std::iterator_traits<
97  RandomAccessIteratorIterator>::value_type::first_type>::
98  difference_type size,
99  typename std::iterator_traits<
100  typename std::iterator_traits<
101  RandomAccessIteratorIterator>::value_type::first_type>::
102  difference_type total_size,
103  Comparator comp,
104  std::vector<typename std::iterator_traits<
105  RandomAccessIteratorIterator>::value_type>* chunks,
106  const size_t num_threads,
107  const size_t merge_oversampling) {
108 
109  using RandomAccessIterator =
110  typename std::iterator_traits<RandomAccessIteratorIterator>
111  ::value_type::first_type;
112  using value_type = typename std::iterator_traits<RandomAccessIterator>
113  ::value_type;
114  using DiffType = typename std::iterator_traits<RandomAccessIterator>
115  ::difference_type;
116 
117  const DiffType num_seqs = seqs_end - seqs_begin;
118  const DiffType num_samples =
119  num_threads * static_cast<DiffType>(merge_oversampling);
120 
121  // pick samples
122  simple_vector<value_type> samples(num_seqs* num_samples);
123 
124  for (DiffType s = 0; s < num_seqs; ++s)
125  {
126  for (DiffType i = 0; i < num_samples; ++i)
127  {
128  DiffType sample_index = static_cast<DiffType>(
129  double(seqs_begin[s].second - seqs_begin[s].first)
130  * (double(i + 1) / double(num_samples + 1))
131  * (double(size) / double(total_size)));
132  samples[s * num_samples + i] = seqs_begin[s].first[sample_index];
133  }
134  }
135 
136  if (Stable)
137  std::stable_sort(samples.begin(), samples.end(), comp);
138  else
139  std::sort(samples.begin(), samples.end(), comp);
140 
141  // for each processor
142  for (size_t slab = 0; slab < num_threads; ++slab)
143  {
144  // for each sequence
145  for (DiffType seq = 0; seq < num_seqs; ++seq)
146  {
147  if (slab > 0) {
148  chunks[slab][static_cast<size_t>(seq)].first =
149  std::upper_bound(
150  seqs_begin[seq].first, seqs_begin[seq].second,
151  samples[num_samples * num_seqs * slab / num_threads],
152  comp);
153  }
154  else // absolute beginning
155  chunks[slab][static_cast<size_t>(seq)].first = seqs_begin[seq].first;
156 
157  if ((slab + 1) < num_threads) {
158  chunks[slab][static_cast<size_t>(seq)].second =
159  std::upper_bound(
160  seqs_begin[seq].first, seqs_begin[seq].second,
161  samples[num_samples * num_seqs * (slab + 1) / num_threads],
162  comp);
163  }
164  else // absolute ending
165  chunks[slab][static_cast<size_t>(seq)].second = seqs_begin[seq].second;
166  }
167  }
168 }
169 
170 /*!
171  * Splitting method for parallel multi-way merge routine: use multisequence
172  * selection for exact splitting.
173  *
174  * \param seqs_begin Begin iterator of iterator pair input sequence.
175  * \param seqs_end End iterator of iterator pair input sequence.
176  * \param size Maximum size to merge.
177  * \param total_size Total size of all sequences combined.
178  * \param comp Comparator.
179  * \param chunks Output subsequences for num_threads.
180  * \param num_threads Split the sequences into for num_threads.
181  * \tparam Stable Stable merging incurs a performance penalty.
182  * \return End iterator of output sequence.
183  */
184 template <
185  bool Stable,
186  typename RandomAccessIteratorIterator,
187  typename Comparator>
189  const RandomAccessIteratorIterator& seqs_begin,
190  const RandomAccessIteratorIterator& seqs_end,
191  typename std::iterator_traits<
192  typename std::iterator_traits<
193  RandomAccessIteratorIterator>::value_type::first_type>::
194  difference_type size,
195  typename std::iterator_traits<
196  typename std::iterator_traits<
197  RandomAccessIteratorIterator>::value_type::first_type>::
198  difference_type total_size,
199  Comparator comp,
200  std::vector<typename std::iterator_traits<
201  RandomAccessIteratorIterator>::value_type>* chunks,
202  const size_t num_threads) {
203 
204  using RandomAccessIteratorPair =
205  typename std::iterator_traits<RandomAccessIteratorIterator>
206  ::value_type;
207  using RandomAccessIterator = typename RandomAccessIteratorPair
208  ::first_type;
209  using DiffType = typename std::iterator_traits<RandomAccessIterator>
210  ::difference_type;
211 
212  const size_t num_seqs = static_cast<size_t>(seqs_end - seqs_begin);
213  const bool tight = (total_size == size);
214 
216 
217  std::vector<DiffType> ranks(static_cast<size_t>(num_threads + 1));
218  multiway_merge_detail::equally_split(size, num_threads, ranks.begin());
219 
220  for (size_t s = 0; s < (num_threads - 1); ++s)
221  {
222  offsets[s].resize(num_seqs);
224  seqs_begin, seqs_end,
225  ranks[static_cast<size_t>(s + 1)], offsets[s].begin(), comp);
226 
227  if (!tight) // last one also needed and available
228  {
229  offsets[num_threads - 1].resize(num_seqs);
231  seqs_begin, seqs_end,
232  size, offsets[num_threads - 1].begin(), comp);
233  }
234  }
235 
236  // for each processor
237  for (size_t slab = 0; slab < num_threads; ++slab)
238  {
239  // for each sequence
240  for (size_t s = 0; s < num_seqs; ++s)
241  {
242  if (slab == 0) // absolute beginning
243  chunks[slab][s].first = seqs_begin[static_cast<DiffType>(s)].first;
244  else
245  chunks[slab][s].first = offsets[slab - 1][s];
246 
247  if (!tight || slab < (num_threads - 1))
248  chunks[slab][s].second = offsets[slab][s];
249  else // slab == num_threads - 1
250  chunks[slab][s].second = seqs_begin[static_cast<DiffType>(s)].second;
251  }
252  }
253 }
254 
255 //! \}
256 
257 } // namespace tlx
258 
259 #endif // !TLX_ALGORITHM_MULTIWAY_MERGE_SPLITTING_HEADER
260 
261 /******************************************************************************/
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...
void resize(size_type new_size)
resize the array to contain exactly new_size items
DiffTypeOutputIterator equally_split(DiffType n, size_t p, DiffTypeOutputIterator s)
Split a sequence into parts of almost equal size.
Simpler non-growing vector without initialization.
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 seq...
std::vector< std::string > split(char sep, const std::string &str, std::string::size_type limit)
Split the given string at each separator character into distinct substrings.
Definition: split.cpp:20
MultiwayMergeSplittingAlgorithm
Different splitting strategies for sorting/merging: by sampling, exact.
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...
std::vector< T, Allocator< T > > vector
vector with Manager tracking
Definition: allocator.hpp:228