You've been bitten by laziness. Wrapping the concats in (doall ...) will remove the stack overflows. The speed drop is probably from the concats adding many additional list traversals. To fix both requires a restructuring. You can change rst to a vector and use conj instead of concat to append to it. Also (concat rst c) can be changed to (into rst c) then. Since you're using (count c) right at the start anyway, the seq is fully realized and you don't get any real benefits from laziness here, just gotchas, so using a vector is fine. The callee can always call seq explicitly on the vector that will now be returned, when the vector won't work as a drop-in replacement for a seq (say because conj is called on it to add to the beginning, and changing it to a vector makes it add to the end instead).
Of course, once rst is a vector, and you've given up on using laziness in any way, you can go farther and use vectors throughout the sort, converting the input collection to one right off the bat. Then you can swap adjacent elements using a pair of assoc calls with integer keys, and you may get even more speedups if you use transient and persistent after making *that* change. On Fri, Apr 19, 2013 at 1:05 PM, Ben Wolfson <[email protected]> wrote: > I don't know about the speed, but I suspect the stack overflow results > from many nested calls to concat, which will by itself result in stack > overflows. > > > On Fri, Apr 19, 2013 at 9:57 AM, Miles Wen <[email protected]> wrote: > >> Hi all, >> I wrote a bubble-sort program in clojure: >> >> (defn bubble-sort >> [col] >> (letfn [(outter-loop >> [cc i] >> (if (< i 1) >> cc >> (letfn [(inner-loop >> [c j] >> (if (> j (- i 2)) >> c >> (let [_1st (first c) >> _2nd (second c) >> others (rest (rest c))] >> (if (> _1st _2nd) >> (cons _2nd (inner-loop (cons _1st others) >> (inc j))) >> (cons _1st (inner-loop (cons _2nd others) >> (inc j)))))))] >> (recur (inner-loop cc 0) (dec i)))))] >> (outter-loop col (count col)))) >> >> It works quite well, it could sort 1000 elements in no time. >> >> and I also rewrite it to a tail-recursive version: >> >> (defn bubble-sort-tail >> [col] >> ((fn >> [cc i] >> (if (< i 1) >> cc >> (let [inner-loop (fn >> [c j rst] >> (if (> j (- i 2)) >> (concat rst c) >> (let [_1st (first c) >> _2nd (second c) >> others (rest (rest c))] >> (if (> _1st _2nd) >> (recur (cons _1st others) (inc j) (concat >> rst [_2nd])) >> (recur (cons _2nd others) (inc j) (concat >> rst [_1st]))))))] >> (recur (inner-loop cc 0 []) (dec i))))) >> col (count col))) >> >> But this tail-recursive version is very very slow, much slower than the >> former one. And it also stack-overflows when the input is fairly large... I >> don't understand why. >> >> I also printed out a stack trace when it's running slowly, using 'jstack' >> command, and the strange stack trace is here: >> >> "nREPL-worker-0" daemon prio=10 tid=0x0000000001dc1000 nid=0x7b1b >> runnable [0x00007f77de15a000] >> java.lang.Thread.State: RUNNABLE >> at clojure.lang.RT.seqFrom(RT.java:482) >> at clojure.lang.RT.seq(RT.java:477) >> at clojure.core$seq.invoke(core.clj:133) >> at clojure.core$concat$fn__3941.invoke(core.clj:678) >> at clojure.lang.LazySeq.sval(LazySeq.java:42) >> - eliminated <0x00000000f5deac28> (a clojure.lang.LazySeq) >> at clojure.lang.LazySeq.seq(LazySeq.java:60) >> - locked <0x00000000f5deac28> (a clojure.lang.LazySeq) >> at clojure.lang.RT.seq(RT.java:475) >> at clojure.core$seq.invoke(core.clj:133) >> at clojure.core$concat$fn__3941.invoke(core.clj:678) >> at clojure.lang.LazySeq.sval(LazySeq.java:42) >> - eliminated <0x00000000f5deac80> (a clojure.lang.LazySeq) >> at clojure.lang.LazySeq.seq(LazySeq.java:60) >> - locked <0x00000000f5deac80> (a clojure.lang.LazySeq) >> at clojure.lang.RT.seq(RT.java:475) >> at clojure.core$seq.invoke(core.clj:133) >> at clojure.core$concat$fn__3941.invoke(core.clj:678) >> at clojure.lang.LazySeq.sval(LazySeq.java:42) >> - eliminated <0x00000000f5deacd8> (a clojure.lang.LazySeq) >> at clojure.lang.LazySeq.seq(LazySeq.java:60) >> - locked <0x00000000f5deacd8> (a clojure.lang.LazySeq) >> at clojure.lang.RT.seq(RT.java:475) >> at clojure.core$seq.invoke(core.clj:133) >> at clojure.core$concat$fn__3941.invoke(core.clj:678) >> ...... >> ...... >> ...... >> many many more stack frames ignored.... >> ...... >> ...... >> ...... >> at clojure.core$concat$fn__3941.invoke(core.clj:678) >> at clojure.lang.LazySeq.sval(LazySeq.java:42) >> - eliminated <0x00000000f5def0e8> (a clojure.lang.LazySeq) >> at clojure.lang.LazySeq.seq(LazySeq.java:60) >> - locked <0x00000000f5def0e8> (a clojure.lang.LazySeq) >> at clojure.lang.RT.seq(RT.java:475) >> at clojure.core$seq.invoke(core.clj:133) >> at clojure.core$concat$fn__3941.invoke(core.clj:678) >> at clojure.lang.LazySeq.sval(LazySeq.java:42) >> - eliminated <0x00000000f5def140> (a clojure.lang.LazySeq) >> at clojure.lang.LazySeq.seq(LazySeq.java:60) >> - locked <0x00000000f5def140> (a clojure.lang.LazySeq) >> at clojure.lang.RT.seq(RT.java:475) >> at clojure.core$seq.invoke(core.clj:133) >> at clojure.core$concat$fn__3941.invoke(core.clj:678) >> at clojure.lang.LazySeq.sval(LazySeq.java:42) >> - eliminated <0x00000000f5def198> (a clojure.lang.LazySeq) >> at clojure.lang.LazySeq.seq(LazySeq.java:60) >> - locked <0x00000000f5def198> (a clojure.lang.LazySeq) >> at clojure.lang.RT.seq(RT.java:475) >> at clojure.core$seq.invoke(core.clj:133) >> at clojure.core$concat$fn__3941.invoke(core.clj:678) >> at clojure.lang.LazySeq.sval(LazySeq.java:42) >> - eliminated <0x00000000f5def1f0> (a clojure.lang.LazySeq) >> at clojure.lang.LazySeq.seq(LazySeq.java:60) >> - locked <0x00000000f5def1f0> (a clojure.lang.LazySeq) >> at clojure.lang.RT.seq(RT.java:475) >> at clojure.core$seq.invoke(core.clj:133) >> at clojure.core$concat$fn__3941.invoke(core.clj:678) >> >> It seems that the tail-recursive version also resulted in a very deep >> recursion. >> I think my program is nothing wrong in the algorithm itself. But why >> would this happen? Any ideas? >> >> Thanks! >> >> -- >> Regards. >> Yue . Wen >> >> -- >> -- >> 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 >> --- >> You received this message because you are subscribed to the Google Groups >> "Clojure" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> For more options, visit https://groups.google.com/groups/opt_out. >> >> >> > > > > -- > Ben Wolfson > "Human kind has used its intelligence to vary the flavour of drinks, which > may be sweet, aromatic, fermented or spirit-based. ... Family and social > life also offer numerous other occasions to consume drinks for pleasure." > [Larousse, "Drink" entry] > > -- > -- > 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 > --- > You received this message because you are subscribed to the Google Groups > "Clojure" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- -- 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 --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
