memoization 技术

目录

函数式编程有个好处就是对于 f(x)只要 x 相同那么返回的值必然相同,利用函数的这种特性我们可以使用 memoization 技术
原理非常简单就是每次调用 f 时存储 x 和对应的值,调用前检查是否已经存储了 x,如果有就返回,没有就计算

实例

; 没有使用 memoization 版本的求斐波那契数列
; 非常慢 cpu 100%
(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

(define true #t)
(define false #f)

(define (make-table)
   (let ((local-table (list '*table*)))

   ;(assoc 'x '(*table* (a 1) (b 2) (x 3) (c 4)))
   ;> '(x 3)
     (define (assoc key records)
       (cond ((null? records) false)
             ((equal? key (caar records)) (car records))
             (else (assoc key (cdr records)))))

   ;(lookup 'a)
   ;> 1
     (define (lookup key-list)
       (define (iter keys table)
         (cond ((null? keys) false)
               ((null? (cdr keys))
                (let ((record (assoc (car keys) (cdr table))))
                  (if record
                      (cdr record)
                      false)))
               (else  
                (let ((subtable (assoc (car keys) (cdr table))))
                  (if subtable
                      (iter (cdr keys) subtable)
                      false)))))
       (iter key-list local-table))

; 这里的 insert 虽然看起来是有副作用的,但是对于返回值不变的函数是无所谓的
     (define (insert! value key-list)
       (define (iter keys table)
         (cond ((null? table)   
                (if (null? (cdr keys))
                    (cons (car keys) value)
                    (list (car keys) (iter (cdr keys) '()))))
               ((null? (cdr keys)) 
                   (let ((record (assoc (car keys) (cdr table))))
                     (if record
                         (set-cdr! record value)
                         (set-cdr! table
                                   (cons (cons (car keys) value)
                                         (cdr table))))))
               (else            ;;有多个 key
                (let ((subtable (assoc (car keys) (cdr table))))
                  (if subtable
                      (iter (cdr keys) subtable)
                      (set-cdr! table
                                (cons (list (car keys)
                                            (iter (cdr keys) '())) 
                                      (cdr table))))))))
       (iter key-list local-table)
       'ok)
     (define (dispatch m)
       (cond ((eq? m 'lookup-proc) lookup)
             ((eq? m 'insert-proc!) insert!)
             (else (error "Unknown operation -- TABLE" m))))
     dispatch))

(define (lookup table . key-list) ((table 'lookup-proc) key-list))
(define (insert! table value . key-list) ((table 'insert-proc!) value key-list))

; f 是函数 x 是 f 的参数
(define (memoize f)
  (let ((table (make-table)))
    (lambda (x)
      (let ((previously-computed-result (lookup table x)))
        (or previously-computed-result
            (let ((result (f x)))
              (insert! table result x)
              result))))))

(define memo-fib
  (memoize (lambda (n)
             (cond ((= n 0) 0)
                   ((= n 1) 1)
                   (else (+ (memo-fib (- n 1))
                            (memo-fib (- n 2))))))))

目录