Hi all,
I'm toying around with the lazy, tail-recursive quick-sort
implementation Michael Fogus and Chris Houser present in their book The
Joy of Clojure:
--8<---------------cut here---------------start------------->8---
(in-ns 'user)
(defn sort-parts
"Lazy, tail-recursive, incremental quicksort. Works against
and creates partitions based on the pivot, defined as 'work'."
[work]
(lazy-seq
(loop [[part & parts] work]
(if-let [[pivot & xs] (seq part)]
(let [smaller? #(< % pivot)]
(recur (list*
(filter smaller? xs)
pivot
(remove smaller? xs)
parts)))
(when-let [[x & parts] parts]
(cons x (sort-parts parts)))))))
(defn qsort [xs]
(sort-parts (list xs)))
--8<---------------cut here---------------end--------------->8---
It works fine for smaller seqs:
--8<---------------cut here---------------start------------->8---
user> (time (first (qsort (take 1000 (iterate dec 500)))))
"Elapsed time: 142.61696 msecs"
-499
--8<---------------cut here---------------end--------------->8---
Well, except that being lazy is about 20 times faster than the standard
sort, although taking only the first (smallest) element of a possibly
large collection is the exact use-case for the lazy-sort, isn't it?
--8<---------------cut here---------------start------------->8---
user> (time (first (sort (take 1000 (iterate dec 500)))))
"Elapsed time: 7.298069 msecs"
-499
--8<---------------cut here---------------end--------------->8---
But that's only the minor issue. The major issue is that I get a
StackOverflowError when the seq passed to qsort becomes too large. And
that error is not in the sorting code, but in clojure itself!
--8<---------------cut here---------------start------------->8---
user> (first (qsort (take 100000 (iterate dec 50000))))
; Evaluation aborted.
No message.
[Thrown class java.lang.StackOverflowError]
Restarts:
0: [QUIT] Quit to the SLIME top level
Backtrace:
0: clojure.core$take$fn__3836.invoke(core.clj:2500)
1: clojure.lang.LazySeq.sval(LazySeq.java:42)
2: clojure.lang.LazySeq.seq(LazySeq.java:60)
3: clojure.lang.RT.seq(RT.java:466)
4: clojure.core$seq.invoke(core.clj:133)
5: clojure.core$filter$fn__3830.invoke(core.clj:2469)
6: clojure.lang.LazySeq.sval(LazySeq.java:42)
7: clojure.lang.LazySeq.seq(LazySeq.java:60)
8: clojure.lang.RT.seq(RT.java:466)
9: clojure.core$seq.invoke(core.clj:133)
10: clojure.core$filter$fn__3830.invoke(core.clj:2469)
11: clojure.lang.LazySeq.sval(LazySeq.java:42)
12: clojure.lang.LazySeq.seq(LazySeq.java:60)
13: clojure.lang.RT.seq(RT.java:466)
14: clojure.core$seq.invoke(core.clj:133)
15: clojure.core$filter$fn__3830.invoke(core.clj:2469)
16: clojure.lang.LazySeq.sval(LazySeq.java:42)
17: clojure.lang.LazySeq.seq(LazySeq.java:60)
18: clojure.lang.RT.seq(RT.java:466)
19: clojure.core$seq.invoke(core.clj:133)
20: clojure.core$filter$fn__3830.invoke(core.clj:2469)
--more--
--8<---------------cut here---------------end--------------->8---
Is that a bug? It occurs in both clojure 1.2.1 and a 1.3 snapshot.
The standard sort function works, though:
--8<---------------cut here---------------start------------->8---
user> (first (sort (take 100000 (iterate dec 50000))))
-49999
--8<---------------cut here---------------end--------------->8---
Bye,
Tassilo
--
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
