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 #24 - 25 kwietnia, 18:00, Białystok!
Szukaj Szukaj
Strony: [1]   Do dołu
Drukuj
Wątek: Optymalizacja sita Eratostelesa  (Przeczytany 494 razy)
« : 16:31 18/06/17 »
Guaz Offline
Hello World!

Zobacz profil
*

Reputacja: 10
Płeć: Mężczyzna
Wiadomości: 80


Hej Uśmiech.

W sumie chciałbym się jednocześnie pochwalić, ale też skonfrontować z innymi algorytmami. Bo może ktoś zna jeszcze szybszy algorytm dla dużych liczb gdzie ważna jest pamięć, od tego który udało mi się napisać Uśmiech.
Podsyłam kod:
Kod
def binary_guaz_sieve_primes(n=1000000):
   #__Author_of_sieve__: Maciej 'Guaz' Pawlowski
   #Value to check is between 0 - 16 and 100 - Infinity.
   #Alghoritm must got even number, else will change value +1.
   if n < 16:
       primes = (2, 3, 5, 7, 11, 13);
       return [i for i in primes if i<n];
   elif n < 100: n = 100;
   elif n % 2: n += 1;
   #Declaring variables, methods and sieve
   ap = list.append
   sqn = int(n**0.5)+1; res = [2]
   s = bytearray([0]); s *= n
   for i in range(3, sqn, 2):
       #Choose primes numbers
       if not s[i]:
           #To replace eliminated elements, generate byte list
           repl = bytearray([1]); repl *= int((n-(i*i))/(i+i)+1)
           s[i*i::i+i] = repl
           ap(res, i)
           del repl
   #Return all value between 2 and n variable.
   return res + [i for i in range(sqn, n, 2) if not s[i]]
Jeśli komuś udałoby się znaleźć coś szybszego dla liczb rzędu 10**6/ 10**9. To chętnie się douczę co byłoby bardziej optymalne.
Stworzyłem też klasę do zmiany elementów już podczas generowania listy do zwracania, jednak okazało się to wolniejsze. Osobiście nie widzę sposobu na coś optymalniejszego po sprawdzeniu innych algorytmów z sieci, ale może ktoś mnie zaskoczy Uśmiech.

Choć zastanawiałem się czy numpy nie posiada odpowiednika tablicy bitowej, co pewnie mogłoby przyspieszyć jeszcze trochę algorytm Uśmiech. Ale nie znalazłem niestety.
Zapisane

Python 3.5.2 / Mint
« Odpowiedz #1 : 17:11 18/06/17 »
sig Offline
Professional Python User

Zobacz profil
***

Reputacja: 73
Wiadomości: 323


Wydaje mi się że zamiast liczyć pierwiastek, wydajniej będzie while i * i <= n.
Zapisane
« Odpowiedz #2 : 19:17 18/06/17 »
Guaz Offline
Hello World!

Zobacz profil
*

Reputacja: 10
Płeć: Mężczyzna
Wiadomości: 80


Pierwsze co mi przyszło na myśl, to że pierwiastek i tak będę musiał policzyć bo przecież generuje pozostałe elementy w returnie. Jednak po chwili zastanowienia, (baaaardzo odkrywczo) stwierdziłem że nasz przybliżony "pierwiastek" się sam znajduje dzięki temu warunkowi.
Tak więc zacząłem działać, co doprowadziło do tego że algorytm zwolnił o ~ 3-6% z trzech najlepszych czasów:

Kod
def binary_guaz_sieve_primes(n=10**6):
   #__Author_of_sieve__: Maciej 'Guaz' Pawlowski
   if n < 100:
       primes = (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);
       return [i for i in primes if i<n];
   elif n % 2: n += 1;
   ap = list.append
   res = [2]
   s = bytearray([0])
   s *= n
   i = 3
   while i*i<n:
       if not s[i]:
           repl = bytearray([1])
           repl *= int((n-(i*i))/(i+i)+1)
           s[i*i::i+i] = repl
           ap(res, i)
           del repl
       i += 2
   return res + [g for g in range(i, n, 2) if not s[i]]
 

