Python代碼優化

Question

最近我發現一個難題，需要我列出一個數字下面的所有循環素數。 在這種情況下，循環意味着如果我們旋轉數字，它仍然是素數： 例如。 1193是素數 1931年是黃金 9311是素數 3119是素數

這是我origanly代碼中寫道：

a=[] 
upto=1000000 

for x in range(upto): 
    a.append([x,0]) 

print('generated table') 

a[1][1]=1 
a[0][1]=1 

for n in range(2,int(math.sqrt(upto))): 
    for k in range(2,(int(upto/n)+2)): 
     try: 
      a[n*k][1]=1 
     except IndexError: 
      pass 
print('sive complete') 

p=[] 
for e in a: 
    if (e[1]==0): 
     p.append(e[0]) 
print('primes generated') 

s=[] 
for e in p: 
    pr=True 
    w=str(e) 
    if all(c not in w for c in ['2','4','6','8','5','0']): 
     for x in (w[i:]+w[:i] for i in range(len(w))): 
      if int(x) not in p: 
       pr=False 
     if pr==True: 
      s.append(e) 
      print('found',e) 
print(s) 

那是相當的慢！ （大約12s）我知道，總理一代並不完美，但最後一點是最慢的。我知道，對於高達= 10E6這個過程可以在一秒之內完成，所以經過一番研究，我贊成這個功能去掉任何字符串操作：

def rotate(n): 
    prev=[] 
    for l in range(6,0,-1): 
     if(n<10**l): 
      length=l 
    while(n not in prev): 
     prev.append(n) 
     n=(n // 10) + (n % 10) * 10**(length-1) 
     yield n 

我也刪除了5,0,2,4 ，6,8測試，因爲我不知道如何實現它。結果？它運行速度更慢！ （超過10分鐘，我猜測5,0,2,4,6,8測試是一個好主意）

我試過使用time.time（），但我沒有發現任何非常低效的東西（在第一個碼）。如何改進這些代碼？我目前正在使用哪些不良做法？

Answer 1

下面是一些優化的代碼：

import math 

upto = 1000000 

a = [True] * upto 
p = [] 

for n in xrange(2,upto): 
    if a[n]: 
     p.append(n) 
     for k in xrange(2,(upto+n-1)//n): 
      a[k*n] = False 

print('primes generated') 

s = [] 
p = set(p) 
for e in p: 
    pr=True 
    w=str(e) 
    if all(c not in w for c in ['2','4','6','8','5','0']): 
     for x in (w[i:]+w[:i] for i in range(len(w))): 
      if int(x) not in p: 
       pr=False 
       break 
     if pr: 
      s.append(e) 

print(s) 

最重要的優化：

1. 簡化了篩代碼
2. 轉化質數的列表轉換成一組。這使得測試x in p是logaritmic而不是線性
3. 添加break語句發現非黃金旋轉

加入清潔（但等效）代碼時：

import math 

upto=1000000 

sieve = [True] * upto 
primes = set() 

for n in xrange(2,upto): 
    if sieve[n]: 
     primes.add(n) 
     for k in xrange(2,(upto+n-1)//n): 
      sieve[k*n] = False 

def good(e): 
    w = str(e) 
    for c in w: 
     if c not in '1379': 
      return False 
    for i in xrange(1,len(w)): 
     x = int(w[i:]+w[:i]) 
     if x not in primes: 
      return False 
    return True 

print filter(good,primes) 

Answer 2

下來就可以減在第一次測試所需的時間內進行一組比較，而不是每次像這樣進行完整的迭代：

flags = set('246850') 
if not set(str(e)).intersection(flags): 
    # etc... 

它不僅可以按對數比例縮放，還可以讓您在此步驟中選擇另外兩個因子。你甚至可以進一步加快這並使其多了幾分優雅的超過轉變到一個發電機，然後可以用做最後的檢查，像這樣：

flags = set('246850') 
primes = set(p) 
easy_checks = (str(prime) for prime in primes if not set(str(prime)).intersection(flags)) 

最後，你可以重寫最後一點，以獲得擺脫所有的追加和諸如此類的東西，這往往是超慢，像這樣：

test = lambda number: any((int(number[i:]+number[:i]) in primes for i in xrange(len(number)))) 
final = [number for number in easy_checks if test(number)]