我正在尝试使用 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]
因此,正如我们所看到的,在测试条件下 sifter 会产生正确的结果。
我哪里出错了?我认为这一定是一些我看不到的微不足道的事情。
最佳答案
我必须同意,这些东西有时会非常令人困惑(但这是一个很好的谜题!)。
事实证明,当 p
的值更改时,您的 sifter
迭代器也会更改(顺便说一句,我使用 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 的 new 进行计算。 p 确实在您的主循环中更新了,这就是您没有得到预期结果的原因。
有一个简单的方法可以解决这个问题:创建一个函数来生成 sifter 迭代器,这样迭代器就不会绑定(bind)到 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]
质数丰富!
关于python - 合并迭代器产生模糊的结果,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12095846/