Оптимизация кода на Python

Недавно я нашел загадку, которая потребовала, чтобы я перечислил все циклические числа ниже числа. В этом контексте циклический означает, что, если мы поворачиваем цифры, он все еще является простым: например. 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)

Это было довольно медленно! (около 12 секунд) Я знаю, что первое поколение не идеально, но последний бит является самым медленным. Я знал, что этот процесс для upto = 10** можно сделать за секунду, поэтому после некоторого исследования я удалил любые строковые манипуляции в пользу этой функции:

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(), но я не нашел ничего ужасно неэффективного (в первом коде). Как можно улучшить этот код? Есть ли какие-то плохие практики, которые я сейчас использую?

2 ответа

Вот некоторый оптимизированный код:

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. добавил оператор 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)


Вы можете сократить время, необходимое для первого теста, выполнив заданное сравнение вместо выполнения полной итерации каждый раз так:

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

licensed under cc by-sa 3.0 with attribution.