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.
