0

for 循环遍历一个长列表。我试图加速修改列表的迭代（没有成功）。编码：

from math import sqrt
def holeofStrainer():
    isPrime = [False, False] + [True]*999999
    for num in range(3, len(isPrime)):
        if isPrime[num] == False:
            continue
        else:
            for x in range(2, int(sqrt(num)) + 1):
                if num % x == 0:
                    isPrime[num] = False        
                    break
            else:          
                isPrime[num] = True       
                for item in range (2, int(1000001/num) + 2):
                    ple = item * num
                    if ple < len(isPrime):
                        isPrime[ple] = False  
    return(isPrime) 
print(holeofStrainer())

第5 行的目标是避免不必要的计算。

在第 14-17 行中，我进行了修改（按照 Eratosthenes 的筛选，我将素数的倍数的值更改为 False）通过这种方式避免通过第 5 行进行更多计算。

概括：

  1. 是否可以从循环本身修改循环迭代列表？
  2. 如果答案是肯定的，为什么我的代码不好？
4

1 回答 1

1

我很确定，您偶然发现了过早优化的情况，即尝试在没有工作代码的情况下构建快速代码。

你的外部 for 循环

for num in isPrime:

迭代True和中的False值isPrime，而不是数字或索引位置。

            for item in range (2, int(1000001/num) + 2):
                ple = item * num
                if ple < len(isPrime):
                    isPrime[ple] = False

正如 Padraic Cunningham 的评论中所指出的，我不知道这部分代码应该实现什么。还有一个 DRY 违规（重复限制号）。

如果我清理所有这些，我最终会得到类似的东西

def holeofStrainer(nprimes):
    isPrime = [False, False] + [True] * (nprimes - 1)
    for num in (num for num, numIsPrime in enumerate(isPrime) if numIsPrime):                                            
        for x in xrange(2, int(sqrt(num)) + 1):                                                                           
            if num % x == 0:                 
                isPrime[num] = False
                break                      
     return isPrime

注意使用xrange()代替range()。如果这是 python 2，则range()在调用时会创建一个完整列表，这对于较大的数字会造成很大的伤害。

holeofStrainer(1000000)大约需要 14 秒才能跑到这里。这可能可以更快地完成（例如，首先检查和存储奇数），但是已经有更快的 SO 工作版本。

于 2015-05-09T21:53:51.080 回答