Erathostenes筛优化

Question

我用Python编写的erathostenes算法在几个星期前，它看上去像下面这样：

def erathostenes(n): 

    A = range(2,n+1) 
    B = [] 
    i = 0 

    while A[i] < math.sqrt(n): 
     B.append(A[i]) 
     j = i 
     aux = A[i] 
     while j < len(A): 
      if A[j]%aux == 0: 
       A[j] = 0 
      j += aux 
     i += 1 
     while A[i] == 0: 
      i += 1 
    for i in range(len(A)): 
     if A[i] != 0: 
      B.append(A[i]) 
     i += 1 
    return B 

想一点（我在编程小白）之后，我只是做了一些在我的算法的修改的右现在看起来像：

def erathostenes(n): 

    A = range(2,n + 1) 
    B = [] 
    i = 0 

    raiz = math.sqrt(n) 
    lenA = len(A)  
    rangeLenA = range(lenA) 

    while A[i] < raiz: 
     B.append(A[i]) 
     j = i 
     aux = A[i] 

     while j < lenA: 
      A[j] = 0 
      j += aux 
     i += 1 
     while A[i] == 0: 
      i += 1 
    for i in rangeLenA: 
     if A[i] != 0: 
      B.append(A[i]) 
     i += 1 
    return B 

如果我在n = 10.000.000在所述第一代码的执行时间执行的算法是大约7秒，并与所述第二代码是约4秒。

有关我的算法中更多优化的任何想法？谢谢！

Answer 1

i += 1 

在最后一个循环很有趣。

考虑与

for i in xrange(LenA) 

你避免产生你并不需要一个巨大的名单更换

for i in rangeLenA: 

。

编辑：

也可以这样考虑：而不是

for j in xrange(i,lenA,aux): 

：

while j < lenA: 

并修复错误

while A[i] <= raiz: 

通过fryday的建议。

Answer 2

代码中有错误。在

while A[i] <= raiz: 

你可以发现错误时，N为方形更改

while A[i] < raiz: 

。

对于opimization使用x范围为rangeLenA代替范围。

Answer 3

尝试阿特金筛。它是相似的，但它是对Eratosthenes Sieve的修改，它过滤掉2,3,5的所有倍数，以及其他一些优化。您可能还想尝试找到一个工具，告诉您每个操作的运行时间，并用更长的运行时间修改操作。

但是，由于您是编程新手，您最好接受其他算法的实现或者进行其他编程练习以提高效果。

Answer 4

试图做一个非循环版本只是为了好玩。它出来是这样的：

def erathostenes(n): 

    def helper_function(num_lst, acc): 

     if not num_lst: 
      return acc 
     if len(num_lst) == 1: 
      acc.append(num_lst[0]) 
      return acc 
     num = num_lst.pop(0) 
     multiples = ([x for x in range(num + 1, num_lst[-1] + 1) 
         if x % num == 0]) 

     remains = ([x for x in num_lst if x not in multiples]) 
     acc.append(num) 
     return helper_function(remains, acc) 
    return helper_function(range(2, n + 1), []) 

，当我跑的时间，得到了826我们后erathostenes（1000），和我的版本26ms（!!）。让我感到惊讶，它太慢了。使用函数式编程更有趣，但看起来并不适合这个问题，在Python中（我的猜测是它会在更多的函数式语言中更快）。

所以我尝试了一个命令式的版本。它看起来像这样：

def erathostenes_imperative(n): 
    limit = int(math.sqrt(n)) 
    def helper_function(flags, size): 
     for i in range(2,limit): 
      if flags[i] == True: 
       j = 2*i 
       while j < size: 
        if j % i == 0: 
         flags[j] = False 
        j = j + i 
     return [x for x in range(2, n + 1) if flags[x]] 
    return helper_function([True]*(n + 1), n) 

我所做的是将整数列表更改为True/False标志列表。直观地说，看起来迭代速度更快，对吗？

我的结果其中831ms为erathostenes_imperative（100000），而你的版本为1.45。

令人遗憾的是，它的写作速度更快。代码看起来很杂乱，所有的fors，whiles，我和j的