合併迭代器產生難以理解的結果

Question

我試圖使用Sieve of Eratosthenes算法實現素數生成器。我這樣做只是嘗試使用遞歸iterator merging來實現篩選器。

我做到這一點：

from itertools import count,islice,groupby 
from heapq import merge 


def primes3(): 
    p = 2 
    yield p 
    sifter = (i*p for i in count(p)) 
    s = next(sifter) 
    for p in count(p+1): 
     if p==s: # this p is sieved out 
      print('s: {}'.format(s)) 
      s = next(sifter) 
     else: 
      yield p # this is prime 
      print('p: {}'.format(p)) 
      sifter = (k for k, g in groupby(merge(sifter,(i*p for i in count(p))))) #add this serie to the sifter: p*p, p*(p+1), p*(p+2), ... 


print(list(islice(primes3(),10))) 

輸出是：

p: 3 
s: 4 
p: 5 
p: 6 
p: 7 
p: 8 
p: 9 
p: 10 
p: 11 
s: 12 
[2, 3, 5, 6, 7, 8, 9, 10, 11, 13] 

第一個數字被篩分爲4。但接下來是12，而不是6，因爲它應該是。這是爲什麼？我用下面的代碼檢查的話：

>>> sifter = (i*2 for i in count(2)) 
>>> next(sifter) 
4 
>>> sifter = (k for k, g in groupby(merge(sifter,(i*3 for i in count(3))))) 
>>> print(list(islice(sifter,20))) 
[6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 26, 27, 28, 30, 32, 33, 34] 

所以，我們可以看出，在試驗條件篩得到正確的結果。

我在哪裏犯錯？我認爲這一定是微不足道的，我只是看不到。

Answer 1

我不得不同意，這些東西有時會很混亂（但是一個很好的謎題！）。

原來，你sifter迭代變化時p變化值（順便說一下，我使用的Python 2.6.5測試這一點，而不是Python 3，所以打印語法有點不同）：

>> p = 2 
>> sifter = (i*p for i in count(p)) 
>> for x in range(3): 
>> print next(sifter) 
4 
6 
8 
>>> # now lets see what happens when we change p 
>>> p = 3 
>>> for x in range(3): 
>>>  print next(sifter) 
15 
18 
21 

因此，只要p已更新，迭代器的i*p部分將與p的新一起評估。一個p確實在你的主循環中更新，這就是爲什麼你沒有得到預期的結果。

有一個簡單的方法來解決這個問題：創建一個函數來生成篩迭代使得迭代器是無界爲P：

def gensifter(x): 
    return (i*x for i in count(x)) 

，並再次把這個在你的代碼（我轉換它到Python 2.6.5）：

def primes3(): 
    p = 2 
    yield p 
    sifter = gensifter(p) # <-- changed! 
    s = next(sifter) 
    for p in count(p+1): 
     #print '(testing p = %d\ts = %d)' % (p, s) 
     if p==s: # this p is sieved out 
      print 's:', s 
      s = next(sifter) 
     else: 
      yield p # this is prime 
      print 'p:', p 
      sifter = (k for k, g in groupby(merge(sifter,gensifter(p)))) # <-- changed! 

讓我們來看看現在的結果是：

>>> print list(islice(primes3(), 10)) 
p: 3 
s: 4 
p: 5 
s: 6 
p: 7 
s: 8 
s: 9 
s: 10 
p: 11 
s: 12 
p: 13 
s: 14 
s: 15 
s: 16 
p: 17 
s: 18 
p: 19 
s: 20 
s: 21 
s: 22 
p: 23 
s: 24 
s: 25 
s: 26 
s: 27 
s: 28 
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29] 

總理數字嘉豪！