Strona główna Polish Python Coders Group
   Strona główna   Pomoc Zaloguj się Rejestracja  
Witamy, Gość. Zaloguj się lub zarejestruj.
Czy dotarł do Ciebie email aktywacyjny?

Zaloguj się podając nazwę użytkownika, hasło i długość sesji

Aktualności: PyStok #39, 20 marca 18:00, Białystok: AI w diagnostyce obrazowej i metaklasy
Szukaj Szukaj
Strony: [1]   Do dołu
Drukuj
Wątek: generator liczb pierwszych  (Przeczytany 477 razy)
« : 19:56 29/01/19 »
Alabasco Offline
Hello World!

Zobacz profil
*

Reputacja: 0
Wiadomości: 4


 Cześć, jestem samoukiem i próbowałem zrobić generator liczb pierwszych z takim skutkiem ( robiłem to całkowicie sam intuicyjnie). Kończę kursy internetowe ale nie chciałbym skończyć na zwykłym klepaniu.

import time
a = 1

while True:
    a= a +1
    i = 2
    while i<a:
        if a%i != 0:
            if i == a-1:
                print(a)
        else:
            break
        i = i + 1

przy czym nie zadowala mnie szybkość. mojemu procesorowi 3.4 GHz dojscie do 20000 zajmuje ok 8 sec. A po dojsciu do 100000 dramatycznie spowalnia. Macie może jakieś pomysły i polecilibyście mi coś abym przyswajał wiedzę z najlepszych źródeł? Dodam, że jestem studentem I roku inż. chemicznej a programowaniem zainteresowałem się na przekór gdy wykładowca powiedział, że będziemy programować w Matlabie. Dzięki:)
Zapisane
« Odpowiedz #1 : 20:27 30/01/19 »
Guaz Offline
Professional Python User

Zobacz profil
***

Reputacja: 64
Płeć: Mężczyzna
Wiadomości: 467


Niecodzienne podejście, z reguły to takie osoby szukają gotowców po forach Chichot.
Jeśli masz żyłkę do bawienia się w kodowanie, dociekanie godzinami itd. I przejdzie ci przez głowę zmiana kierunku na Informatykę, w moim przypadku bardzo dobrze to wypadło Mrugnięcie.

Ogólnie, masz tu dwa ograniczenia:
) Na początku:
- print, przy szybkich działaniach i częstym wyrzucaniu informacji na ekran, jest 'spowalniaczem' bo terminal obsługuje określoną ilość linii na sekundę i tego nie przeskoczysz. Na początku prędkość wyrzucania liczb pierwszych jest spowolniona przez print.
) Na końcu:
- Robisz dzielenie modulo. Które jest powolne. Przy wielkich liczbach, ono jest wykonywane setki tysięcy razy, co wydłuża czas każdej kolejnej liczby którą wyznaczasz.

Jak możesz to przyspieszyć, kilka opcji:
- Sito euklidesa:
https://pl.wikipedia.org/wiki/Sito_Eratostenesa [To niestety żre sporo pamięci, ale jest dobre do pewnego zakresu]
- Największym możliwym dzielnikiem w przypadku pierwszych (poza nią samą) jest jej ułamek pierwiastek. Dalej nie musisz szukać.
- Z wyjątkiem 2, każda liczba pierwsza jest nieparzysta, więc możesz sprawdzać 3, 5, 7, 9 itd. dalej co drugą liczbę zamiast wszystkie po drodze.

Przykład mojego researchu w tej dziedzinie z którym możesz powalczyć do prędkości sita:
Kod
from time import time as tm
 
###Func section###
def guaz(n=10**6*4):
   if n < 100: return [i for i in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97) if i<n];
   res = [2]; s = bytearray([0]); i = 3; j = 9;
   nxt_i = lambda: i+2; nxt_j = lambda: i*i;
   s *= n
   def mo():
       s[j::i+i] = bytearray([1])*int((n-(j))/(i+i)+1)
       res.append(i)
   while j<n:
       mo() if not s[i] else None
       i = nxt_i(); j = nxt_j();
   return res + [g for g in range(i, n, 2) if not s[g]]
 
