transient quicksort | Jonas | 8/4/09 1:08 AM | 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! |

Re: transient quicksort | Albert Cardona | 8/4/09 5:55 AM | Jonas wrote:
(let [pivot-value (v pivot-index)] could be: (let [pivot-value (int (v pivot-index))]
Albert -- |

Re: transient quicksort | Jonas | 8/4/09 5:42 AM | I get ~8% performance boost by turning swap-index! into a macro: (defmacro swap-index! [v i j] |

Re: transient quicksort | Jonas Enlund | 8/4/09 6:03 AM | On Tue, Aug 4, 2009 at 3:55 PM, Albert Cardona<sapr...@gmail.com> wrote: I have tried to add type hints but they don't seem to speed things up. (defn partition! [....] |

Re: transient quicksort | Mark Addleman | 8/4/09 7:42 AM | I haven't tried the code, so caveat emptor:
If you convert partition to a macro *AND* use type-hints, I suspect you'll see a win. The issue here is the primitive boxing that must occur when when calling a function. It's my hope that when a macro is used with the appropriate type hints, the Clojure compiler won't box the primitives but I don't know that. On Aug 4, 6:03 am, Jonas Enlund <jonas.enl...@gmail.com> wrote: > ...)- Hide quoted text - > > - Show quoted text - |

Re: transient quicksort | Jarkko Oranen | 8/4/09 10:49 AM | On Aug 4, 11:08 am, Jonas <jonas.enl...@gmail.com> wrote: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. > ; Fromhttp://rosettacode.org/wiki/Quicksort#Clojure > (defn qsort-rs [[pivot & xs]]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: (let [tmp (nth v i)] (-> v (assoc! i (nth v j)) (assoc! j tmp)))) (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])))) (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) -- Jarkko |

Re: transient quicksort | jdz | 8/5/09 1:32 AM | On Aug 4, 11:08 am, Jonas <jonas.enl...@gmail.com> wrote: > Can you give any hints on how I can make the transient sort faster? IYou are comparing apples to oranges. Clojure's persistent vectors do not magically turn into Java arrays when using the new transients feature; they are still good old persistent vectors, with the added bonus that some operations can be done by mutating existing structure. But this structure is still the same old awesome piece of persistent vector! A bit lame analogy, but maybe helps some people understand the point I'm trying to make. It's like the good old story about how MySQL is "faster" than PostgreSQL. Not. At least if you want safety. What the native sort function does is just what I wanted to suggest you do: turn the persistent vector into a plain old array, sort that, and then convert the sorted array back into a Clojure data structure. |

Re: transient quicksort | Jonas Enlund | 8/4/09 9:56 PM | 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. Ok, I will try that Nice, thank you! > > -- > Jarkko > > > |