Hi
I'm playing with the new transient/persistent! features in Clojure. I
have implemented quicksort as described on wikipedia (http://
en.wikipedia.org/wiki/Quicksort#Algorithm). Here is the code:
(defn swap-index! [v i j]
(let [tmp (v i)]
(assoc! v i (v j))
(assoc! v j tmp)))
(defn partition! [v left-index right-index pivot-index]
(let [pivot-value (v pivot-index)]
(swap-index! v pivot-index right-index)
(loop [i left-index store-index left-index]
(if (< i right-index)
(if (<= (v i) pivot-value)
(do (swap-index! v i store-index)
(recur (inc i) (inc store-index)))
(recur (inc i) store-index))
(do (swap-index! v store-index right-index)
store-index)))))
(defn qsort! [v left right]
(when (> right left)
(let [pivot-index left
pivot-new-index (partition! v left right pivot-index)]
(qsort! v left (dec pivot-new-index))
(qsort! v (inc pivot-new-index) right))))
(defn qsort [v]
(let [tv (transient v)]
(qsort! tv 0 (dec (count v)))
(persistent! tv)))
This sorts a vector of doubles in about 6000-7000 msec on my machine:
user=> (def s (time (qsort (rvector 1000000))))
"Elapsed time: 6681.35889 msecs"
This is much faster than the classical functional programming
"quicksort":
; From http://rosettacode.org/wiki/Quicksort#Clojure
(defn qsort-rs [[pivot & xs]]
(when pivot
(let [smaller #(< % pivot)]
(lazy-cat (qsort (filter smaller xs))
[pivot]
(qsort (remove smaller xs))))))
user=> (def s (time (doall (qsort-rs (rvector 1000000)))))
"Elapsed time: 32565.537389 msecs"
The Java sort however is about 5 times faster then the transient
version:
user=> (def s (time (sort (rvector 1000000))))
"Elapsed time: 1354.427239 msecs"
Can you give any hints on how I can make the transient sort faster? I
would like to get as close as possible to the native Java speed.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Here is the rvector function as used in the timing tests (for
completeness):
(defn rvector [n]
(loop [i 0 v (transient [])]
(if (< i n)
(recur (inc i) (conj! v (Math/random)))
(persistent! v))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
These new clojure features are so much fun!
--~--~---------~--~----~------------~-------~--~----~
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
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
