[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Bug-gsl] [bug #51104] gsl_permutation_next efficiency
From: |
Patrick Alken |
Subject: |
[Bug-gsl] [bug #51104] gsl_permutation_next efficiency |
Date: |
Wed, 24 May 2017 04:46:44 -0400 (EDT) |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36 |
Follow-up Comment #1, bug #51104 (project gsl):
from rsmith =at= whistlin =dot= com
I think Pavel Sinitcyn's code gives a more literal translation of step L3 in
Knuth's description of the algorithm ("Algorithm L" in AoCP vol 4, page 319).
The change decreases the running time by over 10% in my tests. I haven't
tested for accuracy, though.
Incidentally, the existing version of gsl_permutation_next() in
permutatiion.c
has a superfluous check in the boolean expression on line 155:
(p->data[j] > p->data[i]) && (p->data[j] < p->data[k])
The while loop starting on line 141 guarantees that p->data[j] < p->data[k]
for
i<k<j (Knuth explains this in step L3). But I think the slow down is caused
by
the structure of the for loop, which seems awkward compared to the
straightforward textbook version.
Regis
_______________________________________________________
Reply to this item at:
<http://savannah.gnu.org/bugs/?51104>
_______________________________________________
Message sent via/by Savannah
http://savannah.gnu.org/