Elegant but very slow

[PeterB]

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?

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