前回では、テクニカルには主にメモワイズ、あるいはメモ化、と言う数値の再計算を避ける手法を導入してた。
要するに、コラッツ数列を計算する際に、その「経路」をガンガンと記録していく手法だ。
前回作ったcollatz-seqs関数は、適当な数を与えると1に到達する前の全経路をハッシュテーブルへと登録する能力を持っていた。
例えばcollatz-seqs関数に11を与えると、1に到達する前の全数値に付いて、それらが形成する経路を全部ハッシュテーブルに登録する。
ところで、ハッシュテーブルに登録されたリストを「保有する」コストってのは如何ほどなんだろうか。例えば4が形成する経路、(4, 2, 1)、なんつーのは上の写真を見てみると頻出してる。
そうすると、ハッシュテーブルのデータとしては、単に望んだ数値へとリンクを貼る、だけでもいいんじゃないか、と言う疑いが出てくる。
例えば結果が次のようになってもいいんじゃないか、と言う話だ。
'#hasheqv((1 . (1))
(2 . (cons 2 (hash-ref table 1)))
(4 . (cons 4 (hash-ref table 2)))
(5 . (cons 5 (hash-ref table 16)))
(8 . (cons 8 (hash-ref table 4)))
(10 . (cons 10 (hash-ref table 5)))
(11 . (cons 11 (hash-table table 16))
(13 . (cons 13 (hash-table table 40)))
(16 . (cons 16 (hash-table table 8)))
(17 . (cons 17 (hash-table table 52)))
(20 . (cons 20 (hash-table table 10)))
(26 . (cons 26 (hash-table table 13)))
(34 . (cons 34 (hash-table table 17)))
(40 . (cons 40 (hash-table table 20)))
(52 . (cons 52 (hash-table table 26))))
こうすることで、具現化した値を持つことなく、リンクを参照するだけ、で問題が解決するのではないか。データ自体を再帰構造させるんだ。そして'(1)がベースケースで、ここで参照が終了する事となる。
いや、実の事を言うと関数collatz-seqは、事実上こういう再帰構造を想定した計算をしている。ただし、「計算する」以上、リンクをリンクのまま保持せずに実値を計算しちゃって登録してるわけだ。
もし、「計算をせずに」リンクのままで登録したい、ってぇのなら、次のような結果を返す(データテーブルを作る)事を想定しないといけない。
'#hasheqv((1 . (1))
(2 . (cons 2 (lambda () (hash-ref table 1))))
(4 . (cons 4 (lambda () (hash-ref table 2))))
(5 . (cons 5 (lambda () (hash-ref table 16))))
(8 . (cons 8 (lambda () (hash-ref table 4))))
(10 . (cons 10 (lambda () (hash-ref table 5))))
(11 . (cons 11 (lambda () (hash-table table 16))))
(13 . (cons 13 (lambda () (hash-table table 40))))
(16 . (cons 16 (lambda () (hash-table table 8))))
(17 . (cons 17 (lambda () (hash-table table 52))))
(20 . (cons 20 (lambda () (hash-table table 10))))
(26 . (cons 26 (lambda () (hash-table table 13))))
(34 . (cons 34 (lambda () (hash-table table 17))))
(40 . (cons 40 (lambda () (hash-table table 20))))
(52 . (cons 52 (lambda () (hash-table table 26)))))
こうすれば、「実行」するまで「リンクを辿る」行為は遮られる。無引数ラムダ式、いわゆるthunkを使って計算を閉じ込める、と。
これで計算効率が良くなるかどうなるかは分からんのだが、いずれにせよ、「これを計算する」場合、Scheme/Racketにはもっと単純に上記のような構造を記述出来る方策が存在する。そう、遅延評価だ。
実は遅延評価機構、あるいはSRFI-41を使えば簡単に、どんな整数をも先頭としたコラッツ数列のストリーム(※1)を入手する事が出来る。
それはこのように書く。
(define *collatz-seqs*
(stream-cons (stream 1)
(stream-map (lambda (n)
(stream-cons n
(stream-ref *collatz-seqs*
(if (even? n)
(sub1 (/ n 2))
(* 3 n)))))
(stream-from 2))))
これは前回見せたような関数ではなくって永続したデータだ。
意味は大体次のような事だ。
- 2から始まる無限長の整数列を入手する。
- 1. にラムダ式をstream-mapする。
- stream-mapするラムダ式の内訳は、1. から引っ張ってきた数値(n)が偶数の場合、「完成したコラッツ数列のストリーム」の n / 2 - 1 番目の情報にstream-consする。奇数だったら「完成したコラッツ数列のストリーム」の3 × n 番目の情報に stream-cons する。
- 3. までで生成したストリームに '(1) を stream-cons して完成したコラッツ数列のストリームとする。
注意点が二点ある。
まず一点目。n が偶数の時、あるいは奇数の時、の場合の計算条件が違うんじゃないか、って思う向きもあるだろう。
しかし、これで問題はない。と言うのも完成したストリームの、いわゆる添字番号(インデックス)とそこに含まれる数値にズレがあるんで、こうなってるんだ。
この計算法だと、0番目に1が来てる。つまり、例えば2を得た時、これは偶数なんで結果は1になるんだけど、1を直接参照出来ないのでインデックスの 0 を参照しないといけない。この場合、インデックスの計算は n / 2 - 1 で 0 を得られる。
同様の理由で、奇数の場合、3 × n + 1 を得る数にしなきゃなんないんだけど、添字番号と格納されてる数値が -1 ズレてるんで、3 × n でインデックス指定しないとならないわけだ。
作成した*collatz-seqs*と添字の関係。見事に1づつズレている。
もう一つの注意点が、今、コラッツ数列のストリームを書いてるのに、「完成したコラッツ数列のストリーム」から計算結果を拾ってきてる辺りだ。言い換えると、データを書いてる途中であたかも完成したデータが既にある、と言うような書き方になっている。
しかし、遅延評価だとこれは全く問題がない。大方の人間が再帰で悩むのは関数を書いてる最中に既に関数が完成してるような書き方になってる、って辺りだが、遅延評価だと、その書き方がデータ型にまで拡張されてるだけだ。
いや、むしろ、こういう書き方はプログラミング初心者の方が良くやる書き方で、その度にインタプリタやコンパイラに怒られて矯正されるわけだ。でもそれは正格評価、と言うフツーのプログラミング言語の評価方式だからこそ怒られる書き方であって、実は遅延評価はそのやり方を受け入れるんだ。
言い換えると、遅延評価が難しい、ってのは調教済みの人だからそう思うわけだな。素人になればなるほどこのテの方法論にはむしろ抵抗がない。何も知らんし、「思ったように書ける」のはむしろこのテの超高級言語の方だろう。
いずれにせよ、遅延評価はデータ型記述でさえ再帰構造を許す、って事だ。関数だけに限らないんだ(※2)。
さてさて、我々はこれで遅延評価により各数値に於けるコラッツ数列のストリームを手に入れた。んで、前回、実はどんなコラッツ数列も最後は1に収束する、と言う事実は証明されていない、と言う話をした。しかしながら、入手したストリームは理論上、無限の長さを持っている(そもそも2から始まる無限長の自然数列から作成してる)。と言う事は、どんな大きな自然数から始まるコラッツ数列だろうと、このストリームはその情報を知ってるんだ(笑)。すげぇだろ(笑)?
いや、ホントの事を言うと「どんな数値から始まるコラッツ数列だろうと知ってるフリをしてる」と言う事だけどな(笑)。何故なら、遅延評価、と言う名前な以上、実はまだ計算をしてないんだ(笑)。
でも現時点、理論的にはどんな自然数が先頭のコラッツ数列だろうと、メモリがあれば引っ張ってこれるわけ。すげぇだろ(笑)?
しかし、喜んでいられるのもここまでだった。
と言うのも、遅延評価だとProject Euler Problem 14には残念ながら太刀打ち出来なかったんだよなぁ。
元々、ハッシュテーブルで書いたメモワイズ手法と、遅延評価と、どっちが性能がいいんだろ?ってぇんで始めた実験だったんだけど、遅延評価が思ったよりメモリを食いつぶす、ってのが分かった。よって計算が終わらない。まるでC++やJavaのようになっちまったんだ(笑)。Scheme初の敗北、である。
コード的には次のコードが遅延評価での解題例だ。
(define (euler14 n)
(let ((strm (stream-take n *collatz-seqs*)))
(stream-car (stream-fold (lambda (y x)
(if (apply > (map stream-length `(,y ,x)))
y
x)) (stream-car strm) (stream-cdr strm)))))
単純には、無限長の長さのコラッツ数列のストリームから n 個引っ張ってきて、各要素の長さを調べていく。
ところが、この形式だと4桁程度までしか到達せず、ハッシュテーブルを使ったメモワイズ版より大幅に性能が落ちる事が分かった。いや、ホント、JavaやC++で書いたコードくらい性能が悪いんだわ(苦笑)。
Racketだからか?っつって他のScheme、Chicken Schemeでも試してみた。でもダメだった。要は、遅延評価はホント、結構メモリを喰うみたいで、ヒープ領域を食い尽くそうとするんだな。う〜む、思ったより性能が大幅に落ちる、ってのが今回やってみた実験で分かった。
一応、上にも書いたけど、無限の長さの何かを簡単に記述可能なんだけど、それが実体化する際に長さが大きいとフツーより計算負荷が半端ない、と(笑)。
ホンマ、こりゃダメだ、って結果だった(笑)。
う〜ん、残念!
Scheme初の敗北、である(※3)。
※1: 一般論ではないが、ここで言うストリームとは遅延評価用のリストだ。
※2: Javaでも8以降、ストリームと言う機能が搭載されたが、名前が同じだけで、機能的にはSchemeのそれに及ばない。そもそも再帰的に書けないストリームなんて一体何の役に立つんだ、ってなカンジだ。
Javaのストリームは、リスト及びArraylistの一時変換先に過ぎず、って事は正格評価で評価されたブツを変換してる、と言う仏作って魂入れずなデータ型なだけ、だ。
結果、型変換を多用する意味不明な姿になっていて、一体誰がこんなアホな機能にしようとしたんだか、一切意味が分からない。
※3: コラッツの問題が遅延評価と相性が悪い最大の理由は、遅延評価は何だかんだ言って「ストリームを先頭から順繰りに辿る構造になってる」事だ。ここがハッシュテーブルと決定的に違う。
例えば前回見たが、100万以下で最大の長さを持つコラッツ数列を生成する数値は83万7799だった。これは上のストリームで言うと83万7798番目に相当するが、そこの計算列に含まれる最大値は29億7498万4576だ。
ハッシュテーブルの場合、その「とある値」を計算して登録するが、しかしストリームに取ってはバカ正直に、29億7498万4576は29億7498万4575番目に現れる値なのである。
と言う事は、コラッツの問題では、ストリームで83万7798番目の値を知るには29億7498万4575番目までアタマから順繰りに見ていかないとならない、って事になる。
つまり、ハッシュテーブルで「そこに記録してある値」を直接引っ張り出すより明らかに計算コストがかかるんだよな。
こんな計算を、しかも一つに限らずそれこそ「天文学的な」回数でストリーム上を行ったり来たり、舐め回すように行ってりゃあ、そりゃ性能もC++やJava並に陥る、ってこった。
言い換えると、遅延評価は万能な手段ではなく、あくまで単純に昇順や降順で並んでるデータ向けで、あっちこっちにデータの「断片」が分布してるような構造には向かん、っちゅうこっちゃな。
