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(1, 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 1 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
-~--~~~~--~~--~--~---

Re: Elegant but very slow

[PeterB]

Thanks for all the suggestions!

This modified version is very close to that in the thread:
http://groups.google.com/group/clojure/browse_thread/thread/f0303a9e00b38529/99f02fef21721a2f?lnk=gst&q=alioth+tree#99f02fef21721a2f
(Thanks for pointing that out Meikel. I should have searched old
threads before posting.)

(defn make-tree [item depth]
  (if (zero? depth)
[item nil nil]
(let [item2 (* 2 item)  depth-1 (dec depth)]
  [item (make-tree (dec item2) depth-1) (make-tree item2
depth-1)])))

; Note: (+ (tree 0) (check-tree (tree 1)) (- (check-tree (tree 2
seems to require
; the creation of an intermediate list and runs twice as slow
(defn check-tree [tree]
  (if tree
  (- (+ (tree 0) (check-tree (tree 1))) (check-tree (tree 2)))
  0))

(defn sum-trees [iterations depth]
  (let [sum #(+ (check-tree (make-tree % depth))
  (check-tree (make-tree (- %) depth)))]
(reduce + (map sum (range 1 (inc iterations))

(time (println "result:" (sum-trees 1 10)))


Running in Clojure REPL for java 1.6.0_11 with -server option:

result: -2
Elapsed time: 6080.294283 msecs

Wow! Elegant and fast!





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