Ускорить строку битов/битовые операции в Python?
Я записал генератор простого числа с помощью Решета Эратосфена и Python 3.1. Код работает правильно и корректно в 0,32 секунды на ideone.com для генерации простых чисел до 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
Проблема, у меня заканчивается память, когда я пытаюсь генерировать числа до 1 000 000 000.
flags = [False, False] + [True] * (limit - 2)
MemoryError
Как можно предположить, выделив 1 миллиард булевых значений (1 байт 4 или 8 байтов (см. комментарий), каждый в Python), действительно не выполнимо, таким образом, я изучил строку битов. Я фигурировал, использование 1 бита для каждого флага будет намного более эффективным памятью. Однако производительность программы, отброшенная решительно - время выполнения 24 секунд, для простого числа до 1 000 000. Это происходит, вероятно, из-за внутренней реализации строки битов.
Можно комментировать/не комментировать эти три строки для наблюдения то, что я изменил для использования BitString как фрагмент кода выше.
Мой вопрос, там способ ускорить мою программу, с или без строки битов?
Править: Протестируйте код сами перед регистрацией. Я не могу принять ответы, которые работают медленнее, чем мой существующий код, естественно.
Отредактируйте снова:
9 ответов
Есть пара небольших оптимизаций для вашей версии. Поменяв местами роли True и False, вы можете изменить "if flags[i] is False:" на "if flags[i]:". А начальное значение для второго оператора range может быть i*i вместо i*3. Ваша первоначальная версия занимает 0,166 секунды на моей системе. С этими изменениями версия, представленная ниже, занимает 0,156 секунды на моей системе.
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
Однако это не поможет вам решить проблему с памятью.
Переходя в мир расширений C, я использовал версию разработки gmpy. (Оговорка: я один из сопровождающих.) Версия разработки называется gmpy2 и поддерживает изменяемые целые числа, называемые xmpz. Используя gmpy2 и следующий код, я получил время выполнения 0,140 секунды. Время выполнения для ограничения в 1 000 000 000 составляет 158 секунд.
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)
Продвигая оптимизацию и жертвуя ясностью, я получаю время выполнения 0.107 и 123 секунды со следующим кодом:
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: Based on this exercise, I modified gmpy2 to accept xmpz.bit_set(iterator). При использовании следующего кода время выполнения для всех простых чисел меньше 1 000 000 000 составляет 56 секунд для Python 2.7 и 74 секунды для Python 3.2. (Как отмечено в комментариях, xrange быстрее, чем 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)))
Правка #2: Еще одна попытка! Я модифицировал gmpy2, чтобы он принимал xmpz.bit_set(slice). При использовании следующего кода время выполнения для всех простых чисел меньше 1,000,000,000 составляет около 40 секунд как для Python 2.7, так и для Python 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)
Правка #3: Я обновил gmpy2 для правильной поддержки нарезки на битовом уровне xmpz. Производительность не изменилась, но API стал намного удобнее. Я немного подправил и добился снижения времени до примерно 37 секунд. (См. Правку #4 об изменениях в 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)
Правка #4: Я сделал некоторые изменения в gmpy2 2.0.0b1, которые нарушают предыдущий пример. gmpy2 больше не рассматривает True как специальное значение, которое обеспечивает бесконечный источник 1-битов. Вместо него следует использовать -1.
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)
Правка #5: Я сделал некоторые улучшения в gmpy2 2.0.0b2. Теперь вы можете перебирать все биты, которые либо установлены, либо очищены. Время работы улучшилось на ~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))
Один из вариантов, на который вы, возможно, захотите посмотреть, - это просто скомпилировать модуль C / C ++, чтобы у вас был прямой доступ к функциям бит-тиддлинга. AFAIK вы можете написать что-то в этом роде и возвращать результаты только после завершения вычислений, выполненных на C / C ++. Теперь, когда я это набираю, вы также можете посмотреть на numpy, который для скорости хранит массивы как нативный C. Я не знаю, будет ли это быстрее, чем модуль битовой строки!
Хорошо, вот (почти полный) комплексный бенчмаркинг, который я сделал сегодня вечером, чтобы увидеть, какой код работает быстрее всего. Надеюсь, кто-то найдет этот список полезным. Я пропустил все, что занимает более 30 секунд на моей машине.
Я хотел бы поблагодарить всех, кто внес свой вклад. Я получил много информации от ваших усилий, и я надеюсь, что вы тоже.
Моя машина: AMD ZM-86, 2,40 ГГц dual-Core, с 4 ГБ оперативной памяти. Это ноутбук HP Touchsmart Tx2. Обратите внимание, что, хотя я, возможно, связался с pastebin, я протестировал все следующее на своей собственной машине.
Я добавлю тест gmpy2, как только смогу его построить.
Все тесты протестированы в Python 2.6 x86
Возврат списка простых чисел n до 1,000,000: (Использование Python генераторы)
Версия генератора numpy Себастьяна (обновленная) - 121 мс @
Сито Марка + Колесо - 154 мс
Версия Роберта со нарезкой - 159 мс
Моя улучшенная версия со нарезкой - 205 мс
Генератор Numpy с перечислением - 249 мс @
Базовое сито Марка - 317 мс
casevh улучшение по сравнению с моим оригиналом solution - 343 ms
Мой модифицированный numpy генератор раствор - 407 ms
Мой оригинальный метод в question - 409 мс
Решение Bitarray - 414 мс @
Чистый Python с байтаррием - 1394 мс @
Решение BitString Скотта - 6659 ms @
'@' означает, что этот метод способен генерировать до n < 1 000 000 000 на настройка моей машины.
Кроме того, если вам не нужен генератор и просто хочу весь список сразу:
numpy решение от RosettaCode - 32 мс @
(Решение numpy также способно генерировать до 1 миллиарда, что заняло 61,6259 секунды. Я подозреваю, что память была заменена один раз, следовательно, двойное время.)
Вот версия, которую я написал некоторое время назад; может быть интересно сравнить с вашим по скорости. Однако это не решает проблем с пространством (на самом деле, они, вероятно, хуже, чем в вашей версии).
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 является основной точкой входа.
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]])
Что касается колеса: ну, вы знаете, что (кроме 2) все простые числа нечетные, поэтому большинство решет пропускает все четные числа. Точно так же вы можете пойти немного дальше и заметить, что все простые числа (кроме 2 и 3) конгруэнтны 1 или 5 по модулю 6 (== 2 * 3), поэтому вы можете уйти, сохраняя только записи для этих чисел в вашем сите. . Следующий шаг - отметить, что все простые числа (кроме 2, 3 и 5) конгруэнтны одному из 1, 7, 11, 13, 17, 19, 23, 29 (по модулю 30) (здесь 30 == 2 * 3 * 5) и так далее.
Связанный вопрос: Самый быстрый способ перечислить все простые числа ниже N в python .
Привет, я тоже ищу код на Python, чтобы генерировать простые числа до 10 ^ 9 так быстро, как я могу, что сложно из-за проблем с памятью. до сих пор я придумал это для генерации простых чисел до 10 ^ 6 и 10 ^ 7 (тактовая частота 0,171 с и 1764 с соответственно на моей старой машине), что, похоже, немного быстрее (по крайней мере, на моем компьютере), чем «Моя улучшенная версия с нарезкой» из предыдущего сообщения, вероятно потому, что я использую n // ii +1 (см. ниже) вместо аналогичный len (flags [i2 :: i << 1]) в другом коде.пожалуйста, поправьте меня, если я ошибаюсь. Любые предложения по улучшению очень приветствуются.
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]]
В одном из своих кодов Ксавье использует flags [i2 :: i << 1] и len (flags [i2 :: i << 1]) . Я вычислил размер явно, используя тот факт, что между i * i..n мы имеем (ni * i) // 2 * i кратные 2 * i , поскольку мы хотим подсчитать i * i , мы также суммируем 1 , поэтому len (sieve [i * i :: 2 * i]) равно (ni * i) // (2 * i) +1 . Это ускоряет код. Базовый генератор, основанный на приведенном выше коде, будет выглядеть следующим образом:
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
с небольшой модификацией можно написать немного более медленную версию приведенного выше кода, которая начинается с сита половинного размера sieve = [True] * (n // 2) и работает для того же n . не уверен, как это отразится на проблеме с памятью. В качестве примера реализации приведем
модифицированная версия кода numpy rosetta (возможно, быстрее), начиная с сита, составляющего половину размера.
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
Генератор Faster & more с точки зрения памяти будет выглядеть так:
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
или с немного большим количеством кода:
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: Если у вас есть предложения о том, как ускорить этот код, все, от изменения порядка операций до предварительное вычисление чего-либо, прокомментируйте, пожалуйста.
Еще один действительно глупый вариант, но он может помочь, если вам действительно нужен большой список простых чисел, доступный очень быстро. Скажем, если они вам нужны как инструмент для решения проблем проекта Эйлера (если проблема просто в оптимизации вашего кода как в игре разума, это не имеет значения).
Используйте любое медленное решение для создания списка и сохранения его в исходный файл на Python, говорит primes.py , который будет просто содержать:
primes = [ a list of a million primes numbers here ]
Теперь, чтобы использовать их, вам просто нужно выполнить import primes , и вы получаете их с минимальным объемом памяти со скоростью дискового ввода-вывода. Сложность - это количество простых чисел: -)
Даже если вы использовали плохо оптимизированное решение для создания этого списка, это будет сделано только один раз, и это не имеет большого значения.
Возможно, вы могли бы сделать это еще быстрее, используя pickle / unpickle, но вы поняли идею ...
Целочисленные типы Python могут иметь произвольный размер, поэтому вам не понадобится умная библиотека битовых строк для представления набора битов, только одно число.
Вот код. Он с легкостью обрабатывает ограничение в 1 000 000 и даже 10 000 000 без особых претензий:
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)
Функция multiples_of позволяет избежать затрат на установку каждого кратного по отдельности. Он устанавливает начальный бит, сдвигает его на начальный шаг ( i << 1 ) и добавляет результат самому себе. Затем он удваивает шаг, так что следующий сдвиг копирует оба бита и так далее, пока не достигнет предела. Это устанавливает все кратные числа до предела времени O (log (limit)).
Одно из улучшений скорости, которое вы можете сделать, используя битовую строку, - это использовать метод «set», когда вы исключаете кратные текущему числу.
Таким образом, жизненно важный раздел становится
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))
На моей машине он работает примерно в 3 раза быстрее, чем оригинал.
Другой моей мыслью было использовать цепочку битов для представления только нечетных чисел. Затем вы можете найти неустановленные биты, используя flags.findall ([0]) , который возвращает генератор. Не уверен, что это будет намного быстрее (найти битовые шаблоны не так уж и легко).
[Полное раскрытие: я написал модуль битовой строки, так что на кону у меня есть некоторая гордость!]
Для сравнения я также убрал кишку из метода битовой строки, так что он делает это в таким же образом, но без проверки диапазона и т. д.Я думаю, что это дает разумный нижний предел для чистого Python, который работает с миллиардом элементов (без изменения алгоритма, который я считаю обманом!)
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)
На моей машине это выполняется примерно за 0,62 секунды для миллиона элементов, что означает примерно четверть скорости ответа на битовый массив. Я думаю, что это вполне разумно для чистого Python.
Хорошо, это мой второй ответ, но поскольку скорость имеет существенное значение, я подумал, что должен упомянуть модуль bitarray - хотя это битовая строка враг: ). Он идеально подходит для этого случая, так как не только является расширением C (и он быстрее, чем чистый Python), но также поддерживает присвоение срезов. Однако это еще не доступно для Python 3.
Я даже не пытался это оптимизировать, я просто переписал версию с битовой строкой. На моей машине я получаю 0,16 секунды для простых чисел меньше миллиона.
Для миллиарда он работает отлично и завершается за 2 минуты 31 секунду.
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