###Func to self check length of primes is correctly###
def primesi(n):
   import primesieve
   return primesieve.primes(n)
 
###Test section###
num_to_check = 10**6
 
 
time_start = tm()
test=guaz(num_to_check)
print ("Time to complete funkction guaz (in sec): ", round(tm()-time_start,5), len(test))
del test
 
time_start = tm()
test=primesi(num_to_check)
print ("Time to complete funkction primesi (in sec): ", round(tm()-time_start,5), len(test))
del test

Kod może być przerażający na początek, ale tu nie chodzi o zrozumienie (choć polecam się zagłębiać, mogę podesłać ci też całą historię ewolucji i prób mojego rozwiązania, co będzie prostsze do zrozumienia).

Zapisane

Python 3.5+ / Mint

Daje wędkę zamiast ryby. Chyba że ktoś się chce czegoś nauczyć, wtedy chętnie pomogę każdemu.
Za rybę niestety trzeba zapłacić Z politowaniem.
« Odpowiedz #2 : 00:11 31/01/19 »
sig Offline
Professional Python User

Zobacz profil
***

Reputacja: 88
Wiadomości: 423



- Największym możliwym dzielnikiem w przypadku pierwszych (poza nią samą) jest jej ułamek. Dalej nie musisz szukać.
Raczej pierwiastek, a raczej while i * i <= a (będzie szybsze niż liczenie wspomnianego, chyba że sobie jego część całkowitą szukaniem binarnym wyznaczy)
Zapisane
« Odpowiedz #3 : 04:52 31/01/19 »
Guaz Offline
Professional Python User

Zobacz profil
***

Reputacja: 64
Płeć: Mężczyzna
Wiadomości: 467


Fakt, użyłem złego słowa, dzięki za podkreślenie go @sig.

Tak, przemnożenie jest szybsze, dlatego też go użyłem w swoim rozwiązaniu Uśmiech .

A o szukaniu binarnym części całkowitej pierwiastka w sumie nie słyszałem nigdy. Dzięki za bakcyla, w wolnej chwili muszę poszperać Chichot
Zapisane

Python 3.5+ / Mint

Daje wędkę zamiast ryby. Chyba że ktoś się chce czegoś nauczyć, wtedy chętnie pomogę każdemu.
Za rybę niestety trzeba zapłacić Z politowaniem.
« Odpowiedz #4 : 08:43 31/01/19 »
sig Offline
Professional Python User

Zobacz profil
***

Reputacja: 88
Wiadomości: 423


To od razu przetestuj ten pierwiastek, nie wiem czy ktoś to kiedyś stosował w praktyce (tak mi do głowy swojego czasu przyszło że powinno być szybsze niż mnożenie co liczbę a części ułamkowej w takim programie nie potrzeba).
Zapisane
« Odpowiedz #5 : 12:16 04/02/19 »
Guaz Offline
Professional Python User

Zobacz profil
***

Reputacja: 64
Płeć: Mężczyzna
Wiadomości: 467


Kod
# Python3 program to find floor(sqrt(x) 
 
# Returns floor of square root of x
def floorSqrt(x):
 
   # Base cases
   if (x == 0 or x == 1):
       return x
 
   # Staring from 1, try all numbers until
   # i*i is greater than or equal to x.
   i = 1; result = 1
   while (result <= x):
 
       i += 1
       result = i * i
 
   return i - 1
 
# Driver Code
x = 11
print(floorSqrt(x))
 
# This code is contributed by Smitha Dinesh Semwal.
To jest zwykły kod na pierwiastek całkowity (napisany jak widać w komentarzach przez kogo).
Natomiast do tego specyficznego rozwiązania można go przyspieszyć (iterując od 1 do 10**8 przyspiesza jakieś ~42%).
W taki banalny sposób sposób:
Kod
def floorSqrt(x): 
 
   if (x == 0 or x == 1):
       return x
   elif (x > 999999):
       i = 10000; result = 1000000
   elif (x > 9999):
       i = 100; result = 10000
   elif (x > 99):
       i = 10; result = 100
   else:
       i = 2; result = 4
   while (result <= x):
 
       i += 1
       result = i * i
 
   return i - 1

