Czy ktoś może mnie nauczyć, jak zoptymalizować ten skrypt "drukuj do n-tego pierwszego numeru"?

Question

Mam 17 lat, rozpoczynam programowanie za pomocą języka programowania Python.

Starałem się zoptymalizować ten algorytm, być może poprzez wyeliminowanie jednej z pętli lub z lepszym testem w celu sprawdzenia liczb pierwszych.

Próba obliczenia i wyświetlenia 100000 liczb pierwszych powoduje wstrzymanie skryptu na około 6 sekund, ponieważ wypełnia listę wartościami liczb pierwszych, zanim lista liczb pierwszych zostanie zwrócona do konsoli jako wynik.

Byłem eksperymentować z użyciem

print odd, 

po prostu wydrukować każdy znaleziony liczbą pierwszą, która jest szybsza w przypadku mniejszych nakładów, takich jak n = 1000, ale dla n = 1000000 listy sama drukuje znacznie szybciej (zarówno w powłoce Pythona i w konsoli).

Być może cały kod/algorytm powinien zostać przebudowany, ale skrypt powinien pozostać zasadniczo taki sam: użytkownik wpisuje liczbę liczb pierwszych do wydrukowania (n), a skrypt zwraca wszystkie liczby pierwsze do n-tego numer.

from time import time 
odd = 1 
primes = [2] 
n = input("Number of prime numbers to print: ") 
clock = time() 
def isPrime(number): 
    global primes 
    for i in primes: 
     if i*i > number: 
      return True 
     if number%i is 0: 
      return False 
while len(primes) < n: 
    odd += 2 
    if isPrime(odd): 
     primes += [odd] 
print primes 
clock -= time() 
print "\n", -clock 
raw_input() 

może chcę przepisać cały skrypt użyć sita jak sito Atkin: http://en.wikipedia.org/wiki/Sieve_of_Atkin

jednak jestem po prostu początkujący w Pythonie (lub nawet przy programowaniu: Zacząłem pisać tylko 2 kod kilka tygodni temu) i byłoby dla mnie dużym wyzwaniem wymyślić jak kodować algorytm Sieve of Atkin w Pythonie.

życzę hakera google tam będzie ręka trzymać mnie za rzeczy, jak to :(

Answer 1

jeden prosty optymalizacje, które mogą być stosowane bez hacking kod całkowicie.

• I * I na każdy prime dostaje bardzo rozrzutny jako lista wydłuża się. Zamiast obliczyć pierwiastek kwadratowy i poza pętlą i test przeciwko tej wartości wewnątrz pętli.

jak kiedykolwiek pierwiastek kwadratowy jest sam w sobie i kosztowne obliczenia, a większość kandydujących numerów zostanie odrzucona jako podzielna przez jedną z niższych liczb pierwszych (3,5,7), więc okazuje się, że nie jest to taka dobra optymalizacja (pesymizacja?). Ale tak naprawdę nie musimy być aż tak dokładni, a prosta kontrola, że ​​prime jest mniejsze niż jedna trzecia wartości, ma podobny efekt bez kosztów obliczeniowych pierwiastków kwadratowych, ale kosztem stosunkowo niewielu niepotrzebnych test.

Answer 2

Można użyć prime sieve iz prostego twist:

1. zdefiniować pierwszy Prime 2, jak to zrobić, należy ustawić największą liczbę osiągnięta (max) 2;
2. Wygeneruj listę n kolejnych numerów od max+1 do max+n;
3. Użyj sita z liczbami głównymi z tej listy. Podczas przesiewania, ustaw początkowy numer dla każdej liczby pierwszej na najmniejszą liczbę na liście, którą można podzielić przez liczbę pierwszą;
4. Jeśli kwota nie jest liczbą reacher, goto 2.

W ten sposób można kontrolować długość listy, a ponieważ długość będzie większa, prędkość będzie większa. Jest to jednak całkowita przeróbka algorytmu i trudniej ją programować.

Oto przykładowy kod, który jest dość surowy, ale to tylko zajmuje mniej niż 70% czasu oryginału:

from math import sqrt 
from time import time 
primes = [2] 
max = 3 
n = input("Number of prime numbers to print: ") 
r=2 
clock = time() 
def sieve(r): 
    global primes 
    global max 
    s = set(range(max,max+r)) 
    for i in primes: 
     b=max//i 
     if (b*i<max): 
      b=b+1 
     b=b*i 
     while b<=max+r-1: 
      if b in s: 
       s.remove(b) 
      b=b+i 
    for i in s: 
     primes.append(i) 
while len(primes) < n: 
    r=primes[-1] 
    sieve(r) 
    max=max+r 
primes=primes[0:n] 
print primes 
clock -= time() 
print "\n", -clock 
raw_input() 

Istnieje wiele sposobów, aby poprawić to, to tylko pokazuje koncepcję podejścia .

Może to również spowodować powiększenie pamięci, gdy liczba jest duża. Użyłem limitu dynamicznego, aby nieco to złagodzić.

A jeśli jesteś naprawdę ciekawy (i nieustraszony), możesz spojrzeć na bardziej skomplikowane implementacje w różnych projektach open source. Jednym z przykładów jest Pari/GP, napisany w C++, który szybko się płonie (testowałem od 1 do 50000000 w mniej niż 1 min, jeśli dobrze pamiętam). Przetłumaczenie ich na Python może być trudne, ale będzie pomocne, może nie tylko dla ciebie ;-)

