14 #ifndef STXXL_RANDOM_SHUFFLE_HEADER
15 #define STXXL_RANDOM_SHUFFLE_HEADER
21 #include <stxxl/bits/stream/stream.h>
23 #include <stxxl/stack>
26 __STXXL_BEGIN_NAMESPACE
28 namespace random_shuffle_local
32 template <
class ExtIterator>
35 typedef typename ExtIterator::size_type size_type;
36 typedef typename ExtIterator::value_type value_type;
37 typedef typename ExtIterator::block_type block_type;
38 typedef typename ExtIterator::const_iterator ConstExtIterator;
39 typedef stxxl::buf_ostream<block_type, typename ExtIterator::bids_container_iterator> buf_ostream_type;
42 unsigned_type nbuffers;
43 buf_ostream_type * outstream;
46 write_vector(ExtIterator begin,
47 unsigned nbuffers_ = 2
48 ) : it(begin), nbuffers(nbuffers_)
50 outstream =
new buf_ostream_type(it.bid(), nbuffers);
53 value_type & operator * ()
55 if (it.block_offset() == 0)
61 write_vector & operator ++ ()
70 ConstExtIterator const_out = it;
72 while (const_out.block_offset())
74 **outstream = *const_out;
84 virtual ~write_vector()
97 template <
typename Tp_,
typename AllocStrategy_,
typename SzTp_,
typename DiffTp_,
98 unsigned BlockSize_,
typename PgTp_,
unsigned PageSize_,
typename RandomNumberGenerator_>
99 void random_shuffle(stxxl::vector_iterator<Tp_, AllocStrategy_, SzTp_, DiffTp_, BlockSize_, PgTp_, PageSize_> first,
100 stxxl::vector_iterator<Tp_, AllocStrategy_, SzTp_, DiffTp_, BlockSize_, PgTp_, PageSize_> beyond,
101 RandomNumberGenerator_ & rand,
114 template <
typename ExtIterator_,
115 typename RandomNumberGenerator_,
118 typename AllocStrategy_>
121 RandomNumberGenerator_ & rand,
123 AllocStrategy_ AS = STXXL_DEFAULT_ALLOC_STRATEGY())
125 typedef typename ExtIterator_::value_type value_type;
126 typedef typename stxxl::STACK_GENERATOR<value_type, stxxl::external,
127 stxxl::grow_shrink2, PageSize_,
128 BlockSize_, void, 0, AllocStrategy_>::result stack_type;
129 typedef typename stack_type::block_type block_type;
131 STXXL_VERBOSE1(
"random_shuffle: Plain Version");
133 stxxl::int64 n = beyond - first;
136 if (M < 6 * BlockSize_ + PageSize_ * BlockSize_)
137 M = 6 * BlockSize_ + PageSize_ * BlockSize_;
140 int_type k = M / (3 * BlockSize_);
143 stxxl::int64 i, j, size = 0;
145 value_type * temp_array;
146 typedef typename stxxl::VECTOR_GENERATOR<value_type,
147 PageSize_, 4, BlockSize_, AllocStrategy_>::result temp_vector_type;
148 temp_vector_type * temp_vector;
150 stxxl::prefetch_pool<block_type> p_pool(0);
151 STXXL_VERBOSE1(
"random_shuffle: " << M / BlockSize_ - k <<
" write buffers for " << k <<
" buckets");
152 stxxl::write_pool<block_type> w_pool(M / BlockSize_ - k);
154 stack_type ** buckets;
157 buckets =
new stack_type *[k];
158 for (j = 0; j < k; j++)
159 buckets[j] =
new stack_type(p_pool, w_pool, 0);
167 int_type random_bucket = 0;
168 for (i = 0; i < n; ++i) {
169 random_bucket = rand(k);
170 buckets[random_bucket]->push(*in);
177 p_pool.resize(PageSize_);
180 for (int_type j = 0; j < k; j++) {
181 buckets[j]->set_prefetch_aggr(PageSize_);
184 unsigned_type space_left = M - k * BlockSize_ -
185 PageSize_ * BlockSize_;
186 ExtIterator_ Writer = first;
187 ExtIterator_ it = first;
189 for (i = 0; i < k; i++) {
190 STXXL_VERBOSE1(
"random_shuffle: bucket no " << i <<
" contains " << buckets[i]->size() <<
" elements");
194 for (i = 0; i < k; i++) {
195 size = buckets[i]->size();
198 if (size *
sizeof(value_type) < space_left) {
199 STXXL_VERBOSE1(
"random_shuffle: no recursion");
202 temp_array =
new value_type[size];
203 for (j = 0; j < size; j++) {
204 temp_array[j] = buckets[i]->top();
212 for (j = 0; j < size; j++) {
213 *Writer = temp_array[j];
221 STXXL_VERBOSE1(
"random_shuffle: recursion");
224 temp_vector =
new temp_vector_type(size);
226 for (j = 0; j < size; j++) {
227 (*temp_vector)[j] = buckets[i]->top();
232 space_left += PageSize_ * BlockSize_;
233 STXXL_VERBOSE1(
"random_shuffle: Space left: " << space_left);
237 temp_vector->end(), rand, space_left);
239 p_pool.resize(PageSize_);
242 for (j = 0; j < size; j++) {
243 *Writer = (*temp_vector)[j];
253 for (
int j = 0; j < k; j++)
264 template <
typename Tp_,
typename AllocStrategy_,
typename SzTp_,
typename DiffTp_,
265 unsigned BlockSize_,
typename PgTp_,
unsigned PageSize_,
typename RandomNumberGenerator_>
266 void random_shuffle(stxxl::vector_iterator<Tp_, AllocStrategy_, SzTp_, DiffTp_, BlockSize_, PgTp_, PageSize_> first,
267 stxxl::vector_iterator<Tp_, AllocStrategy_, SzTp_, DiffTp_, BlockSize_, PgTp_, PageSize_> beyond,
268 RandomNumberGenerator_ & rand,
271 typedef stxxl::vector_iterator<Tp_, AllocStrategy_, SzTp_, DiffTp_, BlockSize_, PgTp_, PageSize_> ExtIterator_;
272 typedef typename ExtIterator_::value_type value_type;
273 typedef typename stxxl::STACK_GENERATOR<value_type, stxxl::external,
274 stxxl::grow_shrink2, PageSize_, BlockSize_>::result stack_type;
275 typedef typename stack_type::block_type block_type;
277 STXXL_VERBOSE1(
"random_shuffle: Vector Version");
280 if (M < 6 * BlockSize_ + PageSize_ * BlockSize_)
281 M = 6 * BlockSize_ + PageSize_ * BlockSize_;
284 stxxl::int64 n = beyond - first;
285 int_type k = M / (3 * BlockSize_);
287 stxxl::int64 i, j, size = 0;
289 value_type * temp_array;
290 typedef typename stxxl::VECTOR_GENERATOR<value_type,
291 PageSize_, 4, BlockSize_, AllocStrategy_>::result temp_vector_type;
292 temp_vector_type * temp_vector;
294 stxxl::prefetch_pool<block_type> p_pool(0);
295 stxxl::write_pool<block_type> w_pool(M / BlockSize_ - k);
297 stack_type ** buckets;
300 buckets =
new stack_type *[k];
301 for (j = 0; j < k; j++)
302 buckets[j] =
new stack_type(p_pool, w_pool, 0);
310 int_type random_bucket = 0;
311 for (i = 0; i < n; ++i) {
312 random_bucket = rand(k);
313 buckets[random_bucket]->push(*in);
320 p_pool.resize(PageSize_);
323 for (j = 0; j < k; j++) {
324 buckets[j]->set_prefetch_aggr(PageSize_);
327 unsigned_type space_left = M - k * BlockSize_ -
328 PageSize_ * BlockSize_;
329 random_shuffle_local::write_vector<ExtIterator_>
330 Writer(first, 2 * PageSize_);
331 ExtIterator_ it = first;
333 for (i = 0; i < k; i++) {
334 STXXL_VERBOSE1(
"random_shuffle: bucket no " << i <<
" contains " << buckets[i]->size() <<
" elements");
338 for (i = 0; i < k; i++) {
339 size = buckets[i]->size();
342 if (size *
sizeof(value_type) < space_left) {
343 STXXL_VERBOSE1(
"random_shuffle: no recursion");
346 temp_array =
new value_type[size];
347 for (j = 0; j < size; j++) {
348 temp_array[j] = buckets[i]->top();
356 for (j = 0; j < size; j++) {
357 *Writer = temp_array[j];
365 STXXL_VERBOSE1(
"random_shuffle: recursion");
367 temp_vector =
new temp_vector_type(size);
369 for (j = 0; j < size; j++) {
370 (*temp_vector)[j] = buckets[i]->top();
375 space_left += PageSize_ * BlockSize_;
377 STXXL_VERBOSE1(
"random_shuffle: Space left: " << space_left);
381 temp_vector->end(), rand, space_left);
383 p_pool.resize(PageSize_);
386 for (j = 0; j < size; j++) {
387 *Writer = (*temp_vector)[j];
397 for (
int j = 0; j < k; j++)
409 template <
typename Tp_,
typename AllocStrategy_,
typename SzTp_,
typename DiffTp_,
410 unsigned BlockSize_,
typename PgTp_,
unsigned PageSize_>
411 void random_shuffle(stxxl::vector_iterator<Tp_, AllocStrategy_, SzTp_, DiffTp_, BlockSize_, PgTp_, PageSize_> first,
412 stxxl::vector_iterator<Tp_, AllocStrategy_, SzTp_, DiffTp_, BlockSize_, PgTp_, PageSize_> beyond,
415 stxxl::random_number<> rand;
421 __STXXL_END_NAMESPACE
423 #endif // !STXXL_RANDOM_SHUFFLE_HEADER