The output with the sample data prints out as:
Code: Select all
linear | lg-n | ln-n | log-n | n-lg-n | n-ln-n | n-log-n | n-sq |two-expt-n
-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+
1 | 10000 | 10000 | 10000 | 1000 | 500 | 500 | 100 | 100
8 | 30000 | 20795 | 10000 | 24000 | 8318 | 3613 | 6400 | 12800
10 | 33220 | 23026 | 10000 | 33220 | 11513 | 5000 | 10000 | 51200
16 | 40000 | 27726 | 12042 | 64000 | 22181 | 9633 | 25600 | 3276800
127 | 69887 | 48442 | 21039 | 887563 | 307606 | 133592 | 1612900 | 8.507E+39
128 | 70000 | 48521 | 21073 | 896000 | 310530 | 134862 | 1638400 | 1.701E+40
1000 | 99658 | 69078 | 30000 | 9965785 | 3453878 | 1500000 | 100000000 |5.358E+302
It is pretty terrible code, actually. I am only posting this here because... I dunno, ego satisfaction I guess. A waste of time, but it was my time to waste.
Code: Select all
(define (but-last lst) (reverse (cdr (reverse lst))))
(define (body lst) (cdr (but-last lst)))
(define order-of-n
(lambda (fn marginal)
(lambda (n)
(inexact->exact (ceiling (* marginal (fn n)))))))
(define identity (lambda (n) n))
;; most Scheme implementations only include a natural log function
(define logB
(lambda (B)
(lambda (x)
(if (= 0 x)
0
(/ (log x) (log B))))))
(define log2 (logB 2))
(define log10 (logB 10))
(define n-1000 (order-of-n identity 1000))
(define nlgn-500 (order-of-n (lambda (n) (* n (log2 n))) 500))
(define nlogn-500 (order-of-n (lambda (n) (* n (log10 n))) 500))
(define lgn-10k (order-of-n log2 10000))
(define logn-10k (order-of-n log10 10000))
(define tabulate-predicted-performance
(lambda (order-list sizes-list)
(let ((test-functions
(map (lambda (entry)
(cons (car entry) (order-of-n (cdr entry) (cdar entry))))
order-list)))
(cons (map caar test-functions)
(map (lambda (size)
(cons size
(map (lambda (entry)
(max (cdar entry)
((cdr entry) size)))
(cdr test-functions))))
sizes-list)))))
(define test-set-a (list
(cons (cons 'linear 1000) identity)
(cons (cons 'lg-n 10000) log2)
(cons (cons 'ln-n 10000) log)
(cons (cons 'log-n 10000) log10)
(cons (cons 'n-lg-n 1000) (lambda (n) (* n (log2 n))))
(cons (cons 'n-ln-n 500) (lambda (n) (* n (log n))))
(cons (cons 'n-log-n 500) (lambda (n) (* n (log10 n))))
(cons (cons 'n-sq 100) (lambda (n) (* n n)))
(cons (cons 'two-expt-n 50) (lambda (n) (expt 2 n)))))
(define size-samples '(1 8 10 16 127 128 1000))
(define symbol-length
(lambda (sym)
(string-length (symbol->string sym))))
(define decimal-integer-length
(lambda (n)
(inexact->exact (ceiling (abs (log10 n))))))
(define resize-notation
(lambda (x max-width)
(if (< max-width (decimal-integer-length x))
(format #f "~v,3e" max-width x)
(format #f "~vd" max-width x))))
(define symbol->centered-text
(lambda (sym column-size)
(let* ((len (symbol-length sym))
(offset (if (even? len) 0 1))
(midpoint (ceiling (/ column-size 2)))
(left-pad (- midpoint (ceiling (/ len 2))))
(right-pad (+ offset (- midpoint (ceiling (/ len 2))))))
(format #f "~v@t~s~v@t" left-pad sym right-pad))))
(define fill-list
(lambda (element k)
(if (>= 0 k)
'()
(cons element (fill-list element (- k 1))))))
(use-modules (ice-9 format))
(define display-tabulated-performance
(lambda (ratings sizes column-width)
(let* ((table (tabulate-predicted-performance ratings sizes))
(column-count (length (car table)))
(sub-divider (format #f "~v,0,'-t+" (+ 1 column-width)))
(divider (format #f "~v{~a~}~%"
column-count
(fill-list sub-divider column-count)))
(headings (map (lambda (heading)
(symbol->centered-text heading column-width))
(car table)))
(data (map (lambda (row)
(format #f "~{~a~^ |~}~%"
(map (lambda (datum)
(resize-notation datum column-width))
row)))
(cdr table))))
(format #t "~{~a~^ |~}~%" headings)
(display divider)
(format #t "~{~a~}" data))))
(display-tabulated-performance test-set-a size-samples 10)