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/ |