binary-trees Racket CS program
source code
#lang racket/base
;;; The Computer Language Benchmarks Game
;;; https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
;;; Derived from the Chicken variant by Sven Hartrumpf
;;; contributed by Matthew Flatt
;;; *reset*
(require racket/cmdline)
(struct node (left val right))
;; Instead of (define-struct leaf (val)):
(define (leaf val) (node #f val #f))
(define (leaf? l) (not (node-left l)))
(define (leaf-val l) (node-val l))
(define (make item d)
(if (= d 0)
(leaf item)
(let ((item2 (* item 2))
(d2 (- d 1)))
(node (make (- item2 1) d2)
item
(make item2 d2)))))
(define (check t)
(if (leaf? t)
1
(+ 1 (+ (check (node-left t))
(check (node-right t))))))
(define (main n)
(let* ((min-depth 4)
(max-depth (max (+ min-depth 2) n)))
(let ((stretch-depth (+ max-depth 1)))
(printf "stretch tree of depth ~a\t check: ~a\n"
stretch-depth
(check (make 0 stretch-depth))))
(let ((long-lived-tree (make 0 max-depth)))
(for ((d (in-range 4 (add1 max-depth) 2)))
(let ((iterations (arithmetic-shift 1 (+ (- max-depth d) min-depth))))
(printf "~a\t trees of depth ~a\t check: ~a\n"
iterations
d
(for/fold ([c 0])
([i (in-range iterations)])
(+ c
(check (make i d)) )))))
(printf "long lived tree of depth ~a\t check: ~a\n"
max-depth
(check long-lived-tree)))))
(command-line #:args (n)
(main (string->number n)))
notes, command-line, and program output
NOTES:
64-bit Ubuntu quad core
Welcome to Racket v7.7.0.4 [cs].
Thu, 07 May 2020 16:15:42 GMT
MAKE:
make: *** No rule to make target 'binarytrees.racketcs_run'. Stop.
0.07s to complete and log all make actions
COMMAND LINE:
/opt/src/racket-7.7.0.4-cs/bin/racket binarytrees.racketcs 21
PROGRAM OUTPUT:
stretch tree of depth 22 check: 8388607
2097152 trees of depth 4 check: 65011712
524288 trees of depth 6 check: 66584576
131072 trees of depth 8 check: 66977792
32768 trees of depth 10 check: 67076096
8192 trees of depth 12 check: 67100672
2048 trees of depth 14 check: 67106816
512 trees of depth 16 check: 67108352
128 trees of depth 18 check: 67108736
32 trees of depth 20 check: 67108832
long lived tree of depth 21 check: 4194303