### Re: Speed/Efficiency tweaks for a fannkuch benchmark script?

by robin (Chaplain)
 on Dec 01, 2005 at 13:34 UTC ( #513261=note: print w/replies, xml ) Need Help??

That's a mighty good permutation algorithm you're using. I'm curious as to where you came across it. (A few years ago I did a fair bit of investigation into permutation generation, and this algorithm was the fastest pure-Perl one I could find by quite a margin. Your code looks remarkably similar to mine!)

It may also be worth looking at the algorithm used in tye's Algorithm::Loops, which is jolly clever. I haven't compared it directly with this one, though if I had to guess, I would guess this one is probably still faster.

PS. I still haven't figured out how you can get away with doing nothing when \$copy->[-1] == @\$copy. What's the trick?

Update: Okay, I've got it. That's pretty clever. Here's my proof that it works.

Lemma: for every \$n ≥ 1, there is some permutation of (1..\$n+1) that takes more flips than any permutation of (1..\$n).
Proof. Let @a be a permutation of (1..\$n) that takes as many flips as possible, say it takes \$flip flips; and consider the permutation (\$n+1, reverse @a). Clearly this takes (\$flip+1) flips.

Now, if \$copy->[-1] == @\$copy then the last element can never be moved by the flipping, and so this will take the same number of flips as @\$copy[0..\$#\$copy-1]. By the Lemma, this is less than the maximum number of flips.

Replies are listed 'Best First'.
Re^2: Speed/Efficiency tweaks for a fannkuch benchmark script?
by thundergnat (Deacon) on Dec 01, 2005 at 15:40 UTC
That's a mighty good permutation algorithm you're using. I'm curious as to where you came across it. (A few years ago I did a fair bit of investigation into permutation generation, and this algorithm was the fastest pure-Perl one I could find by quite a margin. Your code looks remarkably similar to mine!)
That was a subroutine I had found on the web a while ago when I was looking for how to do fast permutations. I didn't really remember exactly where I got it, (I had stored it away in my folder of cool and interesting perl stuff,) but in looking at your web page, there is little doubt that it was from there. Sorry for not attributing it correctly, and thank you for making it available.
No need to be sorry. I'm glad you found it useful!

In any case, I got the algorithm from a C program posted to alt.sources in 1990 by Matt Day, who I haven't been able to track down.

Re^2: Speed/Efficiency tweaks for a fannkuch benchmark script?
by Roy Johnson (Monsignor) on Dec 02, 2005 at 16:00 UTC
I noticed that your fast permutation algorithm passes an arrayref, but then copies the values out. There's no particular savings there compared to passing the array. That and a few other micro-optimizations squeezed 210+% more speed out (if you don't print — the savings are probably less significant with printing turned on.) Code (update: fixed, reducing savings, as expected) follows.

Caution: Contents may have been coded under pressure.
Interesting, but broken. (Uncomment the print and you'll see what I mean!)

You can fix it by adding

```  local @_ = @_;
to the beginning of the sub, but that presumably makes it slower again.

Create A New User
Node Status?
node history
Node Type: note [id://513261]
help
Chatterbox?
 [tobyink]: 1nickt: your code? [LanX]: pryrt: yeah, that's why I didn't consider, but the last >10 anonymous posts are from the same troll-person [jdporter]: is there a module for expanding tabs in text? [jdporter]: A: yes. [Lady_Aleena]: I don't know how hard it will be to get out of that mess. [LanX]: M-x untabify [choroba]: I don't think they're multiple people. I was told "he or she" sounds old-fashioned and "they" is the way to say it [pryrt]: Those others were definitely offensive or unequivocably rude, I agree. [choroba]: (well, it comes from the 14th century, so labelling it as "modern" doesn't seem appropriate) [Your Mother]: "They" is becoming accepted but it irritates me sometimes. I tend to just pick she or he randomly or try to use "one."

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (17)
As of 2017-05-24 20:18 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My favorite model of computation is ...

Results (186 votes). Check out past polls.