OSDev.org
https://forum.osdev.org/

Revisiting a school homework assignment.
https://forum.osdev.org/viewtopic.php?f=13&t=32590
Page 2 of 2

Author:  Schol-R-LEA [ Sun Jan 07, 2018 10:33 pm ]
Post subject:  Re: Revisiting a school homework assignment.

After a disturbingly long time, I finally got a set of tabulating functions together that collate and display the results of my order-of-n functions in a semi-acceptable manner. I don't know why I spent so long on this, TBH, I guess it just felt unfinished. The version in question works for Guile, but I haven't tried it on other Scheme implementations due to the mess that is Scheme libraries.

The output with the sample data prints out as:
Code:
  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:
(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)

Page 2 of 2 All times are UTC - 6 hours
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/