OSDev.org

The Place to Start for Operating System Developers
It is currently Fri Jan 19, 2018 7:51 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 16 posts ]  Go to page Previous  1, 2
Author Message
 Post subject: Re: Revisiting a school homework assignment.
PostPosted: Sun Jan 07, 2018 10:33 pm 
Offline
Member
Member
User avatar

Joined: Fri Oct 27, 2006 9:42 am
Posts: 1057
Location: Athens, GA, USA
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)

_________________
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
μή εἶναι βασιλικήν ἀτραπόν ἐπί γεωμετρίαν
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 16 posts ]  Go to page Previous  1, 2

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group