Hi, Thank's for pointing this out for me. I didn't realize how to use these constructs correctly. Seeing the !-mark i just thought that assoc! was to be used like set! set-car! set-cdr! in Scheme... my mistake.
On Tue, Aug 4, 2009 at 8:49 PM, Jarkko Oranen<chous...@gmail.com> wrote: > > On Aug 4, 11:08 am, Jonas <jonas.enl...@gmail.com> 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. Ok, I will try that > > 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))) Nice, thank you! > > -- > Jarkko > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