Niestety nadal sprawdza się dużo wolniej od mnożenia, więc sprawdzamy wyszukiwaniem binarnym:

Kod
 
# Python 3 program to find floor(sqrt(x)
 
# Returns floor of square root of x          
def floorSqrt(x) :
 
   # Base cases
   if (x == 0 or x == 1) :
       return x
 
   # Do Binary Search for floor(sqrt(x))
   start = 1
   end = x    
   while (start <= end) :
       mid = (start + end) // 2
 
       # If x is a perfect square
       if (mid*mid == x) :
           return mid
 
       # Since we need floor, we update  
       # answer when mid*mid is smaller
       # than x, and move closer to sqrt(x)
       if (mid * mid < x) :
           start = mid + 1
           ans = mid
 
       else :
           # If mid*mid is greater than x
           end = mid-1
 
   return ans
 
# driver code    
x = 11
print(floorSqrt(x))
 
# This code is contributed by Nikita Tiwari.

Jednak jak widać po programie, w nim również występuje mnożenie, oraz dzielenie przez dwa, defakto nie robione operacjami bitowymi. I nadal się sprawdza gorzej, więc postanowiłem je również poprawić pod ten specyficzny problem:
(- Zbliżonym zakresem + przesunięciem bitowym + ograniczeniem operacji mnożenia) [Jakieś ~ 17 % szybciej dla tego rozwiązania]
Kod
def floorSqrt(x): 
   if (x == 0 or x == 1) :
       return x
   elif (x > 999999 and x < 1000000000000):
       start = 10000; end = 1000000
   elif (x > 9999):
       start = 100; end = 10000
   elif (x > 99):
       start = 10; end = 100
   else:
       start = 1; end = x
   while (start <= end) :
       mid = ((start + end)>>1)
       mid_pow = mid*mid
       if (mid_pow == x) :
           return mid
       if (mid_pow < x) :
           start = mid + 1
           ans = mid
       else :
           end = mid-1
   return ans

Jednak wszystkie cztery, z racji tego że nadal jest to szukanie pierwiastka zawierające m.in. mnożenie, nie jest szybsze od tego trywianego i*i.

Dodam jeszcze że spróbowałem to też zrobić za pomocą ciągu rekurencyjnego... (a1 = a0 + x)
Bo wyznaczanie kolejnych potęg gdy mamy jej pierwiastek w takiej iteracji:
i = 3 -> 5 -> 7 -> 9 -> ... ; j = 9 -> 25 -> 49 -> 81 -> ...;
Można przedstawić tak:
j += i+i+i+i+4; i += 2 ;
Lub tak:
j += (i+1)*4 ; i += 2 ;
Ewentualnie:
i += 2 ; j += (i-1)*4 ;
W ostateczności też tak:
i += 1 ; j += i*4 ; i += 1 ;

Jednak wszystkie powyższe również są wolniejsze od 'tradycyjnego':
i += 2 ; j = i*i ;

Powód jest prosty. W moim programie i tak 'j' będzie potrzebne do wyznaczania fragmentu listy i obliczaniu jej długości, więc tak czy inaczej będzie obliczane, chyba że pierwiastek miałby zostać użyty znacznie rzadziej niż mnożenie, wtedy jak najbardziej może to mieć swój sens Chichot

Więc z tym wiele chyba się nie naczaruje, chyba że ktoś widzi abym coś przeoczył Uśmiech
Zapisane

Python 3.5+ / Mint

Daje wędkę zamiast ryby. Chyba że ktoś się chce czegoś nauczyć, wtedy chętnie pomogę każdemu.
Za rybę niestety trzeba zapłacić Z politowaniem.
« Odpowiedz #6 : 18:55 04/02/19 »
sig Offline
Professional Python User

Zobacz profil
***

Reputacja: 88
Wiadomości: 423


Wyglada na to że faktycznie binarnie wolniej. Oto mój kod, na 7-dmioletnim laptopie z corei3 330m (2.13 MHz) dolicza do miliona w 10s jak wypisuje każdą, w 7 jak tylko tablice na końcu.pass dodałem bo był potrzebny do testów bez wypisywania każdej.
Kod
tab = [2, 3, 5]
 
