On Aug 4, 11:08 am, Jonas <[email protected]> wrote:
> 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)))
I think Rich mentioned on IRC that you should not reuse the transient
vector binding after an operation; that it works is merely an
implementation detail. The transient documentation page also says
tells to "capture return value, use for next call". So:
(defn swap-index! [tv i j]
(let [tmp (tv i)]
(-> tv
(assoc! i (v j))
(assoc! j tmp))))
And similar modifications for the quicksort below.
>
> (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":
>
> ; Fromhttp://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.
This is partially comparing apples to oranges though: sort returns a
lazy seq, while
the quicksort algorithm produces a proper vector.
Anyway, (nth v i) might be somewhat faster than (v i) because it gets
inlined. I did not try, though.
Below is code that avoids reusing the reference to v:
(defn swap-index! [v i j]
(let [tmp (nth v i)]
(-> v
(assoc! i (nth v j))
(assoc! j tmp))))
(defn partition! [v left-index right-index pivot-index]
(let [pivot-value (nth v pivot-index)
new-v (swap-index! v pivot-index right-index)]
(loop [v new-v, i left-index, store-index left-index]
(if (< i right-index)
(if (<= (nth v i) pivot-value)
(recur (swap-index! v i store-index) (inc i) (inc store-
index))
(recur v (inc i) store-index))
[(swap-index! v store-index right-index)
store-index]))))
(defn qsort! [v left right]
(if (> right left)
(let [pivot-index left
[new-v pivot-new-index] (partition! v left right pivot-
index)]
(-> new-v
(qsort! left (dec pivot-new-index))
(qsort! (inc pivot-new-index) right))))
v)
(defn qsort [v]
(let [tv (transient v)]
(qsort! tv 0 (dec (count v)))
(persistent! tv)))
--
Jarkko
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