Szybki wniosek, po jaką cholerę teraz liczę potęgę mojego 'i' w trzech miejscach. W przypadku dwóch miejsc, nie miało to najmniejszego sensu, bo referencja do kolejnego obiektu spowalniała algorytm bardziej niż potęga tego samego, dzięki temu spostrzeżeniu doszedłem do nieco szybszej formy:

Kod
def binary_guaz_sieve_primes(n=10**6):
   #__Author_of_sieve__: Maciej 'Guaz' Pawlowski
   #Value to check higher primes at 100 to infinity.
   if n < 100:
       primes = (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);
       return [i for i in primes if i<n];
   #Declaring variables, methods and sieve
   ap = list.append
   res = [2]
   s = bytearray([0])
   s *= n
   i,j = 3,9
   while j < n:
       #Choose primes numbers
       if not s[i]:
           #To replace eliminated elements, generate byte list
           repl = bytearray([1])
           repl *= int((n-(j))/(i+i)+1)
           s[j::i+i] = repl
           ap(res, i)
           del repl
       i += 2
       j = i*i
   #Return all value between 2 and n variable.
   return res + [g for g in range(i, n, 2) if not s[g]]

Co jest faktycznie szybsze o 4-5%, dzięki za nakierowanie Uśmiech.
Teraz jeszcze bardziej mnie zżera ciekawość, jako że od wcześniejszego nic szybszego w sieci nie znalazłem Chichot.
Zapisane

Python 3.5.2 / Mint
« Odpowiedz #3 : 21:18 18/06/17 »
sig Offline
Professional Python User

Zobacz profil
***

Reputacja: 73
Wiadomości: 323


Masz jakąś górną granicę sprawdzanej liczby? jak tak, to zrobienie listy wszystkich pierwszych mniejszych lub równych jej pierwiastkowi znacznie przyśpieszy prace, bo będziesz sprawdzał dzielenie tylko przez liczby z tejże (naturalnie dopóki dzielnik razy dzielnik nie będzie większy niż sprawdzana liczba) np dla wspomnianego 10^9 były by to liczby pierwsze do 31623
Zapisane
« Odpowiedz #4 : 22:25 18/06/17 »
raydeal Offline
Professional Python User

Zobacz profil
***

Reputacja: 53
Wiadomości: 304


Cytuj
Jeśli komuś udałoby się znaleźć coś szybszego dla liczb rzędu 10**6/ 10**9. To chętnie się douczę co byłoby bardziej optymalne.

@Guaz
Szybszego to znaczy jaką szybkość osiągnąłeś i jak to zmierzyłeś (gdzie)?
Nie wiem czy to widziałeś ale w tym wątku było trochę na ten temat.
Zapisane
« Odpowiedz #5 : 23:02 18/06/17 »
sig Offline
Professional Python User

Zobacz profil
***

Reputacja: 73
Wiadomości: 323


W tamtym wątku był program liczący pierwsze do określonej liczby (100000) , a to zupełnie inny algorytm. Napisałem kod na bazie tego co go tam dałem (tyle że dodawał nowe pierwsze do tablicy) i polecenie time pokazuje mi że wolniejszy od tego co jest w tym wątku. 
Zapisane
« Odpowiedz #6 : 00:40 19/06/17 »
Guaz Offline
Hello World!

Zobacz profil
*

Reputacja: 10
Płeć: Mężczyzna
Wiadomości: 80


