What type of improvement are you expecting to see? 1. A linear improvement based on throwing more cores at the problem? In this case you would need to use pmap to compute items in parallel. Your implementation appears to be single threaded. 2. An algorithmic improvement, like going from a DFT to an FFT? In this case, is there any theoretical reason the algorithm does less work? Are you making a time/memory trade off?
This would make it easier to provide suggestions. Sean On Mar 19, 12:53 pm, Andrzej <ndrwr...@googlemail.com> wrote: > 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.
