Python代码优化

Question

最近，我发现了一个难题，要求我列出所有循环素数以下的数字。在这个上下文中，循环意味着如果我们旋转数字，它仍然是素数:例如。1193是素数1931是素数9311是素数3119是素数。

这是我最初写的代码：

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)我知道，第一代不是十全十美的，但最后一点是最慢的。我知道upto=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测试，因为我不知道如何实现它。结果是什么呢？它跑得更慢！(十分钟内，我想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不再是线性的，而是逻辑的。
3. 当发现非素数旋转时，添加了一个中断语句

添加了清洁器(但与此相当)代码：

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...

它不仅以对数方式缩放，而且还能让你在这一步中获得另一个2的因子。您甚至可以进一步加快速度，并通过将其转换到生成器，从而使其更加优雅，然后您可以使用它来完成最后的检查，如下所示：

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