병합 된 반복자가 모호한 결과를 생성합니다.

Question

Sieve of Eratosthenes 알고리즘을 사용하여 소수 생성기를 구현하려고합니다. sifter를 구현하기 위해 재귀적인 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

나는이 물건을 때로는 매우 혼란 스럽다 (그러나 좋은 퍼즐!) 동의해야합니다.

는 p 값이 변경 될 때 sifter 반복자가 변경 것으로 밝혀 (그런데, 나는 이것을 테스트하기 위해 파이썬 2.6.5를 사용하고,하지 (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 

따라서 이터레이터의 i*p 부분은 p가 업데이트 되 자마자 새로운 p로 평가됩니다. p가 실제로 mainloop에서 업데이트되므로 예상 결과가 나오지 않습니다.

는이 문제를 해결하는 쉬운 방법이있다

: 반복자가 P에 묶여 있지되도록 체로 반복자를 생성하는 함수를 작성 :

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

다시 (코드에 넣고, 나는 변환 그것은) 2.6.5를 파이썬 :

>>> 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] 

국무 :

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! 

이의 지금 결과를 보자 숫자가 풍부 해!