Answer 3

Dowolna liczba, która kończy się na 5, innych niż 5, nie jest liczbą pierwszą. Tak więc możesz umieścić instrukcję, która pomija każdą liczbę kończącą się na 5, która jest większa niż 5.

Answer 4

Jak już powiedziałem, Ziyao Wei, spróbowałbym także implementacji Sieve. Jedyną rzeczą, którą poprawię, jest użycie Prime number theorem jako punktu początkowego dla używanego rozmiaru.

Obliczanie funkcji odwrotnej nie jest proste w przypadku czystego Pythona, ale podejście iteracyjne powinno być wystarczająco dobre iw ten sposób można uzyskać całkiem niezły pomysł, jak duże musi być sito. Ponieważ tak naprawdę nie pamiętam dokładnie dowodów na twierdzenie i jest 6 rano tutaj, ktoś inny będzie musiał się złożyć, by powiedzieć, czy twierdzenie gwarantuje jakąś górną granicę, która mogłaby zostać wykorzystana do umożliwienia użycia prostego sita bez martwić się o to. Iirc niestety nie jest tak.

Answer 5

Jak już wspomniano, przedstawiony algorytm nie może zostać znacząco poprawiony. Jeśli wymagane jest szybkie rozwiązanie, sito Eratostenes jest odpowiednie. Rozmiar sita x może być estimated przy użyciu n >= x/(ln x + 2), jeśli jest to . To równanie można rozwiązać za pomocą iteracji Newtona. Przedstawiony algorytm jest około 10 razy szybszy od oryginału:

def sieveSize(n): 
    # computes x such that pi(x) >= n (assumes x >= 55) 
    x = 1.5 * n # start 
    y = x - n * math.log(x) - 2 * n 
    while abs(y) > 0.1: 
     derivative = 1 - n/x 
     x = x - y/derivative 
     y = x - n * math.log(x) - 2 * n 
    return int(x) + 1 

def eratosthenes(n): 
    # create a string flags: flags[i]=='1' iff i prime 
    size = sieveSize(n) 
    flags = ['1'] * size # start with: all numbers are prime 
    flags[0] = flags[1] = '0' # 0 and 1 are not primes 
    i = 0 
    while i * i < size: 
     if flags[i] == '1': 
      for j in range(i * i, size, i): 
       flags[j] = '0' 
     i += 1 
    return flags 

def primes(n): 
    flags = eratosthenes(n) 
    prims = [] 
    for i in range(0, len(flags)): 
     if flags[i] == '1': 
      prims.append(i) 
    return prims 

prims = primes(100000)