vallog: On Lisp memoize

2010/05/13

	;; On Lisp - P.67
	(define (memoize fn)
	(let ((cache (make-hash-table 'equal?)))
	(lambda args
	(let ((val (hash-table-get cache args #f)))
	(if val val
	(hash-table-put! cache args (apply fn args)))))))

	(define (fib n)
	(if (< n 2)
	1
	(+ (fib (- n 1))(fib (- n 2)))))

	(time (fib 35))
	;(time (fib 35))
	; real 8.266
	; user 7.922
	; sys 0.000
	14930352

	(time ((memoize fib) 30))
	;(time ((memoize fib) 30))
	; real 0.828
	; user 0.781
	; sys 0.000
	14930352

view raw ycombinator5.scm hosted with ❤ by GitHub

追記

メモ化されてNEEEEEEEEEEE！ということで。

	(define (memoize fn)
	(let ((cache (make-hash-table 'equal?)))
	(lambda args
	(let ((val (hash-table-get cache args #f)))
	(if val val
	(let ((val (apply fn args)))
	(hash-table-put! cache args val)
	val))))))

	(define (fib n)
	(if (< n 2)
	1
	(+ (fib (- n 1))(fib (- n 2)))))

	(define mfib (memoize fib))

	(time (mfib 35))

	;(time (mfib 35))
	; real 7.953
	; user 7.875
	; sys 0.000
	14930352
	;(time (mfib 35))
	; real 0.000
	; user 0.000
	; sys 0.000
	14930352

view raw memoize-2.scm hosted with ❤ by GitHub

でも、これでもメモられたのは35だけか・・・。うーん。