いつもどおり(?)インターネットを漂流していると、somos sequence(以下「ソモスの数列」)なるものを見つけました。より詳しいことはここを参照してほしいのですが、わたしなりに簡単に要約してみると――4以上の整数kについて次のような漸化式/数列を考えます。
- A1 = A2 = ... = Ak = 1
- An * A(n - k) = (1..(k / 2).floor).sum{|j| A(n-j) * A(n-(k-j))} [n > k]
一見整数列には思えない数列ですが、実のところk=4,5,6,7において無限に整数が続くことが証明されているそうです。わたしはこれを証明することには興味がないというか、証明するだけの数学力を持ち合わせていませんので、今回は「ソモスの数列」を無限リストにして遊んでみたいと思います。
さてやろうと決めて、思いついたのは以下の3選手。それぞれmake-somos-sequence1/2/3として実装しています。
できました。ここには記しませんが、一応テストらしきこともやって3つとも正しく動作することは確かめています。よって次は性能の計測に移りたいと思います――と問題発生。端的にいうと単純な再帰のmake-somos-sequence1がまったく使いものになりませんでした……。わたしの環境では第30項ごときで結果が返ってきません。しょうがないのでmake-somos-sequence2と3のどちらが優秀かを競うこととします。
(time (stream->list (stream-take (make-somos-sequence2 7) 300))) (time (stream->list (stream-take (make-somos-sequence3 7) 300))) ;(time (stream->list (stream-take (make-somos-sequence2 7) 300))) ; real 0.219 ; user 0.219 ; sys 0.000 ;(time (stream->list (stream-take (make-somos-sequence3 7) 300))) ; real 10.232 ; user 10.672 ; sys 0.156
結果はmake-somos-sequence2の圧勝でした。3はみずからを再帰的に呼び出しているのにくわえ、何本(?)もstreamを生成、高階関数に引き渡しているので、このあたりがボトルネックになったのではないかと想像します。やはり効率のいいschemeプログラミングをするにあたっては、できるだけ単純な再帰を避け、末尾再帰の可能性を探るということ大事になりそうで
