In my experiments my code is still about 1.5x slower than seq-utils.shuffle. The current implementation of seq-utils.shuffle simply converts to an ArrayList, calls java.util.Collections.shuffle, and converts back to a Clojure sequence. Here's a quick experiment:
user> (def v (vec (range 500000))) #'user/v user> (time (do (doall (shuffle v)) nil)) "Elapsed time: 449.001 msecs" nil user> (def a (java.util.ArrayList. v)) #'user/array user> (time (do (java.util.Collections/shuffle a) nil)) "Elapsed time: 102.331 msecs" nil Each of those timings were repeated several things to make sure they were sufficiently stable. The conclusion is that java.util.Collections.shuffle is plenty fast. Most of the time (over 3/4ths) taken by seq-utils.shuffle goes into conversions. But even 450 ms for shuffling a 500,000 element list isn't too bad. For comparison, the time to sum that many elements with #(reduce + %) is about 50 ms. -Per On Mon, Apr 5, 2010 at 5:56 PM, Sean Devlin <[email protected]> wrote: > If this is significantly faster than c.c.seq/shuffle, you should > submit a patch. I know Rich was complaining about the speed of that > fn in the past. > > Also, I'd reverse the arg order of with-transient. I think > > (with-transient f x) > > reads easier. Also, it should probably end with a bang, because I > don't think it's safe in the STM. > > Great work guys. > > Sean > > On Apr 5, 12:52 am, Per Vognsen <[email protected]> wrote: >> On Mon, Apr 5, 2010 at 11:33 AM, Lee Spector <[email protected]> wrote: >> >> > Ah -- maybe that foiled my timings too. I didn't expect it to be fast -- >> > just clear (at least to this Lisp programmer). >> >> Embrace recursion combinators! They are warm and fuzzy! >> >> Here's a gist of the final cleaned up version of my code. The code >> itself is only three lines; the rest consists of very general purpose >> utilities that I find myself using again and again. >> >> http://gist.github.com/356035 >> >> -Per >> >> >> >> > -Lee >> >> > On Apr 5, 2010, at 12:11 AM, Per Vognsen wrote: >> >> >> Wow, you're right. The partial laziness of his code was foiling my >> >> benchmark. >> >> >> -Per >> >> >> On Mon, Apr 5, 2010 at 11:05 AM, Mark Engelberg >> >> <[email protected]> wrote: >> >>> On my system, knuth-shuffle performs several times faster than Spector's >> >>> recursive functional shuffle on smallish lists, and the difference grows >> >>> even more dramatic as the list grows, which is what I'd expect (since >> >>> knuth-shuffle is O(n) and shuffle is O(n^2)). >> >> >>> -- >> >>> You received this message because you are subscribed to the Google >> >>> Groups "Clojure" group. >> >>> To post to this group, send email to [email protected] >> >>> Note that posts from new members are moderated - please be patient with >> >>> your >> >>> first post. >> >>> 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 >> >> >> -- >> >> You received this message because you are subscribed to the Google >> >> Groups "Clojure" group. >> >> To post to this group, send email to [email protected] >> >> Note that posts from new members are moderated - please be patient with >> >> your first post. >> >> 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 >> >> >> To unsubscribe, reply using "remove me" as the subject. >> >> > -- >> > Lee Spector, Professor of Computer Science >> > School of Cognitive Science, Hampshire College >> > 893 West Street, Amherst, MA 01002-3359 >> > [email protected],http://hampshire.edu/lspector/ >> > Phone: 413-559-5352, Fax: 413-559-5438 >> >> > Check out Genetic Programming and Evolvable Machines: >> >http://www.springer.com/10710-http://gpemjournal.blogspot.com/ >> >> > -- >> > You received this message because you are subscribed to the Google >> > Groups "Clojure" group. >> > To post to this group, send email to [email protected] >> > Note that posts from new members are moderated - please be patient with >> > your first post. >> > 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 > > -- > You received this message because you are subscribed to the Google > Groups "Clojure" group. > To post to this group, send email to [email protected] > Note that posts from new members are moderated - please be patient with your > first post. > 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 -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to [email protected] Note that posts from new members are moderated - please be patient with your first post. 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
