A simple and fast permutation generator (6)

February 22, 2008 at 11:55 pm Leave a comment

It’s been a while since the last permutation generator article. Mainly because of lack of time, but also because I found out about std::next_permutation. I have been looking at that for a while, and although it’s far from simple, it’s somewhat faster than the fastest installment of the recursive algorithm. The speed of std::next_permutation is also lower bound to O(N!) but still faster overall. For generating all the permutations of 11 items, next_permutation’s runtime is about 2/3 of the time taken by the recursive algo.

However, all that won’t stop me from showing you how to make the original algorithm faster. A key component in improving speed was doing away with std::queue, and replacing it with a custom, dedicated and very specific fixed length queue. This queue has got very few methods, and does not offer lots of flexibility. It does not even have a method to get the size. How we manage to write the algorithm without a size method for the queue is something that will be tackled in another future post.

For today, I give you the source code for the fixed size queue. Have fun.

template< size_t  ac_nSize >
class CFixedSizeQueue
{
  public:

    CFixedSizeQueue( const size_t ac_FirstValue )
    : mv_nFront( 0 )
    , mv_nBack ( 0 )
    {
      mv_Array[ mv_nFront ] = ac_FirstValue ;
    }

    size_t  pop()
    {
      const size_t  c_Result = mv_Array[ mv_nFront ] ;

      mv_nFront =
        mv_nFront < sc_nSize - 1 ? mv_nFront + 1 : 0 ; 

      return c_Result ;
    }

    void    push( const size_t   ac_Value )
    {
      mv_nBack =
        mv_nBack < sc_nSize - 1 ? mv_nBack + 1 : 0 ; 

      mv_Array[ mv_nBack ] = ac_Value ;
    }

    size_t  front() const
    {
      return mv_Array[ mv_nFront ] ;
    }

  private:

    static const size_t sc_nSize  = ac_nSize ;          

    typedef size_t  mt_Array[ sc_nSize ] ;

    size_t        mv_nFront ;
    size_t        mv_nBack  ;
    mt_Array      mv_Array  ;
};

CFixedSizeQueue< gc_nSize >    Pool( 0 ) ;

A couple of extra notes on this class :

  • CFixedSizeQueue demands that there is at least one element in the queue at all times. This requires to pass the first item in the ctor of the queue. Yet another thing that you wouldn’t want in a generic queue.
  • The method of clamping the indices, mv_nBack and mv_nFront, to values within the bounds of the array looks kind of slow, with the ternary operator, but it turned out to be faster than either using the modulo operator – % – or than some form of bit masking using the bit-wise and operator – & -.
  • Another thing you might have noticed is that the pop method returns the element that is popped. This also save a couple of cycles compared to a separate Pool.front and Pool.pop sequence.
  • There is no error or bounds checking whatsoever, nor is there any defense against degenerate use. This class is definitely not liberal in what it accepts. Something that’s quite ok if you know what you are doing, but may not be suited for a library.
  • WordPress’s pre-formatted text handling is driving me nuts.
Advertisements

Entry filed under: Command Line.

A simple and fast permutation generator (4) DIY blog post :

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Trackback this post  |  Subscribe to the comments via RSS Feed


Recent Posts

Categories


%d bloggers like this: