Я немного борюсь с дальнейшей оптимизацией моей основной вычислительной функции.
Пока что я остановился на решете Эратосфена.
Я нашел на https://primesieve.org/ подсказку для дальнейшей оптимизации с реализацией колес и ссылкой к этой статье: ftp://ftp.cs.wisc.edu/ паб/techreports/1991/TR1028.pdf
Я пытался перевести этот псевдокод на python, но он не работает должным образом. У меня такое ощущение, что итерации на шаге B неверны. При вычислении prime_sieve_fast(100, 3)
91 не удаляется. Это логично, поскольку текущие переменные никогда не достигают 7*13
или 13*7
. Что я сделал не так?
def prime_sieve(n):
prime_list=[0,0]
for i in range(2,n+1):
prime_list.append(1)
for p in range(2,int(n**(1/2))+1):
for j in range(p**2,n+1,p):
prime_list[j]=0
primenumbers=[]
for i in range(n):
if prime_list[i+1]==1:
primenumbers.append(i+1)
return prime_list,primenumbers
def prime_sieve_faster(n,n_wheel):
primes=prime_sieve(100)[1][:n_wheel+1]
w=wheel(n_wheel,primes[:-1])
M=len(w)
prime_list=[1]*(n+1)
for r in range(M):
if w[r%M]==0:
b=0
else:
b=1
for i in range(r,n+1,M):
prime_list[i]=b
for i in range(n_wheel):
prime_list[primes[i]]=1
prime_list[1]=0
for p in range(primes[n_wheel],int(n**(1/2))+1):
print(p)
step=w[p%M]
if step==0:
prime_list[p]=0
else:
for f in range(p,p+M+1,step):
for x in range(p*f,n+1,M*p):
prime_list[x]=0
print(p,f,x,M*p)
primenumbers=[]
for i in range(n):
if prime_list[i+1]==1:
primenumbers.append(i+1)
return prime_list,primenumbers
def wheel(k,primes):
M=1
for prime in primes:
M*=prime
W=[1]*M
for prime in primes:
for x in range(0,M,prime):
W[x]=0
W[M-1]=2
prev=M-1
for x in range (M-2,0,-1):
if W[x]!=0:
W[x]=prev-x
prev=x
return W
for i in range(2,n+1):prime_list.append(1)
приводит к тому же результату, что иprime_list += range(2,n+1)
. Вы можете использовать линтер PEP8, чтобы многое сделать за вас. normal_sieve было самым простым и быстрым решетом, которое я смог найти. В реальном коде C вы будете использовать битовый массив. Но опять же, битовый массив не имеет значения. Дело в УПРОЩЕНИИ. И да, не смотрите на sieve в этом коде, просто на normal_sieve. - person mikeLundquist   schedule 30.10.2018PROD( p/(p-1) )
по всемp
с вwheel
. сwheel = {3,5,7,11}
это 2,4x, а с13
это 2,6x. Итак, не даже на один порядок. Простое число2
дает 2x ускорение само по себе, поэтому технически это примерно 5x ускорение в целом, но так легко пропускать четные числа, что я бы сказал, что это не так. считать. И эти ускорения являются теоретическими — использование пространства возрастает настолько, что работа с механикой колес быстро перевешивает ожидаемые выгоды. Я получил ускорение 2,2x с3,5,7
и остался доволен. :) - person Will Ness   schedule 30.10.2018