在Python中寻找素筛

2024-03-29 02:33:16 发布

您现在位置:Python中文网/ 问答频道 /正文

我正在尝试学习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。你知道吗


Tags: in版本foriftopdef基准pr
3条回答

这是因为字典的键没有排序。有时,碰巧for si in sieved:会按递增的顺序循环遍历您的键。 在上一个例子中,si得到的第一个值足够大,可以立即中断循环。你知道吗

您可以简单地使用: 对于分选(筛分)的硅:

好吧,看看运行时,你会发现上一个例子中的运行时几乎比基准快5倍,而它通常慢5倍。所以这是一个危险信号,也许你没有执行所有的迭代?(它的速度快了5倍,而素数几乎是10倍……)

我现在没有时间进一步研究代码,但我希望这能有所帮助。你知道吗

这个筛子需要在候选素数上进行循环排序。所讨论的代码是枚举字典的键,这些键不能保证是有序的。相反,继续使用xrange初始化主筛选循环的字典以及返回结果循环,如下所示:

def sieve3(n):
    top = n+1
    sieved = dict.fromkeys(xrange(3,top,2), True)
    for si in xrange(3,top,2):
        if si * si > top:
            break
        if sieved[si]:
            for j in xrange(3*si, top, si*2):     
                sieved[j] = False
    return [2] + [pr for pr in xrange(3,top,2) if sieved[pr]]

相关问题 更多 >