vallog: On Lisp memoize

vallog: On Lisp memoize

あああ、僕もうっかりしてました。

On Lispのmemoizeなんですけど。久々にGauche起動してValvallowさんに従って試してみたら、次のような結果になりました。

	gosh> (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)))))))
	memoize
	gosh> (define (fib n)
	(if (< n 2)
	1
	(+ (fib (- n 1))(fib (- n 2)))))
	fib
	gosh> (time (fib 35))
	;(time (fib 35))
	; real 2.451
	; user 2.450
	; sys 0.000
	14930352
	gosh> (time ((memoize fib) 35))
	;(time ((memoize fib) 35))
	; real 2.580
	; user 2.570
	; sys 0.000
	#<undef>
	gosh> (time ((memoize fib) 35))
	;(time ((memoize fib) 35))
	; real 2.438
	; user 2.430
	; sys 0.000
	#<undef>
	gosh>

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

あれ、全然速くなっていない……。

考えてみれば当然で、手続きmemoizeは呼び出す度に新しくレキシカル環境を作ります。
と言う事は。cacheに保存される筈のハッシュテーブルは、手続きmemoizeが呼び出される度に新しくクロージャの中で作られて、そしてmemoizeの起動が終了する度にその寿命を全うするわけです。
従って、hash-table-getの返り値は毎度必ず#fになる、って事です。

これじゃあ意味無い。

んで、On Lispを良く見てみると、実は「敢えて」memoizeとそれが受け取る関数引数を合わせて大域環境に束縛しているんです。
これが手続きmemoizeの正しい使い方です。本に依ると、大域変数slowidに束縛されている以上、クロージャ、翻って使用されたハッシュテーブルが廃棄されません。

	gosh> (define slowid (memoize fib))
	slowid
	gosh> (time (slowid 35))
	;(time (slowid 35))
	; real 2.549
	; user 2.510
	; sys 0.000
	#<undef>
	gosh> (time (slowid 35))
	;(time (slowid 35))
	; real 0.000
	; user 0.000
	; sys 0.000
	14930352
	gosh>

view raw right-way-of-using-memoize.scm hosted with ❤ by GitHub

ご覧になれば分かるでしょうが、一回目の大域変数slowidに35を付けた時の呼び出しは遅いです。反面、クロージャ/ハッシュテーブルは依然と大域変数slowidに束縛されたまま、なんで、二回目の呼び出し時は高速なハッシュ検索により、時間が殆どかからず値を見つけ出している事が分かると思います。

これがmemoizeの使い方です。