fork download
copy 
  1. ;; Memoization. (1.01)
  2. ;; @note Using dynamically bound variable (Parameters).
  3.  
  4. (use-modules (srfi srfi-19)
  5.              (ice-9 format))
  6.  
  7. ;; Time.
  8.  
  9. (define (process-time)
  10.   (let ((now (current-time time-process)))
  11.     (+ (time-second now) (/ (time-nanosecond now) 1E9))))
  12.  
  13. (define (timeit thunk)
  14.   (let ((t (process-time)))
  15.     (thunk)
  16.     (format #t "Elapsed: ~,6Fs~%" (- (process-time) t))))
  17.  
  18. ;; Memo
  19.  
  20. (define (memo-list f)
  21.   (let ((m '()))
  22.     (lambda (k)
  23.       (unless (assoc-ref m k)
  24.               (set! m (acons k (f k) m)))
  25.       (assoc-ref m k))))
  26.  
  27. (define (memo-hash f)
  28.   (let ((m (make-hash-table)))
  29.     (lambda (k)
  30.       (unless (hash-ref m k)
  31.               (hash-set! m k (f k)))
  32.       (hash-ref m k))))
  33.  
  34. ;; Show.
  35.  
  36. (define fib
  37.   (make-parameter
  38.    (lambda (n)
  39.     (cond
  40.      ((= n 0) 0)
  41.      ((= n 1) 1)
  42.      (else
  43.       (+ ((fib) (- n 2)) ((fib) (- n 1))))))))
  44.  
  45. (define (make-f f)
  46.   (lambda ()
  47.     (parameterize ((fib f))
  48.       (format #t "~A~%" ((fib) 30)))))
  49.  
  50. (timeit (make-f (memo-list (fib))))
  51. (timeit (make-f (memo-hash (fib))))
  52. (timeit (make-f (fib)))
Success #stdin #stdout 1.41s 13344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
832040
Elapsed: 0.000000s
832040
Elapsed: 0.000000s
832040
Elapsed: 1.383667s
https://ideone.com/M3fJhk
language:
Scheme (guile 2.2.4)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!