|
気分転換に 入門 Haskell に載っていた遅延評価によるエラトステネスの篩を参考に、Python でジェネレータだらけの篩を書いてみることを考える。
元はこんなコード。
primes = 2:(sieve [3, 5..])
where sieve (p:xs) = p:(sieve [x | x <- xs, x `mod` p /=0])
コンピュータの気持ちになってリストを前から評価していくと、
上のコードは結局試し割算を順番に繰り返しているだけだ
(素数列だけで割ることは良いことだが、x が素数である場合に平方根で止まらないので通常の試し割算より効率が悪い)。
等差数列で倍数が取り除けるということを使って初めて篩と呼べるので、
これをエラトステネスの篩と呼ぶのは実は誇大宣伝だ。
primes = 2:(sieve [3, 5..])
where sieve (p:xs) = p:(sieve [x | x <- xs, not elem x [0, p..]])
が正しい Haskell のプログラムかは知らないが、気持ちはこんな感じ。
といったことを考えていたら妙なイメージが浮かんだ。
雲梯を進む怠惰な猿たち
3以上の奇数の番号が振られている横棒が半無限に並んでいる雲梯。
そこに不思議な管理人が現れる。
管理人は 3 という番号の棒に何もないことを見つけると、2段飛ばしで進んでいく猿を 9 という番号が振られている棒にぶら下げ、3 という番号を伝書鳩に託して休憩する。
猿は怠け者なので進めと言われないと進まない。
管理人の元へ、子どもがやってきて何やら言葉を交わし、頭を下げると帰っていく。
管理人は腰を上げ、5 に猿がいないことを確認すると、4段飛ばしで進んでいく猿を 25 という番号の棒にぶら下げる。
やはり伝書鳩に今度は 5 という番号を託して休憩する。
もう一度同じようなことがあって 7 という番号を付けた鳩が飛んでいった後、次に子どもがやってきた時、管理人のすることが少し変わる。
2段飛ばしで進んでいく猿が 9 番の棒にぶら下がっているのを見ると、管理人は猿に進むように促す。
猿は眠たそうに 15 の棒に移る。
管理人はそれを見届けると、11 番に何もいないことを確認し、10段飛ばしで進んでいく猿を 121 番の棒にぶら下げる。
11 という番号を付けた鳩が飛んでいく。
眠たくなるような景色は 37 の鳩が飛んでいった後、ちょっとした変化を迎える。
いつものように管理人の元へ子どもがやってきて去っていく。
管理人は立ち上がると 39 の横棒にぶら下がる猿に進むように促す。
猿は2段飛ばしで 45 の棒に行くがそこには既に4段飛ばしの猿がいる。
すると、あの怠惰な4段飛ばしの猿が歯を剥き威嚇する。
2段飛ばしの猿は逃げるように、でもいつも通り2段飛ばしで 51 の棒に移り、そこに落ち着く。
一つの横棒に2匹がぶら下がることはできずに、後から来た猿が更に移動していくようだ。
管理人は何事も無かったかのように、40段飛ばしの猿を遠くの方にぶら下げ、鳩に 41 の番号を託して放すと、いつものように休憩する。
解題
Python でプログラムを組む話だった。
奇素数生成のジェネレータに相当する。
外部からの呼出がある(子どもが頼みに来る)と、ジェネレータ(管理人)は奇数列(雲梯)から次の素数(空いている棒の番号)を探して yield する(鳩を飛ばす)。
イテレータメソッド(子どもにおつかいを頼む方法)さえ知っていれば実装の詳細は(猿が虐待されていようと)関係はない。
が、ここでの目的はその実装の詳細を述べることで、初項 p2 公差 p の等差数列が、p-1 段飛ばしの猿である。
この等差数列も遅延評価される(怠惰である)。
奇数列から、現れた素数の倍数を取り除いているので、残った列の最初が次の素数になる、ということでエラトステネスの篩の一つの実装方法だと解ってもらえただろうか。
エピローグ
その後、もう一度あの雲梯を見に行くと、そこには猿の影はなくさまざまな長さの紐が垂れ下がっていた。
「猿はもう使わないのですか」
と尋ねるとこんな答えが帰ってきた。
「この雲梯はいつまでも使えるように見えますが、猿が一定以上に増えると重みで壊れてしまうのです。
紐は自分で動いてはくれませんが、猿よりはずっと軽い。
長さに従って私が結び直せば、飛んでいく鳩は同じですから」
|
