On Aug 26, 11:54 pm, "Shawn Hoover" <[EMAIL PROTECTED]> wrote:
> I needed to shuffle a vector so I decided to try doing it functionally.
> Below is the implementation and a couple exercise functions, inspired
> byhttp://en.wikipedia.org/wiki/Fisher-Yates_shuffleandhttp://szeryf.wordpress.com/2007/06/19/a-simple-shuffle-that-proved-n...
> .
>
> A version of sort-by that computes each key only once does most of the work;
> shuffle is trivial using that. I haven't tried it on data other than
> integers yet. The speed is decent under half a million integers, but the
> space cost is high, requiring a larger Java heap to sort a million. As soon
> as I got it working I discovered java.util.Collections/shuffle, which blows
> my implementation away on speed and space, comfortably sorting 10 million.
>
> I'm open to feedback on the algorithm or improving my Clojure. For one
> thing, it seems like there must be a cleaner way to handle my use of reduce
> in test-shuffle-uniformity. I like reduce for looping functionally, but in
> this case I just need to run n times regardless of the specific values in
> (range n). Is that use case common enough for some kind of reduce-times
> macro?
>
While I appreciate the intellectual exercise (and would point you to
http://okmij.org/ftp/Haskell/perfect-shuffle.txt if you haven't seen
it), one of the nice things about Clojure is that you aren't trapped
without mutability when you need it, and you need it here since there
is a known O(n) in-place implementation and you can't do better than
O(n log n) otherwise. Your implementation leveraging Java's
Collections/shuffle _is_ functional, it neither alters its arg nor has
any other side effects, and is the right way to implement this, since
Collections/shuffle has seen a lot of use/testing. See Clojure's sort,
for instance. It's ok to leverage Java's speed inside a functional
interface. For example, Clojure's persistent maps and vectors couldn't
be as nearly fast as they are if they were implemented purely
functionally.
Rich
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to clojure@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
