我正在尝试学习python,我想尝试开发自己的prime sieve将是下午的一个有趣的问题。到目前为止,当需要的时候,我只需要导入一个我在网上找到的Eratosthenes筛的版本——我用这个作为我的基准。你知道吗
在尝试了几个不同的优化之后,我认为我已经编写了一个相当不错的筛选:
def sieve3(n):
top = n+1
sieved = dict.fromkeys(xrange(3,top,2), True)
for si in sieved:
if si * si > top:
break
if sieved[si]:
for j in xrange((si*2) + si, top, si*2): [****]
sieved[j] = False
return [2] + [pr for pr in sieved if sieved[pr]]
使用前1000000个整数作为我的范围,这段代码将生成正确数量的素数,并且只比我的基准慢3-5倍。我正要放弃,拍拍自己的背时,我尝试了一个更大的范围,但它不再工作!你知道吗
n = 1,000 -- Benchmark = 168 in 0.00010 seconds
n = 1,000 -- Sieve3 = 168 in 0.00022 seconds
n = 4,194,304 -- Benchmark = 295,947 in 0.288 seconds
n = 4,194,304 -- Sieve3 = 295,947 in 1.443 seconds
n = 4,194,305 -- Benchmark = 295,947 in 3.154 seconds
n = 4,194,305 -- Sieve3 = 2,097,153 in 0.8465 seconds
我认为问题来自于[****]
的行,但是我不明白为什么它会这么坏。它应该把“j”的每一个奇数倍都标记为假,而且大多数时候都是有效的,但是对于任何超过4194304的东西,这个筛子都是坏的。(公平地说,它也会在其他随机数字上中断,比如10000)。你知道吗
我做了一个更改,它大大减慢了我的代码速度,但它实际上适用于所有值。这个版本包括所有的数字(不仅仅是赔率),但在其他方面是相同的。你知道吗
def sieve2(n):
top = n+1
sieved = dict.fromkeys(xrange(2,top), True)
for si in sieved:
if si * si > top:
break
if sieved[si]:
for j in xrange((si*2), top, si):
sieved[j] = False
return [pr for pr in sieved if sieved[pr]]
有人能帮我弄清楚为什么我原来的功能(sieve3)不能持续工作吗?你知道吗
编辑:我忘了提一下,当Sieve3“中断”时,Sieve3(n)返回n/2。你知道吗
这是因为字典的键没有排序。有时,碰巧
for si in sieved:
会按递增的顺序循环遍历您的键。 在上一个例子中,si得到的第一个值足够大,可以立即中断循环。你知道吗您可以简单地使用: 对于分选(筛分)的硅:
好吧,看看运行时,你会发现上一个例子中的运行时几乎比基准快5倍,而它通常慢5倍。所以这是一个危险信号,也许你没有执行所有的迭代?(它的速度快了5倍,而素数几乎是10倍……)
我现在没有时间进一步研究代码,但我希望这能有所帮助。你知道吗
这个筛子需要在候选素数上进行循环排序。所讨论的代码是枚举字典的键,这些键不能保证是有序的。相反,继续使用
xrange
初始化主筛选循环的字典以及返回结果循环,如下所示:相关问题 更多 >
编程相关推荐