Possible improvement in next_permutation implementation
David GONZALEZ MALINE
David.Gonzalez.Maline@cern.ch
Thu Mar 13 16:26:00 GMT 2008
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.
>
More information about the Libstdc++
mailing list