Re: Possible improvement in next_permutation implementation

[David GONZALEZ MALINE <David dot Gonzalez dot Maline at cern dot ch>]

Hello Paolo,

I have tried a few different tests. I changed the implementation of the 
algorithm in the STL using the one we have here and the time was 
basically the same one as the current algorithm. It looks like you are 
right when you think it's due to the use of bidirectional iterators, 
while in ROOT we use direct access to the arrays.

I guess it was at least worth trying!
Thanks a lot.
David

-----

This is the code I tried:

template<typename _BidirectionalIterator>
bool
next_permutation(_BidirectionalIterator __first,
                _BidirectionalIterator __last)
{

  // concept requirements
  __glibcxx_function_requires(_BidirectionalIteratorConcept<
                              _BidirectionalIterator>)
  __glibcxx_function_requires(_LessThanComparableConcept<
        typename iterator_traits<_BidirectionalIterator>::value_type>)
  __glibcxx_requires_valid_range(__first, __last);

  if (__first == __last)
     return false;
  _BidirectionalIterator __i = __first;
  ++__i;
  if (__i == __last)
    return false;
  __i = __last;
  --__i;

  _BidirectionalIterator __ii = __i;
  while ( --__i != __first )
  {
     if ( *__i < *__ii )
     {
        break;
     }
     __ii = __i;
  }

  __ii = __i;

  __i = __last;
  //--__i;

  while ( --__i != __ii )
  {
     if ( *__ii < *__i )
     {
        std::iter_swap(__i, __ii);
        std::reverse(++__ii, __last);
        return true;
     }
  }
  std::reverse(__ii, __last);
  return false;
}

Paolo Carlini wrote:
> David GONZALEZ MALINE wrote:
>   
> > I wonder whether it would be possible to make an implementation of the
> > standard library method closer to what the gsl algorithm does. The
> > three algorithms are intrinsically the same one, but the way they have
> > been implemented differ in the small details, and that is what makes
> > the difference in time.
> >     
> I'm still checking a few things and performing microbenchmarks, but
> apparently the performance gap is due to the fact that
> std::next_permutation works with generic bidirectional iterators (i.e,
> in the implementation we lack an overload optimized for random access
> iterators).
>
> Paolo.
>