3 ms·

Won't that explode somewhat performance-wise once you have more than a handful of cards? It looks like something along the lines of O(n^2)...

by crux_ 17y ago

astine 17y ago
As it's written I'll blow the call stack before I see a performance decrease. :) Actually, the algorithm is O(n), it's essentially a list reversal with a call to random inserted. In psuedocode: oldlist = [...] newlist = [] if oldlist not empty do x = remove random from oldlist insert x into newlist repeat Of course, I'm ignoring the complexity of 'butnth' in that assesment, but this was just a 'first instinct' sort of deal.
- kmcgivney 17y ago
  I didn't like the butnth. I get an allergic reaction to append. Blame Ken Tilton. (defun shuffle-in-place (l) (cond ((null l) nil) (t (rotatef (nth 0 l) (nth (random (length l)) l)) (shuffle-in-place (rest l)))) l) (defun shuffle (l) (shuffle-in-place (copy-list l)))
  - astine 17y ago
    Blame Ken Tilton. I do. Always. One could use nconc instead of append, but that's not where the processor cycles are being lost as far as I can tell.
- crux_ 17y ago
  It's not O(n): both 'nth' and 'butnth' are themselves O(n), and get called 'n' times. I'm fairly certain you'll end up with O(n^2) unless you introduce mutation. I'm also fairly certain there is no purely functional O(n) algorithm. ;)
  - astine 17y ago
    You're right of course; I'm not looking very deeply. I'm also fairly certain there is no purely functional O(n) algorithm. (defun nth (index list) (if (zerop index) (first index) (nth (1- index) (rest list))))
    - crux_ 17y ago
      I meant for perfect shuffling, not 'nth'. :) This is for you, since I've already had three today & the brainos in your nth implementation are a strong indication for its prescription: http://www.espressoguide.net/resources/images/articles/A002Image01.jpg http://www.espressoguide.net/resources/images/articles/A002I... Cheers!

Won't that explode somewhat performance-wise once you have more than a handful of cards? It looks like something along the lines of O(n^2)...

by crux_ 17y ago

Won't that explode somewhat performance-wise once you have more than a handful of cards? It looks like something along the lines of O(n^2)...

astine 17y ago

As it's written I'll blow the call stack before I see a performance decrease. :) Actually, the algorithm is O(n), it's essentially a list reversal with a call to random inserted. In psuedocode: oldlist = [...] newlist = [] if oldlist not empty do x = remove random from oldlist insert x into newlist repeat Of course, I'm ignoring the complexity of 'butnth' in that assesment, but this was just a 'first instinct' sort of deal.

kmcgivney 17y ago
I didn't like the butnth. I get an allergic reaction to append. Blame Ken Tilton. (defun shuffle-in-place (l) (cond ((null l) nil) (t (rotatef (nth 0 l) (nth (random (length l)) l)) (shuffle-in-place (rest l)))) l) (defun shuffle (l) (shuffle-in-place (copy-list l)))
- astine 17y ago
  Blame Ken Tilton. I do. Always. One could use nconc instead of append, but that's not where the processor cycles are being lost as far as I can tell.
crux_ 17y ago
It's not O(n): both 'nth' and 'butnth' are themselves O(n), and get called 'n' times. I'm fairly certain you'll end up with O(n^2) unless you introduce mutation. I'm also fairly certain there is no purely functional O(n) algorithm. ;)
- astine 17y ago
  You're right of course; I'm not looking very deeply. I'm also fairly certain there is no purely functional O(n) algorithm. (defun nth (index list) (if (zerop index) (first index) (nth (1- index) (rest list))))
  - crux_ 17y ago
    I meant for perfect shuffling, not 'nth'. :) This is for you, since I've already had three today & the brainos in your nth implementation are a strong indication for its prescription: http://www.espressoguide.net/resources/images/articles/A002Image01.jpg http://www.espressoguide.net/resources/images/articles/A002I... Cheers!