为什么我的埃拉托色尼筛法如此缓慢？

Question

为什么我的埃拉托色尼筛法如此缓慢？

pythonperformancealgorithmtime-complexityprimes

6

我正在解决一些Project Euler上的问题，需要生成200万个质数来解决一个问题。我的埃拉托色尼筛法实现非常慢，但我不知道原因。请问有人可以解释一下这种实现的主要问题吗？我认为它很漂亮，但后来发现它是完全糟糕的:(。我在网上找到了另一个实现，比我的快得多。

def generatePrimes(upperBound):
    numbers = range(2,upperBound+1)
    primes = []

    while numbers:
        prime = numbers[0]
        primes.append(prime)
        numbers = filter((lambda x: x%prime),numbers)
    return primes

编辑：感谢所有的回答！结论是问题出在过滤器上，因为它会遍历每个元素（而不仅仅是要标记为非质数的元素），并且每次都创建一个新列表。使用传统的for循环和一轮过滤进行重写后，速度快了很多。新代码：

def generatePrimes(upperBound):
numbers = range(2,upperBound+1)

for i in xrange(len(numbers)):
    if(numbers[i] != 0):
        for j in xrange(i+numbers[i],len(numbers),numbers[i]):
            numbers[j] = 0

primes = filter(lambda x: x,numbers)
return primes

- Alex

10

首先，这不是埃拉托色尼筛法。它是试除法。 - Fred Larson

2

我认为从技术上讲这是一个筛子，但你在每次迭代中使用过滤函数执行大量的分配。大多数筛子都被优化为仅执行一次大型数组分配，而你的筛子执行从len(upperBound)开始的大小为O(n)的分配。 - dustyrockpyle

2

@dustyrockpyle：不，这与埃拉托斯特尼筛法有显著的区别。当外部循环到达某个数字时，SoE只处理该数字一次，并且对于其质因数分解中的每个质数也只处理一次；而此函数对于每个小于其第一个质因数的质数都会处理一次该数字。平均而言，这将导致查看每个数字的次数更多。 - user2357112

@PadraicCunningham 这个问题已经在这里被回答了很多次，我自己最喜欢的是http://stackoverflow.com/a/9302299/5987 - Mark Ransom

1

有一个可以帮助的方法是，一旦你测试的质数大于sqrt(upperBound)，就跳出循环，因为剩下的任何数都保证是质数。 - Mark Ransom

显示剩余8条评论

2个回答

2

运行cProfile显示大部分时间都花费在过滤器上。用列表推导式替换过滤器可以将速度提升约2倍。

numbers = [n for n in numbers if n%prime != 0]

但这并没有真正解决主要问题，即您在每次迭代中都重新创建数字列表，这是很慢的。更快的实现方法是通过将非质数替换为0或类似的方式进行标记。参考http://groups.google.com/group/comp.lang.python/msg/f1f10ced88c68c2d。

- James K

1

如果在代码中看到 n%prime，那不是埃拉托斯特尼筛法。 - jfs

同意。引用维基百科的话说，“生成合成数比测试它们要快得多”。 - James K

@JamesK 是的，因为你生成每个合数只需使用其质因数（小于它的平方根），但在测试时，每个候选数都要被所有小于它的平方根的质数进行测试，而不仅仅是它的质因数。 - Will Ness

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user2357112 · Accepted Answer

埃拉托色尼筛法长这样：

def sieve(n):
    primality_flags = [True]*(n+1)
    primality_flags[0] = primality_flags[1] = False
    primes = []
    for i, flag in enumerate(primality_flags):
        if flag:
            primes.append(i)
            for j in xrange(2*i, n+1, i):
                primality_flags[i] = False
    return primes

当外层循环到达某个数时，它只处理一次，但如果该数能被其中的质数整除，将会再次处理。大约有1/2的数字可被2整除，大约有1/3可被3整除，因此，渐进地说，每个数字被处理的平均次数为1加上前n个质数倒数之和。这个和约为log(log(n)), 因此，筛法的时间复杂度为O(n*log(log(n)))，假设算术运算是常数时间。这非常好。

你的函数没有做到这一点。你的filter会遍历numbers中的每个元素，无论它是否能被prime整除。每个元素都会被处理，直到第一个可以整除它的质数为止，并且处理质数p会删除大约1/p的numbers元素。假设质数的序列为p[0]，p[1]，p[2]等，numbers大小的序列为n[0]，n[1]，n[2]等，我们有以下近似递归关系：

n[0] = upperBound - 1
n[1] = n[0] * (p[0]-1)/p[0]
n[2] = n[1] * (p[1]-1)/p[1]
...
n[k+1] = n[k] * (p[k]-1)/p[k]

你的算法需要的时间大致与 numbers 为空之前的 n 值之和成比例。我没有分析过该系列的行为，但计算表明增长速度要比 O(n*log(log(n))) 糟糕得多。（编辑：当我撰写此答案时，我没有想到的分析表明它是 O((n/log(n))^2)。）