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.
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
