GNU Scientific Library - Bugs: bug #51104, gsl_permutation_next efficiency
You are not allowed to post comments on this tracker with your current authentication level.
bug #51104: gsl_permutation_next efficiency
Submitter: | Patrick Alken <psa> | ||
Submitted: | Wed 24 May 2017 08:45:59 AM UTC | ||
Category: | Performance | Severity: | 3 - Normal |
Operating System: | Status: | None | |
Assigned to: | None | Open/Closed: | Open |
Release: |
Wed 24 May 2017 08:46:44 AM UTC, comment #1: |
Patrick Alken <psa>![]() |
Wed 24 May 2017 08:45:59 AM UTC, original submission:
from pgsinitsyn =at= gmail =dot= com
|
Patrick Alken <psa>![]() |
Depends on the following items: None found
Items that depend on this one: None found
Follow 2 latest changes.
Date | Changed by | Updated Field | Previous Value | => | Replaced by |
---|---|---|---|---|---|
2017-05-24 | psa | Attached File | - | ![]() |
Added benchmark.pdf, #40775 |
Attached File | - | ![]() |
Added result.txt, #40776 |
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