ノイマンの自然数の生成の話

もう一発小ネタです。

#数学の問題 #プログラミング
ノイマンの方法で非負整数を作る。
0 = {}
1 = {{}}
2 = {{},{{}}}
3 = {{},{{}},{{},{{}}}}
…
あなたの好きなプログラミング言語で作ってみよう！

— 結城浩 (@hyuki) May 17, 2016

これがなかなか手こずりました。
いや、アルゴリズムが、って意味じゃなくって計算速度がなかなか上がらんキッツい問題だな、と言う意味です。

さて、これは定義上は、見かけはビックリするんですが、実は実装的にはPythonのrange関数(あるいはSchemeのSRFI-1のiota)の再実装みたいなモンです。
つまり、入力nに対して何を返すのか、と言うと実は

1を入力 -> [0]を返す
2を入力 -> [0, 1]を返す
3を入力 -> [0, 1, 2]を返す

ってのと全く同じ事をしてるんですね。ただ、最初に0を[]と定義してるだけ、なんで仕組みは簡単なんです。
仮に、Schemeでこういう、ちょっとダウングレードなカンジのrangeなりiotaを実装するのは鼻クソでしょう。

	#lang racket
	(define (neumann n)
	(let loop ((n n) (acc '()))
	(if (zero? n)
	acc
	(let ((m (- n 1)))
	(loop m (cons m acc))))))

view raw neumann-1.rkt hosted with ❤ by GitHub

ところが、です。
これが0を空リスト、と定義したらちと厄介な事になる。

	#lang racket
	(define (neumann n)
	(let loop ((n n) (zero '()))
	(if (zero? n)
	zero
	(let ((m (- n 1)))
	(loop m (cons zero zero))))))

view raw neumann-2.rkt hosted with ❤ by GitHub

末尾再帰で書いてるんですが、問題に書かれてるn = 0〜3付近の数ならイイんですが、一方、nが10、20、30と増えていくと、計算がどんどん時間かかっていって、100辺りになると終わらないんですね〜。
ロジック的にはどっちも同じなのに計算時間が物凄くかかる、ってのは、後者は空リストのconsを生成してるだけなんだけど、それで膨大な、恐らくヒープを消費してニッチもサッチもいかなくなってくる、って事です。要するに巨大なガベージを生成してるに他なりません。

実は最初は、遅延評価で書けばどうなんだ、とか思って書いてたんですが、これもnが増大するととんでもない事になっていきます。

	#lang racket
	(require srfi/41)
	(define neumann
	(stream-cons '() (stream-map cons neumann neumann)))

view raw neumann-3.rkt hosted with ❤ by GitHub

多分「定義のクールさ」って意味ではこの遅延評価版が一番カッコイイでしょう。見た目も綺麗ですし。マトモに定義通りに返してくれますし。

	> (stream-ref neumann 0)
	'()
	> (stream-ref neumann 1)
	'(())
	> (stream-ref neumann 2)
	'((()) ())
	> (stream-ref neumann 3)
	'(((()) ()) (()) ())
	>

view raw neumann-3-run.rkt hosted with ❤ by GitHub

ところがさすがの遅延評価版でもnが100とかなると計算が終わりません。やはりどっかで大量のconsを扱うのが大変になるんですね〜。

さて、だったらメモ化はどうだ、って話になるんですが。
通常の高階関数のメモ化を利用して・・・ってのはこの場合は上手くないんです。
基本的に、n = 100を計算する時、n = 100の答えがあったらそいつをハッシュから持ってくる、ってのがメモ化の極意なんですが、生憎、フツーに実装したら今回のような「n = 100の状態を計算する為にはn = 99が必要」のケースだと上手く計算を省略してくれないんですよね。
理想的には再帰的にnを探ってくウチに得た値を利用して計算を行う、と言うちょっとした手動的な最適化が施されてないと、結局毎回新たな値を与える度にn=0まで到達してしまう。
今回のノイマンのモデルだと、どっちにせよnは順番に並んでますし、例えばn = 10を何の情報も無い状態で計算した際にn = 0〜10までのハッシュを全部記録して、n=11の計算の際にn=10「だけ」利用すれば11がすぐ得られる、と言う最適化を施しておいた方が良いわけです。
また、n=11まで計算した後で、n=15を計算するとn=12〜14までの情報は無いわけですが、ハッシュを手繰っていって、n=11の値が見つかった際にそこから計算をスタートしてn=12〜14までをハッシュに埋めつつn=15を返す、ってカタチにしておけば、0まで戻る無駄は省けるわけです。

	#lang racket
	(require srfi/69)
	(define neumann
	(let ((table (make-hash-table eqv?)))
	(hash-table-set! table 0 '())
	(lambda (n)
	(define (get key)
	(let ((val (hash-table-ref/default table key #f)))
	(if val
	key
	(get (- key 1)))))
	(define (put key)
	(if (= key n)
	(hash-table-ref table n)
	(let ((val (hash-table-ref table key)))
	(let ((key (+ key 1)))
	(hash-table-set! table key (cons val val))
	(put key)))))
	(put (get n)))))

view raw neumann-4.rkt hosted with ❤ by GitHub

今回はSRFI-69のハッシュテーブルを利用しています。
ローカル関数のgetはnが与えられた時、nに対応するvalueがハッシュ内にあるかどうか検索します。nが見つからなかった時にはn-1を検索、それでも見つからない場合は・・・と小さいキーを順次検索していって、valueが見つかった時、そのキーを返します。
ローカル関数putは逆に、あるキーからnに向けて計算した数値を逐次ハッシュに記録していって、キーがnと同じになった時にvalueを返して脱出します。
この2つのローカル関数で、ノイマンの定義を最適化するように試みてるんですが・・・・・・。
それでもやっぱn=100とかだと計算時間かかりすぎて、っつーかやっぱどうもヒープ食いつぶして上手い具合にいかないですねぇ。
ハッキリ言って、この問題は、「計算スピードの省略」じゃどうにもならなくって、どっちかっつーとメモリ容量との戦いの模様です。
なかなかconsは手強いですよ。