[boost] Re: Thoughts on partial_random_shuffle

From: Ross MacGregor (ross__macgregor_at_[hidden])
Date: 2003-10-12 15:58:56

The average application does not utilize randomization but some 
diciplines use it extensively and are very interested in optimizing 
these operations, like games and simulation programming for instance.

The partial_random_shuffle() algorithm would be useful when you have a 
random access container filled with a large number of complex items and 
you wish to select a random subset of elements from it.

Now you can do this in one of two ways utilizing 
partial_random_shuffle() or the less efficient random_shuffle().

A) Shuffle the container

size_t elements_wanted = 25;

// Partially shuffle container
partial_random_shuffle(
     thingies.begin(),
     thingies.begin() + elements_wanted,
     thingies.end());

// -OR- Shuffle entire container
//random_shuffle(
//    thingies.begin(),
//    thingies.end());

for_each(
     thingies.begin(),
     thingies.begin() + elements_wanted,
     process_thingy);

B) Create a list of random indices or pointers

size_t elements_wanted = 25;
vector<size_t> indices;

for(size_t i = 0; i < thingies.size(); i++)
     indices.push_back(i);

// Partially shuffle container
partial_random_shuffle(
     indices.begin(),
     indices.begin() + elements_wanted,
     indices.end());

// -OR- Shuffle entire container
//random_shuffle(
//    indices.begin(),
//    indices.end());

for_each(
     indices.begin(),
     indices.begin() + elements_wanted,
     process_indexed_thingy);

As I was saying it really is just an optimization because the standard 
random_shuffle may be used in its place, but why not have a standard 
implementation rather than having people reinvent the wheel for this 
basic algorithm?

Paul, you are right. I should change the parameter names to (begin, 
shuffle_end, end). This matches the specification for partial sort and 
works the same way. The begin-end parameters indicate the range of 
elements for the selection process and the begin-shuffle_end parameters 
indicate the subset of elements to be randomized.

----------------REVISED CODE------------------

#define BOOST_PARTIAL_RANDOM_SHUFFLE_HPP_INCLUDED

#include <cstdlib>

namespace boost {

//  This is a variation of the random_shuffle algorithm
//  that allows you to partially shuffle an STL container.
//  Elements from the subrange ("begin" to "shuffle_end") will
//  be swapped with random elements from the entire range
//  ("begin" to "end").
//
//  Usage:
//    // We have 1000 things to index
//    vector<int> indices;
//    for(int i=0; i<1000; i++) indices.push_back(i);
//    // select 100 random indices
//    partial_random_shuffle(
//        indices.begin(),
//        indices.begin() + 100,
//        indices.end());
//    indices.resize(100);

//  Contributed by Ross MacGregor

template<class RandomAccessIter>
inline void
partial_random_shuffle(
         RandomAccessIter begin,
         RandomAccessIter shuffle_end,
         RandomAccessIter end)
{
     // our travelling iterator
     RandomAccessIter & p = begin;

     // find number of elements to the end
     size_t range = std::distance(p, end);

     // check for empty range
     if( range != 0 )
     {
         // unable to swap last element
         if( shuffle_end == end )
             --shuffle_end;

         // must have more than 1 element
         // for swap operation to work
         if( --range )
         {
             while( p != shuffle_end )
             {
                 size_t n( rand() % range );

                 std::swap(*p,*(p + n));

                 --range;
                 ++p;
             }
         }
     }
}

template<class RandomAccessIter, class RandomNumberGenerator>
inline void
partial_random_shuffle(
         RandomAccessIter begin,
         RandomAccessIter shuffle_end,
         RandomAccessIter end,
         RandomNumberGenerator & rand_func)
{
     // our travelling iterator
     RandomAccessIter & p = begin;

     // find number of elements to the end
     size_t range = std::distance(p, end);

     // check for empty range
     if( range != 0 )
     {
         // unable to swap last element
         if( shuffle_end == end )
             --shuffle_end;

         // must have more than 1 element
         // for swap operation to work
         if( --range )
         {
             while( p != shuffle_end )
             {
                 size_t n( rand_func(range) );

                 std::swap(*p,*(p + n));

                 --range;
                 ++p;
             }
         }
     }
}

} // namespace boost

#endif  // BOOST_PARTIAL_RANDOM_SHUFFLE_HPP_INCLUDED

Paul A. Bristow wrote:
> Looks sensible - but can you give example(s)/references where this would be
> useful in practice?
> 
> Paul
> 
> (Is p == shuffle_begin? Why are there not 4 parameters, thingys begin and end,
> and both shuffle_begin and shuffle_end?)
> 
> Paul A Bristow, Prizet Farmhouse, Kendal, Cumbria, LA8 8AB  UK
> [phone]   Mobile [phone]
> mailto:pbristow_at_[hidden]