def czypierwszat(liczba):
       licznik = 0
       while tab[licznik] * tab[licznik] <= liczba:
           if liczba % tab[licznik] == 0:
               return False
           licznik += 1
       tab.append(liczba)
       return True
 
 
for i in range(6, 1000000):
   if czypierwszat(i) is True:
       print(i)
       pass
print(tab)
 
 
Zapisane
« Odpowiedz #7 : 23:55 04/02/19 »
Guaz Offline
Professional Python User

Zobacz profil
***

Reputacja: 64
Płeć: Mężczyzna
Wiadomości: 467


Modulo też jest niestety bardzo wolne. W dodatku sprawdzasz zarówno parzyste jak i nieparzyste. Co więcej, przy modulo nawet opłaca się zrobić generator który na przemian zwraca (2, 4) [z powodu 2 i 3] skoro 2, 3 i 5 wypisujesz ze startu. Najszybciej działające rozwiązanie z modulo jakie udało mi się stworzyć:
[To drugie, bo dla testów twoje wkleiłem na początek]
Kod
from time import time as tm
 
def czypierwszat(liczba):
   licznik = 0
   while L[licznik] * L[licznik] <= liczba:
       if liczba % L[licznik] == 0:
           return False
       licznik += 1
   L.append(liczba)
   return True
 
###/ Inkrementor Modulo for Generate Primes \###
class Inkrementor():
   inkr = (2,4)
   idx = 0
   def __next__(self):
       if self.idx:
           self.idx-=1
           return self.inkr[self.idx]
       else:
           self.idx+=1
           return self.inkr[self.idx]
 
def zwroc_pierwsze(n):
   yield from (i for i in (2, 3, 5) if i < n)
   i = 7
   it = Inkrementor()
   while i < n:
       idx = 0
       while L[idx] * L[idx] <= i:
           if not (i % L[idx]):
               break
           idx += 1
       else:
           L.append(i)
           yield i
       i += next(it)
###\ Inkrementor Modulo for Generate Primes /###
 
class Generator_Pierwszych():
   class Inkrement():
       inkr = (2,4)
       idx = 1
       def __next__(self):
           if self.idx:
               self.idx-=1
               return self.inkr[self.idx]
           else:
               self.idx+=1
               return self.inkr[self.idx]
 
 
   def __init__(self, n):
       self.n = n #Zakres iteratora
       self.pierwsze = [2, 3] #Startowy zakres
       self.i = 2 #Sprawdzająca
       self.Inkr = self.Inkrement()
 
   def __iter__(self):
       return self
 
   def __next__(self):
       ###/ Begin block \###
       if self.i < 5:
           i = self.i
           idx = self.pierwsze.index(i)+1
           if idx < len(self.pierwsze):
               self.i = self.pierwsze[idx]
           else:
               self.i = 5
           if i < self.n:
               return i
           raise StopIteration
       ###\ Begin block /###
 
       ###/ True iteration block \###
       while self.i < self.n:
           idx = 1
           while self.pierwsze[idx]*self.pierwsze[idx] <= self.i:
               if not (self.i % self.pierwsze[idx]):
                   break
               idx += 1
           else: #Ten else się wykona tylko gdy wystąpi break
               self.pierwsze.append(self.i)
               self.i += next(self.Inkr)
               return self.pierwsze[-1]
           self.i += next(self.Inkr)
       raise StopIteration
 
N = 100**2
#~ N = 100
 
time_start = tm()
L = [2, 3, 5]
for i in range(6, N):
   if czypierwszat(i) is True:
       pass
print ("Time to complete function sig (in sec): ", round(tm()-time_start,5), len(L))
 
L = [2, 3, 5]
time_start = tm()
for i in zwroc_pierwsze(N):
   pass
print ("Time to complete function guaz_func (in sec): ", round(tm()-time_start,5), len(L))
 
del(L)
it = Generator_Pierwszych(N)
time_start = tm()
for i in it:
   pass
print ("Time to complete function guaz_class (in sec): ", round(tm()-time_start,5), len(it.pierwsze))
 

