As a learning exercise and also to continue to investigate Clojure performance I've roughly translated the Alioth binary-tree benchmark into Clojure. I chose the binary-tree simply because it's the first of the Alioth benchmarks in alphabetical collation; I may do others later.
I've based my implementation on Manuel Giraud's Common LISP implementation http://shootout.alioth.debian.org/gp4/benchmark.php?test=binarytrees&lang=sbcl&id=2 and followed his algorithm blindly. However Giraud uses the Common LISP ASH (arithmetic shift) function, and, if there's a built-in function in Clojure, I did not find it; consequently I implemented an arithmetic-shift function of my own. As I'm as yet unfamiliar with Clojure it's likely that my implementation is less than optimal. ;;; -*- mode: clojure -*- ;;; ;;; http://shootout.alioth.debian.org/ ;;; ;;; From: Simon Brooke ;;; Based on Common LISP by: Manuel Giraud ;;; Node is either NIL (for leaf nodes) or an improper list (DATA LEFT . RIGHT) (defn build-btree [item depth] (if (zero? depth) (cons item (cons nil nil)) (let [item2 (* 2 item) depth-1 (- depth 1)] (cons item (cons (build-btree (- item2 1) depth-1) (build-btree item2 depth-1)))))) (defn check-node [node] (if node (let [data (first node) kids (rest node)] (- (+ data (check-node (first kids))) (check-node (rest kids)))) 0)) ;;; The Common LISP implementation used the ASH (arithmetic shift) function. ;;; Whether this was optimisation or just showing off I'm not sure, ;;; but I'm going to blindly follow their implementation. This function ;;; could almost certainly be improved upon (defn arithmetic-shift [n i] (cond (zero? i) n (> i 0) (loop [result n expt 0] (cond (= expt i) result true (recur (* result 2) (+ expt 1)))) true (loop [result n expt 0] (cond (= expt i) result true (recur (/ result 2) (- expt 1)))))) (defn loop-depths [max-depth & others] (let [min-depth (or (first others) 4)] (loop [d min-depth] (let [iterations (arithmetic-shift 1 (+ max-depth min-depth (- d)))] (if (> d max-depth) nil ;; return value (do (println (* iterations 2) "\t trees of depth " d "\t check: " (loop [i 1 sum 0] (if (> i iterations) sum (recur (+ i 1) (+ sum (check-node (build-btree i d)) (check-node (build-btree (- i) d))))))) (recur (+ d 2)))))))) (defn main [n] ;;; ignore for now the issue of parsing a command-line variable (println "stretch trees of depth " (+ n 1) "\t check: " (check-node (build-btree 0 (+ n 1)))) (let [long-lived-tree (build-btree 0 n)] (loop-depths n) (println "long lived tree of depth " n "\t check: " (check-node long-lived-tree)))) ;;(main) I get the following values (normalised to seconds) for (time (main 16)): Armed Bear Interpreted 232.54 Compiled 35.3 CMUCL Interpreted 600.15 Compiled 6.13 Clojure 57.131432 These are not formal benchmark tests; each test is of one run, not averaged over several, and is performed on my development machine which has many other processes running. What's iinteresting (to me) --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
