Ah, disregard that. I found the rules: http://shootout.alioth.debian.org/u32q/benchmark.php?test=binarytrees&lang=all#about
On Fri, Dec 5, 2008 at 1:04 AM, Christian Vest Hansen <[EMAIL PROTECTED]> wrote: > Is it important that we build and deconstruct a complete tree in the > process, or is merely getting the correct end result enough? > > > (defn checkTree [item depth] > (if (zero? depth) > item > (- (+ item (checkTree (- (* 2 item) 1) (dec depth))) > (checkTree (* 2 item) (dec depth))))) > > (defn sumTrees [iterations depth] > (loop [sum (int 0) i (int 1)] > (if (<= i iterations) > (recur (int (+ sum (checkTree i depth) (checkTree (- i) depth))) > (inc i)) > sum))) > > ;;; followed by all of your code, and then: > > (time (println "My result:" (sumTrees 10000 10))) > (time (println "Your result:" (sum-trees 10000 10))) > > Produces this output: > > rowe:~$ clj trees.clj > My result: -20000 > "Elapsed time: 11179.616 msecs" > Your result: -20000 > "Elapsed time: 112541.067 msecs" > rowe:~$ > > > > > On Thu, Dec 4, 2008 at 8:55 PM, PeterB <[EMAIL PROTECTED]> wrote: >> >> Hi, >> >> I downloaded clojure_20080916.zip and had a go with a simple tree >> benchmark (cut-down version of the one in the computer language >> shootout http://shootout.alioth.debian.org/). >> >> The Java version is pretty simple and runs in about 2s on my laptop: >> >> public class Main >> { >> public static void main(String[] args) >> { >> System.out.println("result: " + sumTrees(10000, 10)); >> } >> >> public static int sumTrees(int iterations, int depth) >> { >> int i; >> int sum = 0; >> >> for (i = 1; i <= iterations; i++) >> sum += TreeNode.bottomUpTree(i, depth).itemCheck() + >> TreeNode.bottomUpTree(-i, depth).itemCheck(); >> return sum; >> } >> >> public static class TreeNode >> { >> private TreeNode left, right; >> private int item; >> >> TreeNode(int item) >> { >> this.item = item; >> } >> >> TreeNode(int item, TreeNode left, TreeNode right) >> { >> this.left = left; >> this.right = right; >> this.item = item; >> } >> >> private static TreeNode bottomUpTree(int item, int depth) >> { >> if (depth > 0) >> return new TreeNode(item, >> bottomUpTree(2*item-1, >> depth-1), >> bottomUpTree(2*item, >> depth-1)); >> else >> return new TreeNode(item); >> } >> >> int itemCheck() >> { >> if (left == null) >> return item; >> else >> return item + left.itemCheck() - right.itemCheck(); >> } >> } >> } >> >> >> The Clojure version is considerably more compact and elegant: >> >> (defn make-tree [item depth] >> (if (zero? depth) >> (list item nil nil) >> (let [item2 (* 2 item) depth-1 (dec depth)] >> (list item (make-tree (dec item2) depth-1) (make-tree item2 >> depth-1))))) >> >> (defn check-tree [tree] >> (if (nil? tree) >> 0 >> (let [[i l r] tree] (- (+ i (check-tree l)) (check-tree r))))) >> >> (defn sum-trees [iterations depth] >> (let [sum #(+ (check-tree (make-tree % depth)) >> (check-tree (make-tree (- %) depth)))] >> (reduce #(+ %1 %2) 0 (map sum (range 1 (inc iterations)))))) >> >> (time (println "result:" (sum-trees 10000 10))) >> >> However, there is a heavy price to be paid for this elegance: >> 'Elapsed time: 100730.161515 msecs' >> >> Ouch! That's rather disappointing :-( >> Any suggestions for improving the performance? >> >> >> >> > > > > -- > Venlig hilsen / Kind regards, > Christian Vest Hansen. > -- Venlig hilsen / Kind regards, Christian Vest Hansen. --~--~---------~--~----~------------~-------~--~----~ 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 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 -~----------~----~----~----~------~----~------~--~---