Z klasą mnie teraz natchnęło aby spróbować stworzyć z tego iterator, chociaż nie wykorzystałem pełnego potencjału, ale już mi się nie chce, i tak jest zbliżone ;d.
[Klasowe rozwiązanie jest bardzo podobne w prędkości do twojego]
Kod
5 uruchomień:
Time to complete function sig (in sec):  0.01496 1229
Time to complete function guaz_func (in sec):  0.00849 1229
Time to complete function guaz_class (in sec):  0.01184 1229
 
Time to complete function sig (in sec):  0.01018 1229
Time to complete function guaz_func (in sec):  0.00884 1229
Time to complete function guaz_class (in sec):  0.01209 1229
 
Time to complete function sig (in sec):  0.00958 1229
Time to complete function guaz_func (in sec):  0.00718 1229
Time to complete function guaz_class (in sec):  0.01142 1229
 
Time to complete function sig (in sec):  0.0103 1229
Time to complete function guaz_func (in sec):  0.0073 1229
Time to complete function guaz_class (in sec):  0.01279 1229
 
Time to complete function sig (in sec):  0.0098 1229
Time to complete function guaz_func (in sec):  0.00718 1229
Time to complete function guaz_class (in sec):  0.01287 1229
 
Time to complete function sig (in sec):  0.01003 1229
Time to complete function guaz_func (in sec):  0.00731 1229
Time to complete function guaz_class (in sec):  0.0116 1229
 
W pierwszym się pojawiła najpewniej jakaś anomalia bo znacząco odstawał. Pewnie przy większej ilości prób by to zanikło w średniej, też ciężko powiedzieć.

Na przykładzie tysiąca uruchomień:
Kod
Time to complete function sig (in sec):  10.19973 1229
Time to complete function guaz_func (in sec):  7.56668 1229
Time to complete function guaz_class (in sec):  12.3783 1229

A to na przykładzie 10**6:
Kod
Time to complete function sig (in sec):  2.89004 78498
Time to complete function guaz_func (in sec):  2.49015 78498
Time to complete function guaz_class (in sec):  3.71913 78498
Dla porównania, sito wklejone wyżej, jest nieporównywalnie lepsze [dla 10**6 jak wyżej]:
Kod:
Time to complete function guaz (in sec):  0.0277 78498

A wykorzystując biblioteki zewnętrzne, jak numpy, da się to zrobić jeszcze dużo szybciej:
Kod
 Time to complete function guaz_numpy (in sec):  0.00446 78498
dla kodu:
 
import numpy
def siev_np_guaz(n):
   sieve = numpy.ones(n + 1, dtype=numpy.bool)
   i = 7; j = 49; it = Inkrementor()
   sieve[0:2] = 0; sieve[4::2] = 0; sieve[9::6] = 0; sieve[25::10] = 0
   while j<n:
       if sieve[i]:
           sieve[j::i+i] = 0
       i += next(it); j = i*i;
   return numpy.nonzero(sieve)[0]

@EDIT2: Wpadłem w sumie jeszcze na pomysł z drobnym polepszeniem tego wyniku:
Kod
def siev_np_guaz2(n):
   def inkrementor():
       inkr = (4,2,4,2,4,6,2,6)
       while True:
           yield from inkr
   sieve = numpy.ones(n + 1, dtype=numpy.bool)
   i = 7; j = 49; i2 = 14; it = inkrementor()
   sieve[0:2] = 0; sieve[4::2] = 0; sieve[9::6] = 0; sieve[25::10] = 0
   while j<n:
       if sieve[i]:
           sieve[j::i2] = 0
       i += next(it); j = i*i; i2 = i+i
   return numpy.nonzero(sieve)[0]

