Генератор простых чисел в Python


Я пытаюсь получить лучшее понимание о генераторы в Python, потому что я не использую их достаточно (я думаю, что генераторы-это круто). Для этого я написал генератор простых чисел:

def primes():
    x = 2
    while True:
        for y in xrange(2, x/2 + 1):
            if x % y == 0:
                break
        else:
            yield x
        x = x + 1

Это работает, как ожидалось, но если я буду использовать список понимание, чтобы создать список простых чисел, используя этот генератор очень медленно по сравнению с функцией, которая генерирует тот же список решето:

[prime.next() for i in xrange(1000)] # exectues in 0.212 sec, sieve in 0.001 sec

Я предполагаю, что это не целевое назначение генератора, но я думал, я хотел бы видеть, если кто-нибудь может придумать способ, чтобы сделать это быстрее.



335
3
задан 10 декабря 2011 в 07:12 Источник Поделиться
Комментарии
2 ответа

Стилистически, используя модуле itertools.граф() вместо реализации своего собственного счетчика будет немного чище.

Я тоже предпочитаю использовать любой() за генератор, а не явного цикла с перерывом и еще. Я думаю, что это легче следовать.

Алгоритмически, это сито, имеет большое преимущество, потому что он использует предварительно рассчитанные праймы, чтобы сделать проверку следующим премьер-быстрее. Вам не нужно проверять каждую цифру подразделения, только праймы. Вы могли бы сделать что-то вроде:

past_primes = []
for x in itertools.count(2):
if not any(x % prime == 0 for prime in past_primes):
past_primes.append(x)
yield x

Выполняя деление все равно будет дороже, чем решето делать. Вы могли бы реализовать весь алгоритм решета в генераторе. Но я не уверен, что цель, которая будет служить.

Как правило, генераторы хорошо работать, когда вы не должны сохранить большое состояние для каждого сгенерированного значения. Но это не тот случай для простых чисел.

6
ответ дан 10 декабря 2011 в 08:12 Источник Поделиться

Я предпочитаю использовать набор вместо списка в этом случае:

past_primes = set()
for x in itertools.count(2):
if not any(x % prime == 0 for prime in past_primes):
past_primes.add(x)
yield x

Наборы имеют лучше временная сложность 0(1) против o(n) в списки http://wiki.python.org/moin/TimeComplexity

2
ответ дан 12 декабря 2011 в 06:12 Источник Поделиться