On Tue, 28 Dec 2010 19:50:28 +0530
Baishampayan Ghose <b.gh...@gmail.com> wrote:
> Hello,
>
> I tried writing a naive implementation of quicksort using an
> accumulator. Right now, the code is stack-consuming and returns a
> stackoverflowerror on large lists. Is there any way to prevent it from
> consuming stack with some changes? The code is as follows -
You don't say what your test data is, but pretty much any quicksort
implementation will have some nasty test cases for which its memory
usage is nasty and its performance is worse. Given that this is a
simple implementation, data that is already sorted is the degenerate
case.
I don't think you can keep it from using any stack - a non-recursive
implementation would just have to maintain it's own stack state. You
can do some things to make it use less stack, though.
First, deal with sorted data better by picking a median value from
coll instead of the first one.
Once the sequences get small enough, change to a non-recursive sorting
method to sort them.
If you're up to serious refactoring, fix the code to generate the
partitions inside of qsort*, and then use recur for the tail call of
qsort* - and make sure that call is on longer of less and greater.
<mike
> (declare qsort qsort* partify)
>
> (defn partify
> [item coll [less equal greater] acc]
> (if (empty? coll)
> (qsort* less (concat equal (qsort* greater acc)))
> (let [[head & tail] coll]
> (cond
> (< head item) (recur item tail [(cons head less) equal greater] acc)
> (> head item) (recur item tail [less equal (cons head greater)] acc)
> :else (recur item tail [less (cons head equal) greater] acc)))))
>
> (defn qsort*
> [coll acc]
> (if-let [coll (seq coll)]
> (partify (first coll) (rest coll) [[] [(first coll)] []] acc)
> acc))
>
> (defn qsort
> "Perform Quicksort, with apologies to C.A.R. Hoare"
> [coll]
> (if-let [coll (seq coll)]
> (qsort* coll [])
> []))
>
> Regards,
> BG
>
--
Mike Meyer <m...@mired.org> http://www.mired.org/consulting.html
Independent Network/Unix/Perforce consultant, email for more information.
O< ascii ribbon campaign - stop html mail - www.asciiribbon.org
--
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
