素数列の生成2

あの話のエピローグには続きがあって「猿をぶら下げる代わりに紐を結ぶようにした、軽いから」というのがあるのだけれども、どういうことなのか昨晩やっとわかった。

（なんのことかわかってなかったという自覚があったのだから、隠さずにそう書くべきだったのではないか、オレ？ 早速悪い癖を発見。）

「猿が今いる場所, 等差数列イテレータの組」である必要はなくて、「紐が結ばれている場所、公差の組」で十分なんだ。足し算はハト使いの管理者がやればいいわけで。だから数字書いた紐をちょっと勤勉になった管理人が自分で動かせばすむ、というたとえになるのか。

あれ？ イテレータだらけのエラトステネスの篩だったはずなのに、別物になってしまった。

# coding: utf-8

u"""素数列の生成 - 遅延評価によるエラトステネスの篩
"""

def _seq_with_common_difference(first, diff):
    u"""初項 first 公差 diff の等差数列"""

    while True:
        yield first
        first += diff

def prime_numbers():
    u"""素数"""

    yield 2
    odd = _seq_with_common_difference(3, 2)
    prims = {}
    prims_pop = prims.pop
    for i in odd:
        d = prims_pop(i, None)
        if d is None:
            yield i
            i, d = i ** 2, i * 2
        else:
            i += d
            while i in prims:
                i += d
        prims[i] = d

後は…生成済みの値の保持はハッシュ（辞書）である必要ないのかも？ ハト使い確認済みの箇所には猿はいないはずだから、いや、進んだ先に猿がいるかどうかのチェックは必要で、やはり辞書をつかうべきか？ はたして、 dict, list, collections.deque のうち、どれがもっとも効率がよいのだろうか？