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.
