laziness, impatience, and hubris | |
PerlMonks |
Re: When the Best Solution Isn'tby thraxil (Prior) |
on Sep 23, 2002 at 03:44 UTC ( [id://199996]=note: print w/replies, xml ) | Need Help?? |
interesting. the incorrect solution that your toolsmith provided has inspired me to come up with a variation which i think is correct:
kind of a 'randomized schwartzian transform' approach. it benchmarks slightly faster than the standard Fisher-Yates shuffle but not quite as fast as the broken version. mine and Fisher-Yates are both going to be linear with the size of the array and you really can't do any better than that and still have a correct solution. i'm honestly baffled as to why the broken one runs so quickly. my best guess is that getting different values on each comparison in some cases confuses qsort to the point where it thinks it's done before it really is. alternatively though it seems like if you get the wrong series of random numbers, it could make qsort take even longer than normal.
In Section
Meditations
|
|