@sig
Zrobiłem generator liczb pierwszych wykorzystując te zasadę, jednak jego prędkość była tak mizerna, że na samym początku odrzuciłem te możliwość Uśmiech.
Niemniej jednak by nie mówić o czymś z kosmosu, przytoczę kod:
Kod:
def prime_gen(to_num):
    if to_num < 2: return None;
    if to_num < 3:
        yield 2;
        return None;
    yield 2; yield 3;
    list_primes = [3]; num_sqrt = int(to_num**0.5)
    for i in range(5, to_num+1, 2):
        for j in list_primes:
            if i%j > 0:
                if j+1 > list_primes[-1]:
                    yield i;
                    if j < num_sqrt: list_primes+=[i];
                    break
                else:
                    continue
            break
Nawet nie optymalizowałem, po prostu wyszło spod palcy. Na zasadzie podzielności nie opłaca się badać czegokolwiek, bo dopóki nie napiszesz swojej klasy która dzielenie będzie wykonywać bitowo, w sposób który zwróci False widząc że wynik będzie po przecinku (w try, niestety, bo to zawsze wygeneruje błąd). To nie ma się nawet co bawić. Zaś zrobienie uniwersalnej metody, to dziesiątki linii kodu, wolę krótkie Uśmiech.

@raydeal
Badałem przez timeit, z poziomu konsoli importując moduł.
Najmniejsza osiągnięta (na moim sprzęcie) prędkość dla tego algorytmu:
10**6 : 0.02855
10**7 : 0.2815
10**8 : 3.7617
10**9 : 44.43333
Najmniejsza spośród 100 prób puszczonych przez noc.
Dla porównania podrzucę algorytm najbardziej primitywny jaki zrobiłem:
Kod
def primitive_primes(n):
   tab = [i for i in range(n)]
   for index in range(2, n):
       if tab[index] > 1:
           i = 2
           while index*i < n:
               tab[index*i] = 0
               i+=1
   return [i for i in range(2, n) if tab[i] > 1]
10**6 : 0.86415
10**7 : 9.28742
10**8 : 157.64225
10**9 : -Brak danych-
Brakło mi nocy aby chociaż jedna próba się wykonała dla 10**9.
Defakto algorytm jest ~20 krotnie szybszy od najbardziej primitywnego, jakieś 15-30% szybszy od najszybszych w pythonie jakie znalazłem w sieci ;p. Pomijam te które źle liczyły.

W badaniach mi pomógł program napisany w pythonie który testował, spisywał wyniki, a później analizował wyjście żeby zwrócić mi wyniki w ładnej formie ;P.

Jeśli to kogoś interesuje, mogę przedstawić całą drogę w postaci wcześniejszych wersji algorytmu, wnioski i próby, aż optymalizacja dotarła do tego punktu. Ostatnio prowadziłem na forum uczelnianym referat o Optymalizacji programów, i to był jeden z elementów Uśmiech.

@Edit:
Dodam tylko że 'Sito Atkina' też wymięka przy sprawdzaniu kolejnych liczb do zakresu 10**9. Dopiero wyższe liczby stanowią problem gdy zaczyna brakować pamięci nawet z tablicą bitową. O ile generator (pętla z yieldem zamiast returna) jeszcze pociągnie zakres 10**10, to zmagazynowanie wszystkich liczb w liście przerasta mój zasób pamięci Uśmiech.
Dla wyższych liczb są potrzebne albo kolosalne zasoby pamięci, albo właśnie Sito Atkina, by wytyczać liczbę która posiada kilkanaście/dziesiąt cyfr.
Zapisane

Python 3.5.2 / Mint
« Odpowiedz #7 : 21:50 19/06/17 »
khonsu Offline
Professional Python User

Zobacz profil
***

Reputacja: 93
Wiadomości: 425


Z tego co pamiętam projecteuler zawiera kilka zadań z liczbami pierwszymi, możesz sobie w sekcji teoretycznej podejrzeć jak ludzie optymalizowali algorytmy odnośnie liczb pierwszych (trochę tego było).
Zapisane

There are 10 kinds of people:
Those who understand binary and those who don't
Strony: [1]   Do góry
Drukuj
Skocz do:  

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