为什么与迭代素搜索相比"optimized"埃拉托色尼筛如此慢？(蟒蛇 3)

Question

我尝试了一些不同版本的Sieve，包括我自己的和不同页面的。不过，他们都有一个共同点。它们比我使用的迭代方法慢，这与我读到的所有关于它的内容都相反。是我的原因还是因为python的列表处理速度慢？

from time import time
from random import randint
def isPrime(n):
if (n <= 3):
return (n >= 2)
i = 5
if (n % 2 == 0 or n % 3 == 0) :
return False
for i in range(5, int(n**.5)+1, 6):
if (n%i == 0 or n%(i+2) == 0):
return False
return True
def sieveOfEratosthenes(n):
array = [True for i in range((n-1)//2)]
i = 3
for e in array:
if e is True:
for k in range(i**2, n+1, 2*i):
array[k//2-1] = False
i += 2
return [2]+[2*i+1 for i, e in enumerate(array, 1) if e is True]
def runIsPrime(arr):
start = time()
for e in arr:
isPrime(e)
print("Primes:tt", time()-start)
def runSieveOfEratosthenes(arr):
start = time()
primes = sieveOfEratosthenes(max(arr))
#print("Sie. mid.:t", time() - start)
for e in arr:
e in primes
print("Sieve tot.:t", time()-start)
upto = 10**6
times = 10**3
arr = [randint(2, upto) for i in range(times)]
runIsPrime(arr)
runSieveOfEratosthenes(arr)

打印输出：

Primes:      0.0019884109497070312 
Sieve tot.:  1.1940925121307373

Answer 1

sieveOfEratosthenes函数返回一个列表，检查列表中是否有值为O(n)。然而，即使在将代码更改为使用set之后，筛选也会比直接的方法慢：

def runSieveOfEratosthenes(arr):
start = time()
primes = set(sieveOfEratosthenes(max(arr)))
#print("Sie. mid.:t", time() - start)
for e in arr:
e in primes
print("Sieve tot.:t", time()-start)
upto = 10**6
times = 10**3
arr = [randint(2, upto) for i in range(times)]
runIsPrime(arr)
runSieveOfEratosthenes(arr)

输出：

Primes:      0.0013408660888671875
Sieve tot.:  0.19181394577026367

这是因为您的函数实际上在复杂性上有所不同。isPrime检查到根并提前退出，这使它能够快速处理小的复数。sieveOfEratosthenes构建一个筛选，即O(n log log n)，它不依赖于列表的长度。让我们看看我们是否只通过素数的更大大小的列表：

In [57]: ps = [996361] * 10**4
In [58]: runIsPrime(ps)
Primes:      0.20616984367370605
In [59]: runSieveOfEratosthenes(ps)
Sieve tot.:  0.1783740520477295

您可以看到，runIsPrime的性能急剧下降，而runSieveOfEratosthenes的性能变化不大。如果您认为这里可能涉及缓存，让我们准备不同素数的列表：

In [64]: ps2 = [x for x in range(10**5, 10**6) if isPrime(x)]
In [65]: len(ps2)
Out[65]: 68906
In [66]: ps2[-1]
Out[66]: 999983
In [67]: runIsPrime(ps2)
Primes:      0.9789869785308838
In [68]: runSieveOfEratosthenes(ps2)
Sieve tot.:  0.18288207054138184

正如您所看到的，runIsPrime的执行时间随着数组长度的增加而增加，而runSieveOfEratosthenes的执行时间基本保持不变。让我们进一步增加阵列大小：

In [69]: runIsPrime(ps2 * 10)
Primes:      9.91222095489502
In [70]: runSieveOfEratosthenes(ps2 * 10)
Sieve tot.:  0.2231128215789795

作为一个结论——如果你需要检查一个数字是否是素数，你可以迭代到这个数字的根——这将比构建一个筛子更快。如果你有一个数字列表，你可能想运行一些测试，如果列表很小，你仍然可以使用第一种方法。但当你有一大堆数字要检查时，最好建一个筛子。