Przyspieszyć bitstring / operacje bitowe w Pythonie?
Napisałem generator liczb pierwszych używając Sita Eratostenesa i Pythona 3.1. Kod działa poprawnie i z wdziękiem W 0.32 sekundy na ideone.com Aby wygenerować liczby pierwsze do 1,000,000.
# from bitstring import BitString
def prime_numbers(limit=1000000):
'''Prime number generator. Yields the series
2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...
using Sieve of Eratosthenes.
'''
yield 2
sub_limit = int(limit**0.5)
flags = [False, False] + [True] * (limit - 2)
# flags = BitString(limit)
# Step through all the odd numbers
for i in range(3, limit, 2):
if flags[i] is False:
# if flags[i] is True:
continue
yield i
# Exclude further multiples of the current prime number
if i <= sub_limit:
for j in range(i*3, limit, i<<1):
flags[j] = False
# flags[j] = True
flags = [False, False] + [True] * (limit - 2)
MemoryError
Jak można sobie wyobrazić, przydzielanie 1 miliarda wartości logicznych ( 1 bajt 4 lub 8 bajtów (patrz komentarz) każdy w Pythonie) jest naprawdę niewykonalne, więc spojrzałem do bitstring . Pomyślałem, że użycie 1 bitu dla każdej flagi będzie znacznie bardziej wydajne w pamięci. Jednak wydajność programu spadła drastycznie - czas trwania 24 sekund, dla liczby pierwszej do 1 000 000. Jest to prawdopodobnie spowodowane wewnętrzną implementacją bitstring.
Możesz skomentować / odkomentować trzy linie, aby zobaczyć, co zmieniłem, aby użyć BitString, jak urywek kodu powyżej.
Moje pytanie brzmi: czy istnieje sposób na przyspieszenie mojego programu, Z czy bez bitstring?Edit: proszę przetestować kod samodzielnie przed wysłaniem. Nie mogę zaakceptować odpowiedzi, które działają wolniej niż mój istniejący kod, oczywiście.
Edit again:
11 answers
Istnieje kilka małych optymalizacji dla twojej wersji. Odwracając role prawdy i fałszu, możesz zmienić "if flags[i] is False: " na " if flags[i]:". A wartością początkową dla drugiej instrukcji range może być i*i zamiast i*3. Twoja Oryginalna wersja trwa 0.166 sekund na moim systemie. Z tymi zmianami, Wersja poniżej trwa 0.156 sekund na moim systemie.
def prime_numbers(limit=1000000):
'''Prime number generator. Yields the series
2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...
using Sieve of Eratosthenes.
'''
yield 2
sub_limit = int(limit**0.5)
flags = [True, True] + [False] * (limit - 2)
# Step through all the odd numbers
for i in range(3, limit, 2):
if flags[i]:
continue
yield i
# Exclude further multiples of the current prime number
if i <= sub_limit:
for j in range(i*i, limit, i<<1):
flags[j] = True
Przechodząc do świata rozszerzeń C, użyłem wersja rozwojowa gmpy . (Zastrzeżenie: jestem jednym z opiekunów.) Wersja rozwojowa nosi nazwę gmpy2 i obsługuje zmienną liczbę całkowitą o nazwie xmpz. Używając gmpy2 i poniższego kodu, mam czas działania 0.140 sekund. Czas trwania limitu 1,000,000,000 wynosi 158 sekund.
import gmpy2
def prime_numbers(limit=1000000):
'''Prime number generator. Yields the series
2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...
using Sieve of Eratosthenes.
'''
yield 2
sub_limit = int(limit**0.5)
# Actual number is 2*bit_position + 1.
oddnums = gmpy2.xmpz(1)
current = 0
while True:
current += 1
current = oddnums.bit_scan0(current)
prime = 2 * current + 1
if prime > limit:
break
yield prime
# Exclude further multiples of the current prime number
if prime <= sub_limit:
for j in range(2*current*(current+1), limit>>1, prime):
oddnums.bit_set(j)
Naciskając optymalizacje i poświęcając jasność, uzyskuję czasy działania 0.107 i 123 sekund z następującym kodem:
import gmpy2
def prime_numbers(limit=1000000):
'''Prime number generator. Yields the series
2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...
using Sieve of Eratosthenes.
'''
yield 2
sub_limit = int(limit**0.5)
# Actual number is 2*bit_position + 1.
oddnums = gmpy2.xmpz(1)
f_set = oddnums.bit_set
f_scan0 = oddnums.bit_scan0
current = 0
while True:
current += 1
current = f_scan0(current)
prime = 2 * current + 1
if prime > limit:
break
yield prime
# Exclude further multiples of the current prime number
if prime <= sub_limit:
list(map(f_set,range(2*current*(current+1), limit>>1, prime)))
Edit: na podstawie tego ćwiczenia zmodyfikowałem gmpy2 do przyjęcia xmpz.bit_set(iterator). Używając poniższego kodu, czas uruchomienia wszystkich liczb pierwszych mniejszy niż 1,000,000,000 wynosi 56 sekund dla Pythona 2.7 i 74 sekundy dla Pythona 3.2. (Jak zaznaczono w komentarzach, xrange jest szybszy niż range.)
import gmpy2
try:
range = xrange
except NameError:
pass
def prime_numbers(limit=1000000):
'''Prime number generator. Yields the series
2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...
using Sieve of Eratosthenes.
'''
yield 2
sub_limit = int(limit**0.5)
oddnums = gmpy2.xmpz(1)
f_scan0 = oddnums.bit_scan0
current = 0
while True:
current += 1
current = f_scan0(current)
prime = 2 * current + 1
if prime > limit:
break
yield prime
if prime <= sub_limit:
oddnums.bit_set(iter(range(2*current*(current+1), limit>>1, prime)))
Edit # 2: Jeszcze jedna próba! Zmodyfikowałem gmpy2, aby zaakceptować xmpz.bit_set(slice). Używając poniższego kodu, czas uruchomienia wszystkich liczb pierwszych mniejszy niż 1,000,000,000 wynosi około 40 sekund zarówno dla Pythona 2.7, jak i Pythona 3.2.
from __future__ import print_function
import time
import gmpy2
def prime_numbers(limit=1000000):
'''Prime number generator. Yields the series
2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...
using Sieve of Eratosthenes.
'''
yield 2
sub_limit = int(limit**0.5)
flags = gmpy2.xmpz(1)
# pre-allocate the total length
flags.bit_set((limit>>1)+1)
f_scan0 = flags.bit_scan0
current = 0
while True:
current += 1
current = f_scan0(current)
prime = 2 * current + 1
if prime > limit:
break
yield prime
if prime <= sub_limit:
flags.bit_set(slice(2*current*(current+1), limit>>1, prime))
start = time.time()
result = list(prime_numbers(1000000000))
print(time.time() - start)
Edit # 3: zaktualizowałem gmpy2, aby poprawnie obsługiwać krojenie na poziomie bitowym xmpz. Bez zmian w wydajności, ale dużo ładny API. Zrobiłem małe poprawki i mam czas do około 37 sekund. (Patrz Edycja # 4 do zmian w gmpy2 2.0. 0B1.)
from __future__ import print_function
import time
import gmpy2
def prime_numbers(limit=1000000):
'''Prime number generator. Yields the series
2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...
using Sieve of Eratosthenes.
'''
sub_limit = int(limit**0.5)
flags = gmpy2.xmpz(1)
flags[(limit>>1)+1] = True
f_scan0 = flags.bit_scan0
current = 0
prime = 2
while prime <= sub_limit:
yield prime
current += 1
current = f_scan0(current)
prime = 2 * current + 1
flags[2*current*(current+1):limit>>1:prime] = True
while prime <= limit:
yield prime
current += 1
current = f_scan0(current)
prime = 2 * current + 1
start = time.time()
result = list(prime_numbers(1000000000))
print(time.time() - start)
Edit # 4: wprowadziłem kilka zmian w gmpy2 2.0. 0B1, które łamią poprzedni przykład. gmpy2 nie traktuje już True jako specjalnej wartości, która zapewnia nieskończone źródło 1-bitów. -1 należy użyć zamiast tego.
from __future__ import print_function
import time
import gmpy2
def prime_numbers(limit=1000000):
'''Prime number generator. Yields the series
2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...
using Sieve of Eratosthenes.
'''
sub_limit = int(limit**0.5)
flags = gmpy2.xmpz(1)
flags[(limit>>1)+1] = 1
f_scan0 = flags.bit_scan0
current = 0
prime = 2
while prime <= sub_limit:
yield prime
current += 1
current = f_scan0(current)
prime = 2 * current + 1
flags[2*current*(current+1):limit>>1:prime] = -1
while prime <= limit:
yield prime
current += 1
current = f_scan0(current)
prime = 2 * current + 1
start = time.time()
result = list(prime_numbers(1000000000))
print(time.time() - start)
Edit # 5: wprowadziłem kilka ulepszeń do gmpy2 2.0. 0B2. Możesz teraz powtarzaj wszystkie bity, które są albo ustawione, albo wyczyszczone. Czas pracy poprawił się o ~30%.
from __future__ import print_function
import time
import gmpy2
def sieve(limit=1000000):
'''Returns a generator that yields the prime numbers up to limit.'''
# Increment by 1 to account for the fact that slices do not include
# the last index value but we do want to include the last value for
# calculating a list of primes.
sieve_limit = gmpy2.isqrt(limit) + 1
limit += 1
# Mark bit positions 0 and 1 as not prime.
bitmap = gmpy2.xmpz(3)
# Process 2 separately. This allows us to use p+p for the step size
# when sieving the remaining primes.
bitmap[4 : limit : 2] = -1
# Sieve the remaining primes.
for p in bitmap.iter_clear(3, sieve_limit):
bitmap[p*p : limit : p+p] = -1
return bitmap.iter_clear(2, limit)
if __name__ == "__main__":
start = time.time()
result = list(sieve(1000000000))
print(time.time() - start)
print(len(result))
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-10-12 06:05:07
Okay, oto (prawie kompletny) kompleksowy benchmarking zrobiłem dziś wieczorem, aby zobaczyć, który kod działa najszybciej. Mam nadzieję, że ktoś uzna tę listę za przydatną. Pominąłem wszystko, co zajmuje więcej niż 30 sekund, aby zakończyć na mojej maszynie.
Chciałbym podziękować wszystkim, którzy wnieśli wkład. Dzięki twoim wysiłkom zdobyłem wiele wglądu i mam nadzieję, że ty też.
Moja maszyna: AMD zm-86, Dwurdzeniowy 2,40 Ghz, z 4GB PAMIĘCI RAM. To jest laptop HP TouchSmart Tx2. Zauważ, że chociaż mogłem połączyć się z pastebinem, porównałem wszystkie poniższe na mojej własnej maszynie.
Dodam benchmark gmpy2, gdy tylko będę w stanie go zbudować.
Wszystkie benchmarki są testowane w Pythonie 2.6 x86
Zwracanie listy liczb pierwszych n do 1 000 000: (Using Python Generatory)
Sebastian ' s numpy generator version (updated) - 121 ms @
Sito Marka + koło - 154 ms
Wersja Roberta z krojeniem - 159 ms
Moja ulepszona wersja z krojeniem]} - 205 ms
Generator Numpy z wyliczaniem - 249 ms @
Sito podstawowe Marka - 317 ms
Poprawa Casevh na moim oryginale rozwiązanie - 343 ms
Moje zmodyfikowane rozwiązanie generatora numpy - 407 ms
Moja oryginalna metoda w pytanie - 409 ms
Rozwiązanie Bitarray - 414 ms @
Czysty Python z bytearray - 1394 ms @
Scott ' s BitString solution - 6659 ms @
'@' oznacza, że metoda ta jest zdolna do generowania do n
Ponadto, jeśli nie potrzebujesz generator i po prostu chcę całą listę od razu:
Rozwiązanie Numpy z RosettaCode - 32 ms @
(The rozwiązanie numpy jest również w stanie wygenerować do 1 miliarda, co zajęło 61,6259 sekund. Podejrzewam, że pamięć została zamieniona raz, stąd ten podwójny czas.)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-23 12:02:48
OK, to jest moja druga odpowiedź, ale ponieważ szybkość jest najważniejsza, pomyślałem, że muszę wspomnieć o module bitarray - mimo że jest to nemezis bitstring:). Idealnie nadaje się do tego przypadku, ponieważ nie tylko jest to rozszerzenie C (a więc szybsze niż czysty Python ma nadzieję być), ale także obsługuje przypisania slice. Jednak nie jest jeszcze Dostępny dla Pythona 3.
Nawet nie próbowałem tego zoptymalizować, po prostu przepisałem wersję bitstring. Na mojej maszynie dostaję 0.16 sekundy dla liczb pierwszych poniżej miliona.
Za miliard, działa idealnie i kończy się w 2 minuty i 31 sekund.import bitarray
def prime_bitarray(limit=1000000):
yield 2
flags = bitarray.bitarray(limit)
flags.setall(False)
sub_limit = int(limit**0.5)
for i in xrange(3, limit, 2):
if not flags[i]:
yield i
if i <= sub_limit:
flags[3*i:limit:i*2] = True
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-02-07 15:12:11
Powiązane pytanie.
najszybszy sposób na wyświetlenie wszystkich liczb pierwszych poniżej N w Pythonie
Cześć, ja też szukam kodu w Pythonie, aby wygenerować liczby pierwsze do 10 9 tak szybko, jak Mogę, co jest trudne ze względu na problem z pamięcią. do tej pory wymyśliłem to, aby wygenerować primes do 106 & 10*7 (0,171 s & 1764 s W moim starym komputerze), który wydaje się być nieco szybszy(przynajmniej w moim komputerze) niż "moja ulepszona wersja z krojeniem" z poprzedniego posta, prawdopodobnie ponieważ używam n / / i-i +1 (patrz niżej)zamiast analogicznego len(flags[I2:: i
def primes(n):
""" Returns a list of primes < n """
sieve = [True] * n
for i in xrange(3,int(n**0.5)+1,2):
if sieve[i]:
sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
return [2] + [i for i in xrange(3,n,2) if sieve[i]]
W Jednym ze swoich kodów Xavier używa FLAG[i2:: ii..n mamy(n-ii)//2*i wielokrotności 2*i ponieważ chcemy policzyć ii również sumujemy 1 tak len (sito[ii::2*i]) equal (n-I * i) / / (2*i) + 1 to make kod szybciej. Podstawowym generatorem opartym na powyższym kodzie byłoby:
def primesgen(n):
""" Generates all primes <= n """
sieve = [True] * n
yield 2
for i in xrange(3,int(n**0.5)+1,2):
if sieve[i]:
yield i
sieve[i*i::2*i] = [False]*((n-i*i-1)/(2*i)+1)
for i in xrange(i+2,n,2):
if sieve[i]: yield i
Z odrobiną modyfikacji można napisać nieco wolniejszą wersję powyższego kodu, która zaczyna się od sieve o połowę wielkości sieve = [True] * (n / / 2) i działa dla tej samej N. Nie wiem, jak to odzwierciedlają w problemie z pamięcią. Jako przykład realizacji tutaj jest zmodyfikowana wersja kodu numpy rosetta (może szybsza) zaczynająca się od Sita o połowę większego.
import numpy
def primesfrom3to(n):
""" Returns a array of primes, 3 <= p < n """
sieve = numpy.ones(n/2, dtype=numpy.bool)
for i in xrange(3,int(n**0.5)+1,2):
if sieve[i/2]: sieve[i*i/2::i] = False
return 2*numpy.nonzero(sieve)[0][1::]+1
A Faster & more generator pamięci byłby:
import numpy
def primesgen1(n):
""" Input n>=6, Generates all primes < n """
sieve1 = numpy.ones(n/6+1, dtype=numpy.bool)
sieve5 = numpy.ones(n/6 , dtype=numpy.bool)
sieve1[0] = False
yield 2; yield 3;
for i in xrange(int(n**0.5)/6+1):
if sieve1[i]:
k=6*i+1; yield k;
sieve1[ ((k*k)/6) ::k] = False
sieve5[(k*k+4*k)/6::k] = False
if sieve5[i]:
k=6*i+5; yield k;
sieve1[ ((k*k)/6) ::k] = False
sieve5[(k*k+2*k)/6::k] = False
for i in xrange(i+1,n/6):
if sieve1[i]: yield 6*i+1
if sieve5[i]: yield 6*i+5
if n%6 > 1:
if sieve1[i+1]: yield 6*(i+1)+1
Lub z nieco większym kodem:
import numpy
def primesgen(n):
""" Input n>=30, Generates all primes < n """
size = n/30 + 1
sieve01 = numpy.ones(size, dtype=numpy.bool)
sieve07 = numpy.ones(size, dtype=numpy.bool)
sieve11 = numpy.ones(size, dtype=numpy.bool)
sieve13 = numpy.ones(size, dtype=numpy.bool)
sieve17 = numpy.ones(size, dtype=numpy.bool)
sieve19 = numpy.ones(size, dtype=numpy.bool)
sieve23 = numpy.ones(size, dtype=numpy.bool)
sieve29 = numpy.ones(size, dtype=numpy.bool)
sieve01[0] = False
yield 2; yield 3; yield 5;
for i in xrange(int(n**0.5)/30+1):
if sieve01[i]:
k=30*i+1; yield k;
sieve01[ (k*k)/30::k] = False
sieve07[(k*k+ 6*k)/30::k] = False
sieve11[(k*k+10*k)/30::k] = False
sieve13[(k*k+12*k)/30::k] = False
sieve17[(k*k+16*k)/30::k] = False
sieve19[(k*k+18*k)/30::k] = False
sieve23[(k*k+22*k)/30::k] = False
sieve29[(k*k+28*k)/30::k] = False
if sieve07[i]:
k=30*i+7; yield k;
sieve01[(k*k+ 6*k)/30::k] = False
sieve07[(k*k+24*k)/30::k] = False
sieve11[(k*k+16*k)/30::k] = False
sieve13[(k*k+12*k)/30::k] = False
sieve17[(k*k+ 4*k)/30::k] = False
sieve19[ (k*k)/30::k] = False
sieve23[(k*k+22*k)/30::k] = False
sieve29[(k*k+10*k)/30::k] = False
if sieve11[i]:
k=30*i+11; yield k;
sieve01[ (k*k)/30::k] = False
sieve07[(k*k+ 6*k)/30::k] = False
sieve11[(k*k+20*k)/30::k] = False
sieve13[(k*k+12*k)/30::k] = False
sieve17[(k*k+26*k)/30::k] = False
sieve19[(k*k+18*k)/30::k] = False
sieve23[(k*k+ 2*k)/30::k] = False
sieve29[(k*k+ 8*k)/30::k] = False
if sieve13[i]:
k=30*i+13; yield k;
sieve01[(k*k+24*k)/30::k] = False
sieve07[(k*k+ 6*k)/30::k] = False
sieve11[(k*k+ 4*k)/30::k] = False
sieve13[(k*k+18*k)/30::k] = False
sieve17[(k*k+16*k)/30::k] = False
sieve19[ (k*k)/30::k] = False
sieve23[(k*k+28*k)/30::k] = False
sieve29[(k*k+10*k)/30::k] = False
if sieve17[i]:
k=30*i+17; yield k;
sieve01[(k*k+ 6*k)/30::k] = False
sieve07[(k*k+24*k)/30::k] = False
sieve11[(k*k+26*k)/30::k] = False
sieve13[(k*k+12*k)/30::k] = False
sieve17[(k*k+14*k)/30::k] = False
sieve19[ (k*k)/30::k] = False
sieve23[(k*k+ 2*k)/30::k] = False
sieve29[(k*k+20*k)/30::k] = False
if sieve19[i]:
k=30*i+19; yield k;
sieve01[ (k*k)/30::k] = False
sieve07[(k*k+24*k)/30::k] = False
sieve11[(k*k+10*k)/30::k] = False
sieve13[(k*k+18*k)/30::k] = False
sieve17[(k*k+ 4*k)/30::k] = False
sieve19[(k*k+12*k)/30::k] = False
sieve23[(k*k+28*k)/30::k] = False
sieve29[(k*k+22*k)/30::k] = False
if sieve23[i]:
k=30*i+23; yield k;
sieve01[(k*k+24*k)/30::k] = False
sieve07[(k*k+ 6*k)/30::k] = False
sieve11[(k*k+14*k)/30::k] = False
sieve13[(k*k+18*k)/30::k] = False
sieve17[(k*k+26*k)/30::k] = False
sieve19[ (k*k)/30::k] = False
sieve23[(k*k+ 8*k)/30::k] = False
sieve29[(k*k+20*k)/30::k] = False
if sieve29[i]:
k=30*i+29; yield k;
sieve01[ (k*k)/30::k] = False
sieve07[(k*k+24*k)/30::k] = False
sieve11[(k*k+20*k)/30::k] = False
sieve13[(k*k+18*k)/30::k] = False
sieve17[(k*k+14*k)/30::k] = False
sieve19[(k*k+12*k)/30::k] = False
sieve23[(k*k+ 8*k)/30::k] = False
sieve29[(k*k+ 2*k)/30::k] = False
for i in xrange(i+1,n/30):
if sieve01[i]: yield 30*i+1
if sieve07[i]: yield 30*i+7
if sieve11[i]: yield 30*i+11
if sieve13[i]: yield 30*i+13
if sieve17[i]: yield 30*i+17
if sieve19[i]: yield 30*i+19
if sieve23[i]: yield 30*i+23
if sieve29[i]: yield 30*i+29
i += 1
mod30 = n%30
if mod30 > 1:
if sieve01[i]: yield 30*i+1
if mod30 > 7:
if sieve07[i]: yield 30*i+7
if mod30 > 11:
if sieve11[i]: yield 30*i+11
if mod30 > 13:
if sieve13[i]: yield 30*i+13
if mod30 > 17:
if sieve17[i]: yield 30*i+17
if mod30 > 19:
if sieve19[i]: yield 30*i+19
if mod30 > 23:
if sieve23[i]: yield 30*i+23
Ps: Jeśli masz jakieś sugestie, jak przyspieszyć ten kod, cokolwiek od zmiany kolejności operacji do wstępnego przetwarzania czegokolwiek, proszę o komentarz.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-23 10:30:56
Oto wersja, którą napisałem jakiś czas temu; może być interesujące porównanie z Twoją dla szybkości. Nie ma to jednak nic wspólnego z problemami z przestrzenią (w rzeczywistości są one prawdopodobnie gorsze niż w Twojej wersji).
from math import sqrt
def basicSieve(n):
"""Given a positive integer n, generate the primes < n."""
s = [1]*n
for p in xrange(2, 1+int(sqrt(n-1))):
if s[p]:
a = p*p
s[a::p] = [0] * -((a-n)//p)
for p in xrange(2, n):
if s[p]:
yield p
wheelSieve jest głównym punktem wejścia.
from math import sqrt
from bisect import bisect_left
def basicSieve(n):
"""Given a positive integer n, generate the primes < n."""
s = [1]*n
for p in xrange(2, 1+int(sqrt(n-1))):
if s[p]:
a = p*p
s[a::p] = [0] * -((a-n)//p)
for p in xrange(2, n):
if s[p]:
yield p
class Wheel(object):
"""Class representing a wheel.
Attributes:
primelimit -> wheel covers primes < primelimit.
For example, given a primelimit of 6
the wheel primes are 2, 3, and 5.
primes -> list of primes less than primelimit
size -> product of the primes in primes; the modulus of the wheel
units -> list of units modulo size
phi -> number of units
"""
def __init__(self, primelimit):
self.primelimit = primelimit
self.primes = list(basicSieve(primelimit))
# compute the size of the wheel
size = 1
for p in self.primes:
size *= p
self.size = size
# find the units by sieving
units = [1] * self.size
for p in self.primes:
units[::p] = [0]*(self.size//p)
self.units = [i for i in xrange(self.size) if units[i]]
# number of units
self.phi = len(self.units)
def to_index(self, n):
"""Compute alpha(n), where alpha is an order preserving map
from the set of units modulo self.size to the nonnegative integers.
If n is not a unit, the index of the first unit greater than n
is given."""
return bisect_left(self.units, n % self.size) + n // self.size * self.phi
def from_index(self, i):
"""Inverse of to_index."""
return self.units[i % self.phi] + i // self.phi * self.size
def wheelSieveInner(n, wheel):
"""Given a positive integer n and a wheel, find the wheel indices of
all primes that are less than n, and that are units modulo the
wheel modulus.
"""
# renaming to avoid the overhead of attribute lookups
U = wheel.units
wS = wheel.size
# inverse of unit map
UI = dict((u, i) for i, u in enumerate(U))
nU = len(wheel.units)
sqroot = 1+int(sqrt(n-1)) # ceiling of square root of n
# corresponding index (index of next unit up)
sqrti = bisect_left(U, sqroot % wS) + sqroot//wS*nU
upper = bisect_left(U, n % wS) + n//wS*nU
ind2 = bisect_left(U, 2 % wS) + 2//wS*nU
s = [1]*upper
for i in xrange(ind2, sqrti):
if s[i]:
q = i//nU
u = U[i%nU]
p = q*wS+u
u2 = u*u
aq, au = (p+u)*q+u2//wS, u2%wS
wp = p * nU
for v in U:
# eliminate entries corresponding to integers
# congruent to p*v modulo p*wS
uvr = u*v%wS
m = aq + (au > uvr)
bot = (m + (q*v + u*v//wS - m) % p) * nU + UI[uvr]
s[bot::wp] = [0]*-((bot-upper)//wp)
return s
def wheelSieve(n, wheel=Wheel(10)):
"""Given a positive integer n, generate the list of primes <= n."""
n += 1
wS = wheel.size
U = wheel.units
nU = len(wheel.units)
s = wheelSieveInner(n, wheel)
return (wheel.primes[:bisect_left(wheel.primes, n)] +
[p//nU*wS + U[p%nU] for p in xrange(bisect_left(U, 2 % wS)
+ 2//wS*nU, len(s)) if s[p]])
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-05-24 15:25:18
Jednym z ulepszeń prędkości, które możesz wprowadzić za pomocą bitstring, jest użycie metody 'set', gdy wykluczysz wielokrotności bieżącej liczby.
Więc sekcja vital staje się
for i in range(3, limit, 2):
if flags[i]:
yield i
if i <= sub_limit:
flags.set(1, range(i*3, limit, i*2))
flags.findall([0]), który zwraca generator. Nie jestem pewien, czy byłoby to znacznie szybsze (znalezienie wzorców bitowych nie jest strasznie łatwe zrobić sprawnie).
[pełne ujawnienie: napisałem moduł bitstring, więc stawką jest trochę dumy!]
Jako porównanie wyjąłem też flaki z metody bitstring tak, że robi to w ten sam sposób, ale bez sprawdzania zakresu itp. Myślę, że daje to rozsądny niższy limit dla czystego Pythona, który działa na miliard elementów (bez zmiany algorytmu, co moim zdaniem jest oszustwem!)
def prime_pure(limit=1000000):
yield 2
flags = bytearray((limit + 7) // 8)
sub_limit = int(limit**0.5)
for i in xrange(3, limit, 2):
byte, bit = divmod(i, 8)
if not flags[byte] & (128 >> bit):
yield i
if i <= sub_limit:
for j in xrange(i*3, limit, i*2):
byte, bit = divmod(j, 8)
flags[byte] |= (128 >> bit)
Na mojej maszynie to działa w Około 0.62 sekundy dla milion elementów, co oznacza, że to około jedna czwarta prędkości odpowiedzi bitarray. Myślę, że to całkiem rozsądne dla czystego Pythona.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-07-25 21:56:29
Typy liczb całkowitych Pythona mogą mieć dowolny rozmiar, więc nie powinieneś potrzebować sprytnej biblioteki bitstring do reprezentowania zestawu bitów, tylko pojedynczej liczby.
Oto kod. Z łatwością obsługuje limit 1,000,000, a nawet może obsłużyć 10,000,000 bez narzekania zbytnio: {]}def multiples_of(n, step, limit):
bits = 1 << n
old_bits = bits
max = 1 << limit
while old_bits < max:
old_bits = bits
bits += bits << step
step *= 2
return old_bits
def prime_numbers(limit=10000000):
'''Prime number generator. Yields the series
2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...
using Sieve of Eratosthenes.
'''
yield 2
sub_limit = int(limit**0.5)
flags = ((1 << (limit - 2)) - 1) << 2
# Step through all the odd numbers
for i in xrange(3, limit, 2):
if not (flags & (1 << i)):
continue
yield i
# Exclude further multiples of the current prime number
if i <= sub_limit:
flags &= ~multiples_of(i * 3, i << 1, limit)
Funkcja multiples_of pozwala uniknąć kosztów ustawienia każdego pojedynczego wielokrotności z osobna. Ustawia początkowy bit, przesuwa go o początkowy Krok (i << 1) i dodaje wynik do siebie. Następnie podwaja krok, tak, że następny shift kopiuje oba bity, i tak dalej, aż osiągnie limit. Ustawia wszystkie wielokrotności liczby do limitu w czasie o (log (limit)).
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-05-24 14:21:56
Jedną z opcji, na którą warto spojrzeć, jest właśnie kompilacja modułu C / C++, dzięki czemu masz bezpośredni dostęp do funkcji bit-twidling. AFAIK mógłbyś napisać coś takiego i zwrócić wyniki dopiero po zakończeniu obliczeń wykonanych w C / C++. Teraz, gdy to piszę, możesz również spojrzeć na numpy, która przechowuje tablice jako natywne C dla szybkości. Nie wiem, czy będzie to szybsze niż Moduł bitstring!
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-05-24 14:29:45
Kolejna naprawdę głupia opcja, ale to może być pomocne, jeśli naprawdę potrzebujesz dużej listy liczb pierwszych dostępnych bardzo szybko. Powiedzmy, że jeśli potrzebujesz ich jako narzędzia do odpowiedzi na problemy projektu Eulera(jeśli problem polega tylko na optymalizacji kodu jako gry umysłowej, to nie ma znaczenia).
Użyj dowolnego wolnego rozwiązania do generowania listy i zapisz ją do pliku źródłowego Pythona, mówi primes.py, który zawiera tylko:
primes = [ a list of a million primes numbers here ]
Teraz, aby ich użyć, musisz zrobić import primes i uzyskać je z minimalną pamięcią footprint z prędkością dysku IO. Złożoność to liczba liczb pierwszych: -)
Nawet jeśli użyłeś źle zoptymalizowanego rozwiązania do wygenerowania tej listy, zostanie to wykonane tylko raz i nie ma to większego znaczenia.
Prawdopodobnie możesz zrobić to jeszcze szybciej używając ogórków / rozporek, ale masz pomysł...
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-05-27 00:36:23
Przydałoby się segmentowe Sito Eratostenesa. Pamięć używana dla każdego segmentu jest ponownie używana dla następnego segmentu.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-02-02 13:58:07
Oto kod Python3, który zużywa mniej pamięci niż opublikowane do tej pory rozwiązania bitarray/bitstring i około 1/8 pamięci Primesgen () Roberta Williama Hanksa, podczas gdy działa szybciej niż primesgen () (nieznacznie szybciej przy 1 000 000, używając 37kb pamięci, 3x szybciej niż primesgen () przy 1 000 000 000 używając poniżej 34MB). Zwiększenie rozmiaru fragmentu (zmienny fragment w kodzie) zużywa więcej pamięci, ale przyspiesza program, do limitu -- wybrałem wartość tak, aby jego wkład do pamięci jest poniżej około 10% N//30 bajtów sita. Nie jest tak wydajny jak nieskończony generator Willa Nessa (https://stackoverflow.com/a/19391111/5439078 ), ponieważ zapisuje (i zwraca na końcu, w postaci skompresowanej) wszystkie obliczone liczby pierwsze.
Powinno to działać poprawnie, o ile obliczenia pierwiastka kwadratowego są dokładne (około 2 * * 51, jeśli Python używa 64-bitowych podwojeń). Jednak nie należy używać tego programu, aby znaleźć primes tak duże!
(nie przeliczyłem / align = "center" bgcolor = "# e0ffe0 " / król Anglii / / align = center / Dzięki Robert!)
import numpy as np
def prime_30_gen(n):
""" Input n, int-like. Yields all primes < n as Python ints"""
wheel = np.array([2,3,5])
yield from wheel[wheel < n].tolist()
powers = 1 << np.arange(8, dtype='u1')
odds = np.array([1, 7, 11, 13, 17, 19, 23, 29], dtype='i8')
offsets=np.array([[0,6,10,12,16,18,22,28],[6,24,16,12,4,0,22,10],
[0,6,20,12,26,18,2,8], [24,6,4,18,16,0,28,10],
[6,24,26,12,14,0,2,20], [0,24,10,18,4,12,28,22],
[24,6,14,18,26,0,8,20], [0,24,20,18,14,12,8,2]],
dtype='i8')
offsets = {d:f for d,f in zip(odds, offsets)}
sieve = 255 * np.ones((n + 28) // 30, dtype='u1')
if n % 30 > 1: sieve[-1] >>= 8 - odds.searchsorted(n % 30)
sieve[0] &= ~1
for i in range((int((n - 1)**0.5) + 29) // 30):
for odd in odds[(sieve[i] & powers).nonzero()[0]]:
k = i * 30 + odd
yield int(k)
for clear_bit, off in zip(~powers, offsets[odd]):
sieve[(k * (k + off)) // 30 :: k] &= clear_bit
chunk = min(1 + (n >> 13), 1<<15)
for i in range(i + 1, len(sieve), chunk):
a = (sieve[i : i + chunk, np.newaxis] & powers)
a = np.flatnonzero(a.astype('bool')) + i * 8
a = (a // 8 * 30 + odds[a & 7]).tolist()
yield from a
return sieve
Uwaga na marginesie: jeśli chcesz mieć rzeczywistą prędkość i mieć 2GB PAMIĘCI RAM wymagane dla listy primes do 10 * * 9, powinieneś użyć pyprimesieve (on https://pypi.python.org / , używając primesieve http://primesieve.org/).
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-23 12:26:38