/usr/include/stxxl/bits/algo
Edit: /usr/include/stxxl/bits/algo/random_shuffle.h (13357B)
/***************************************************************************
* include/stxxl/bits/algo/random_shuffle.h
*
* Part of the STXXL. See http://stxxl.sourceforge.net
*
* Copyright (C) 2007 Manuel Krings
* Copyright (C) 2007 Markus Westphal
* Copyright (C) 2009, 2010 Andreas Beckmann
*
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
**************************************************************************/
#ifndef STXXL_ALGO_RANDOM_SHUFFLE_HEADER
#define STXXL_ALGO_RANDOM_SHUFFLE_HEADER
// TODO: improve main memory consumption in recursion
// (free stacks buffers)
// TODO: shuffle small input in internal memory
#include
#include
#include
STXXL_BEGIN_NAMESPACE
//! \addtogroup stlalgo
//! \{
//! External equivalent of std::random_shuffle
//! \param first begin of the range to shuffle
//! \param last end of the range to shuffle
//! \param rand random number generator object (functor)
//! \param M number of bytes for internal use
//! \param AS parallel disk allocation strategy
//!
//! - BlockSize size of the block to use for external memory data structures
//! - PageSize page size in blocks to use for external memory data structures
template
void random_shuffle(ExtIterator first,
ExtIterator last,
RandomNumberGenerator& rand,
unsigned_type M,
AllocStrategy AS = STXXL_DEFAULT_ALLOC_STRATEGY())
{
STXXL_UNUSED(AS); // FIXME: Why is this not being used?
typedef typename ExtIterator::value_type value_type;
typedef typename STACK_GENERATOR<
value_type, external, grow_shrink2, PageSize,
BlockSize, void, 0, AllocStrategy
>::result stack_type;
typedef typename stack_type::block_type block_type;
STXXL_VERBOSE1("random_shuffle: Plain Version");
STXXL_STATIC_ASSERT(int(BlockSize) < 0 && "This implementation was never tested. Please report to the stxxl developers if you have an ExtIterator that works with this implementation.");
int64 n = last - first; // the number of input elements
// make sure we have at least 6 blocks + 1 page
if (M < 6 * BlockSize + PageSize * BlockSize) {
STXXL_ERRMSG("random_shuffle: insufficient memory, " << M << " bytes supplied,");
M = 6 * BlockSize + PageSize * BlockSize;
STXXL_ERRMSG("random_shuffle: increasing to " << M << " bytes (6 blocks + 1 page)");
}
int_type k = M / (3 * BlockSize); // number of buckets
int64 i, j, size = 0;
value_type* temp_array;
typedef typename VECTOR_GENERATOR<
value_type, PageSize, 4, BlockSize, AllocStrategy
>::result temp_vector_type;
temp_vector_type* temp_vector;
STXXL_VERBOSE1("random_shuffle: " << M / BlockSize - k << " write buffers for " << k << " buckets");
read_write_pool pool(0, M / BlockSize - k); // no read buffers and M/B-k write buffers
stack_type** buckets;
// create and put buckets into container
buckets = new stack_type*[k];
for (j = 0; j < k; j++)
buckets[j] = new stack_type(pool, 0);
///// Reading input /////////////////////
typedef typename stream::streamify_traits::stream_type input_stream;
input_stream in = stream::streamify(first, last);
// distribute input into random buckets
int_type random_bucket = 0;
for (i = 0; i < n; ++i) {
random_bucket = rand(k);
buckets[random_bucket]->push(*in); // reading the current input element
++in; // go to the next input element
}
///// Processing //////////////////////
// resize buffers
pool.resize_write(0);
pool.resize_prefetch(PageSize);
unsigned_type space_left = M - k * BlockSize -
PageSize * BlockSize; // remaining int space
ExtIterator Writer = first;
ExtIterator it = first;
for (i = 0; i < k; i++) {
STXXL_VERBOSE1("random_shuffle: bucket no " << i << " contains " << buckets[i]->size() << " elements");
}
// shuffle each bucket
for (i = 0; i < k; i++) {
buckets[i]->set_prefetch_aggr(PageSize);
size = buckets[i]->size();
// does the bucket fit into memory?
if (size * sizeof(value_type) < space_left) {
STXXL_VERBOSE1("random_shuffle: no recursion");
// copy bucket into temp. array
temp_array = new value_type[size];
for (j = 0; j < size; j++) {
temp_array[j] = buckets[i]->top();
buckets[i]->pop();
}
// shuffle
potentially_parallel::
random_shuffle(temp_array, temp_array + size, rand);
// write back
for (j = 0; j < size; j++) {
*Writer = temp_array[j];
++Writer;
}
// free memory
delete[] temp_array;
}
else {
STXXL_VERBOSE1("random_shuffle: recursion");
// copy bucket into temp. stxxl::vector
temp_vector = new temp_vector_type(size);
for (j = 0; j < size; j++) {
(*temp_vector)[j] = buckets[i]->top();
buckets[i]->pop();
}
pool.resize_prefetch(0);
space_left += PageSize * BlockSize;
STXXL_VERBOSE1("random_shuffle: Space left: " << space_left);
// recursive shuffle
stxxl::random_shuffle(temp_vector->begin(),
temp_vector->end(), rand, space_left);
pool.resize_prefetch(PageSize);
// write back
for (j = 0; j < size; j++) {
*Writer = (*temp_vector)[j];
++Writer;
}
// free memory
delete temp_vector;
}
// free bucket
delete buckets[i];
space_left += BlockSize;
}
delete[] buckets;
}
//! External equivalent of std::random_shuffle (specialization for stxxl::vector)
//! \param first begin of the range to shuffle
//! \param last end of the range to shuffle
//! \param rand random number generator object (functor)
//! \param M number of bytes for internal use
template
void random_shuffle(
stxxl::vector_iterator first,
stxxl::vector_iterator last,
RandomNumberGenerator& rand,
unsigned_type M)
{
typedef stxxl::vector_iterator ExtIterator;
typedef typename ExtIterator::value_type value_type;
typedef typename ExtIterator::bids_container_iterator bids_container_iterator;
typedef typename stxxl::STACK_GENERATOR::result stack_type;
typedef typename stack_type::block_type block_type;
STXXL_VERBOSE1("random_shuffle: Vector Version");
// make sure we have at least 6 blocks + 1 page
if (M < 6 * BlockSize + PageSize * BlockSize) {
STXXL_ERRMSG("random_shuffle: insufficient memory, " << M << " bytes supplied,");
M = 6 * BlockSize + PageSize * BlockSize;
STXXL_ERRMSG("random_shuffle: increasing to " << M << " bytes (6 blocks + 1 page)");
}
stxxl::int64 n = last - first; // the number of input elements
int_type k = M / (3 * BlockSize); // number of buckets
stxxl::int64 i, j, size = 0;
value_type* temp_array;
typedef typename stxxl::VECTOR_GENERATOR<
value_type, PageSize, 4, BlockSize, AllocStrategy
>::result temp_vector_type;
temp_vector_type* temp_vector;
// no read buffers and M/B-k write buffers
stxxl::read_write_pool pool(0, M / BlockSize - k);
stack_type** buckets;
// create and put buckets into container
buckets = new stack_type*[k];
for (j = 0; j < k; j++)
buckets[j] = new stack_type(pool, 0);
typedef buf_istream buf_istream_type;
typedef buf_ostream buf_ostream_type;
first.flush(); // flush container
// create prefetching stream,
buf_istream_type in(first.bid(), last.bid() + ((last.block_offset()) ? 1 : 0), 2);
// create buffered write stream for blocks
buf_ostream_type out(first.bid(), 2);
ExtIterator _cur = first - first.block_offset();
// leave part of the block before _begin untouched (e.g. copy)
for ( ; _cur != first; ++_cur)
{
typename ExtIterator::value_type tmp;
in >> tmp;
out << tmp;
}
///// Reading input /////////////////////
// distribute input into random buckets
int_type random_bucket = 0;
for (i = 0; i < n; ++i, ++_cur) {
random_bucket = rand((unsigned)k);
typename ExtIterator::value_type tmp;
in >> tmp;
buckets[random_bucket]->push(tmp); // reading the current input element
}
///// Processing //////////////////////
// resize buffers
pool.resize_write(0);
pool.resize_prefetch(PageSize);
// remaining int space
unsigned_type space_left = M - k * BlockSize - PageSize * BlockSize;
for (i = 0; i < k; i++) {
STXXL_VERBOSE1("random_shuffle: bucket no " << i << " contains " << buckets[i]->size() << " elements");
}
// shuffle each bucket
for (i = 0; i < k; i++) {
buckets[i]->set_prefetch_aggr(PageSize);
size = buckets[i]->size();
// does the bucket fit into memory?
if (size * sizeof(value_type) < space_left) {
STXXL_VERBOSE1("random_shuffle: no recursion");
// copy bucket into temp. array
temp_array = new value_type[(size_t)size];
for (j = 0; j < size; j++) {
temp_array[j] = buckets[i]->top();
buckets[i]->pop();
}
// shuffle
potentially_parallel::
random_shuffle(temp_array, temp_array + size, rand);
// write back
for (j = 0; j < size; j++) {
typename ExtIterator::value_type tmp;
tmp = temp_array[j];
out << tmp;
}
// free memory
delete[] temp_array;
} else {
STXXL_VERBOSE1("random_shuffle: recursion");
// copy bucket into temp. stxxl::vector
temp_vector = new temp_vector_type(size);
for (j = 0; j < size; j++) {
(*temp_vector)[j] = buckets[i]->top();
buckets[i]->pop();
}
pool.resize_prefetch(0);
space_left += PageSize * BlockSize;
STXXL_VERBOSE1("random_shuffle: Space left: " << space_left);
// recursive shuffle
stxxl::random_shuffle(temp_vector->begin(),
temp_vector->end(), rand, space_left);
pool.resize_prefetch(PageSize);
// write back
for (j = 0; j < size; j++) {
typename ExtIterator::value_type tmp;
tmp = (*temp_vector)[j];
out << tmp;
}
// free memory
delete temp_vector;
}
// free bucket
delete buckets[i];
space_left += BlockSize;
}
delete[] buckets;
// leave part of the block after _end untouched
if (last.block_offset())
{
ExtIterator last_block_end = last + (block_type::size - last.block_offset());
for ( ; _cur != last_block_end; ++_cur)
{
typename ExtIterator::value_type tmp;
in >> tmp;
out << tmp;
}
}
}
//! External equivalent of std::random_shuffle (specialization for stxxl::vector)
//! \param first begin of the range to shuffle
//! \param last end of the range to shuffle
//! \param M number of bytes for internal use
template
inline
void random_shuffle(
stxxl::vector_iterator first,
stxxl::vector_iterator last,
unsigned_type M)
{
stxxl::random_number<> rand;
stxxl::random_shuffle(first, last, rand, M);
}
//! \}
STXXL_END_NAMESPACE
#endif // !STXXL_ALGO_RANDOM_SHUFFLE_HEADER
// vim: et:ts=4:sw=4