The Q6600
Benchmarks Game

binary-trees Racket #2 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
;;; improved by Phil Nguyen:
;;; - use `cons` instead of struct `node`
;;; - removed the confirmed unneccessary field `val`
;;; - clean up with `define` instead of nested `let`
;;; - clean up with `for/sum` instead of generic `for/fold`
;;; *reset*

(require racket/cmdline)

#;(struct node (left right))
(define node cons)
(define node-left car)
(define node-right cdr)

(define (make d)
  (if (= d 0)
      (node #f #f)
      (let ([d2 (sub1 d)])
        (node (make d2) (make d2)))))

(define (check t)
  (if (node-left t)
      (+ 1 (check (node-left t)) (check (node-right t)))
      1))

(define (main n)
  (define min-depth 4)
  (define max-depth (max (+ min-depth 2) n))
  (define stretch-depth (+ max-depth 1))
  (printf "stretch tree of depth ~a\t check: ~a\n" stretch-depth (check (make stretch-depth)))
  (define long-lived-tree (make max-depth))
  (for ([d (in-range 4 (add1 max-depth) 2)])
    (define iterations (arithmetic-shift 1 (+ (- max-depth d) min-depth)))
    (printf "~a\t trees of depth ~a\t check: ~a\n"
            iterations
            d
            (for/sum ([_ (in-range iterations)])
              (check (make 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.


Wed, 06 May 2020 16:31:05 GMT

MAKE:
/opt/src/racket-7.7/bin/raco make binarytrees.racket-2.racket

3.47s to complete and log all make actions

COMMAND LINE:
/opt/src/racket-7.7/bin/racket binarytrees.racket-2.racket 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