合并后的迭代器产生模糊的结果 [英] Merged iterators produce obscure results
问题描述
我想实现使用的埃拉托色尼算法筛素数生成器。我这样做只是为了尝试使用递归迭代器合并实施筛。
I'm trying to implement prime number generator using Sieve of Eratosthenes algorithm. I do it just to try using recursive iterator merging to implement sifter.
我做的是这样的:
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
理所应当的。这是为什么?我检查有以下code:
The first number to be sieved out is 4
. But the next is 12
, not 6
as it should be. Why is that? I checked it with the following code:
>>> 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]
所以,我们可以看出,在试验条件筛得到正确的结果。
So, as we may see, in test conditions sifter yields the correct results.
我在哪里犯了一个错误?我想这一定是一些小事,我只是不明白。
Where am I making a mistake? I think it must be something trivial that I just don't see.
推荐答案
我不得不承认,这东西有时会非常混乱(但不错的益智!)。
I have to agree, this stuff can sometimes be very confusing (but a nice puzzle!).
原来,当 P
的变化(该值的方式,我是你的筛
迭代变化使用Python 2.6.5,以测试这一点,而不是Python 3,所以打印语法有点不同):
Turns out that your sifter
iterator changes when the value of p
changes (by the way, I'm using python 2.6.5 to test this, not python 3, so print syntax is a bit different):
>> 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
部分与新的p尽快为p已更新评估。一个P是你的主循环,这就是为什么你没有得到预期的结果的确是更新。
So, the i*p
part of the iterator is evaluated with the new of p as soon as p has been updated. An p is indeed updated in your mainloop, which is why you don't get the expected result.
有一个简单的方法来解决这个问题:创建一个函数来产生筛迭代使得迭代器是无界为p:
There is an easy way to solve this: create a function to generate the sifter iterator such that the iterator isn't bounded to p:
def gensifter(x):
return (i*x for i in count(x))
和把它放进你的code(同样,我将它转换到Python 2.6.5):
and put this in your code (again, I converted it to 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!
现在,让我们看到的结果是:
Let's see the result now:
>>> 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]
Primenumbers一应俱全!
Primenumbers galore!
这篇关于合并后的迭代器产生模糊的结果的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!