I've been toying with various implementations of reduce-like
functions, trying to do something "smarter" than a simple iteration
over a collection of data. This hasn't worked out very well, my
implementation is a lot (~50x) slower than a simple loop. Could anyone
point out any bottlenecks in this algorithm and advise me on possible
ways of improving it?
;-- simple (sequential) implementation
(defn- sum_seq_int [val vec]
(if (empty? vec)
val
(recur (+ val (first vec)) (rest vec))))
(defn sum_seq [vec]
(sum_seq_int 0 vec))
;-- "divide&conquer" approach
(defn- split [vec]
(let [c (count vec)
c2 (/ c 2)]
(list (subvec vec 0 c2) (subvec vec c2 c))))
(defn- sum_tree_int [val vec1 vec2]
(cond (and (empty? vec1) (= (count vec2) 1)) (+ val (first vec2))
(and (empty? vec2) (= (count vec1) 1)) (+ val (first vec1))
:else
(let [s1 (split vec1)
s2 (split vec2)]
(recur (sum_tree_int val (first s1) (second s1)) (first s2) (second
s2)))))
(defn sum_tree [vec]
(let [s (split vec)]
(sum_tree_int 0 (first s) (second s))))
;-- some tests
(def l1 (range 1 10))
(def l2 (range 1 1000))
(def l3 (range 1 100000))
(time (sum_seq (vec l1)))
"Elapsed time: 0.040508 msecs"
45
(time (sum_seq (vec l2)))
"Elapsed time: 0.297523 msecs"
499500
(time (sum_seq (vec l3)))
"Elapsed time: 29.381109 msecs"
4999950000
(time (sum_tree (vec l1)))
"Elapsed time: 0.181308 msecs"
45
(time (sum_tree (vec l2)))
"Elapsed time: 13.529094 msecs"
499500
(time (sum_tree (vec l3)))
"Elapsed time: 1387.68363 msecs"
4999950000
What is the most likely cause of the slowdown?
1. split function,
2. non-tail-recursive function call,
3. general overhead.
As for (1), how to split the collection so that no data copying is
required and resulting subvectors are more or less balanced? Or, how
to query the underlying data structure whether, or where, such a
"convenient" position exists?
Andrzej
--
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
To unsubscribe from this group, send email to
clojure+unsubscribegooglegroups.com or reply to this email with the words
"REMOVE ME" as the subject.
