Python代码优化

最近我发现一个难题，需要我列出一个数字下面的所有循环素数。在这种情况下，循环意味着如果我们旋转数字，它仍然是素数：例如。 1193是素数 1931年是黄金 9311是素数 3119是素数Python代码优化

这是我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（），但我没有发现任何非常低效的东西（在第一个码）。如何改进这些代码？我目前正在使用哪些不良做法？

来源

2014-01-07 Michal

这个问题似乎是题外话，因为它属于上http://codereview.stackexchange.com – jonrsharpe

好，消除了即使数字和5肯定是有价值的，因为它会消除你需要测试的绝大多数数字。任何2+数字循环素数必须只包含[1,3,7,9]的某个子集。我认为你也许可以用合理的长度对它进行暴力破解 - 对于一个N位解决方案，最大可能有4^N个可能性（对于各种对称性来说更少），对于任何肯定的可能性，4^N <10^N ñ... – twalberg

我怎么可能在那里迁移它？编码SE的数量令人困惑 – Michal

下面是一些优化的代码：

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)

最重要的优化：

简化了筛代码
转化质数的列表转换成一组。这使得测试x in p是logaritmic而不是线性
添加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)

来源

2014-01-07 21:59:23

下来就可以减在第一次测试所需的时间内进行一组比较，而不是每次像这样进行完整的迭代：

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)]

来源

2014-01-07 22:15:10

我尝试了您的代码来查找素数，但它不起作用。它给出了所有的数字。 –

由于某种原因，筛子不能按预期工作。它声称4是素数（素数[2] = 4） – Michal

@Michal哦，引人入胜。它看起来像Python与递归生成器有一个奇怪的问题，所以不会像其他地方那样工作。删除该部分，但其余部分仍然有效。 –

Python代码优化

回答

相关问题