Przyrównując dwa ostatnie dla 10**8 * 4 [Na tyle RAM'u posiadam by to pierwsze, nie napisane w numpy nie zamuliło]
Kod
Time to complete function guaz_numpy (in sec):  2.84038 21336326
Time to complete function guaz (in sec):  11.36622 21336326
I z czasem podejrzewam że byłoby jeszcze szybsze, przykładowo już sam numpy dla 10**9*3:
Kod
Time to complete function guaz_numpy (in sec):  25.52741 144449537
No i przestałem się w to bawić, ale zachęcam do podmienienia Iteratora (Inkrementor) na wyznaczanie kolejnych liczb w sposób rekurencyjny z 'pod-sita' co również pozwoli na zastosowanie wątków. Po optymalizacji tego można tym sprawdzać względnie pierwsze. I zaoszczędzić masę pamięci. Sposób z modulo też tu miałby swoje zastosowanie. Do tego jakby odpowiednio odcinać z sita już wyznaczone liczby pierwsze oraz fragmenty sita które nie zostaną użyte, też zużycie pamięci by się zmniejszyło. Kolejnym sposobem jest plik binarny reprezentujący sito, ma to swoją wadę jeśli nie używamy pamięci szybko dostępowej jak RAM czy choćby jeszcze szybszej w procesorze, kolejna rzecz do przetestowania z SSD bo na HDD nawet nie ma co testować Uśmiech.

Ogólnie możliwości jest mnóstwo na polepszenie tego, minusem jest że trzeba by do tego sporo czasu wysiedzieć.
Koniec końców, może gdyby to zechciał ktoś dopracować, mógłby nawet na tym skorzystać przy dobrej maszynie obliczeniowej.

Ale progiem wejściowym w świat 'wyznacznia liczb pierwszych' to według mnie wymaga względnie osiągnięcie pierwszych 10**300 na sprzęcie domowym. Bo jak ostatnio patrzyłem jakiś czas temu, ostatnio odkryta liczba pierwsza miała kilkaset milionów cyfr sama w sobie - więc próg wejścia jest ogromny ;>.
[Dla ciekawych nagrody i to za jaką liczbę: https://www.eff.org/awards/coop ]

A osiągając te 10**10 jesteśmy w stanie wyznaczyć używając tego sita [bez zużywania dodatkowej pamięci] choćby sposobem z modulo, dopiero niemalże 10**100 (Niemalże ponieważ potęga ostatniej liczby pierwszej w zasięgu 10**10 wyznacza nam granicę poprawności) jedyne co, to trzeba by skorzystać z wyniku tego sita i nie dodawać już więcej do jego pamięci.

Rekordem u mnie było 10**13 w godzinę, ale jak pisałem wyżej, na takie zabawy trzeba więcej czasu Uśmiech

Oczywiście wszystkie wyniki bez wypisywania, bo print jest tu najwolniejszą funkcją.
@Edit:
Inkrementor też można spokojnie zmodyfikować na wykluczanie sprawdzania 2*3*5 a może nawet 2*3*5*7 (raczej niewarto), niestety nie sprawdzałem niestety w którym miejscu taki inkrementor by osiągnął limit swojego przyspieszenia / zużycia pamięci.
Dla przykładu 2*3*5, zaczynając od 7 już wymaga takiego schematu:
    inkr = (4,2,4,2,4,6,2,6)

@Edit3:
Niestety z różnicy kolejnych liczb pierwszych jakbyśmy chcieli zacząć od 11 przy schemacie 2*3*5*7, nie wynika żaden wzorzec dla liczb pierwszych w zakresie 100 tyś, chyba że zrobiłem błąd w progamie który to sprawdzał, dla zainteresowanych mogę podesłać na PW czy nie zrobiłem błędu Chichot

I będzie się to dość szybko rozrastać, dla szukania wielkich liczb to jeszcze by mogło mieć sens, chociaż tam i tak dominowałoby znacząco sito, inkrementor byłby jedynie dodatkiem. Dopiero na podstawie sita mogłoby się wyznaczać rozmiar sita ** 2 na podstawie modulo przy zapchaniu całej pamięci. Ale do takich zabaw i tak python nie jest najlepszym językiem jeśli nie stosuje się zewnętrznych bibliotek + dobrze byłoby spróbować JIT'a.
Zapisane

Python 3.5+ / Mint

Daje wędkę zamiast ryby. Chyba że ktoś się chce czegoś nauczyć, wtedy chętnie pomogę każdemu.
Za rybę niestety trzeba zapłacić Z politowaniem.
Strony: [1]   Do góry
Drukuj
Skocz do:  

© 2007 - 2019 Polish Python Coders Group
Powered by SMF 1.1.21 | SMF © 2006-2009, Simple Machines | Theme by PixelSlot