Быстрое сито простых чисел в Python

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

def sieve_for_primes_to(n):
    size = n//2
    sieve = [1]*size
    limit = int(n**0.5)
    for i in range(1,limit):
        if sieve[i]:
            val = 2*i+1
            tmp = ((size-1) - i)//val 
            sieve[i+val::val] = [0]*tmp
    return sieve


print [2] + [i*2+1 for i, v in enumerate(sieve_for_primes_to(10000000)) if v and i>0]

Время возврата выполнения

python -m timeit -n10 -s "import euler" "euler.sieve_for_primes_to(1000000)"
10 loops, best of 3: 19.5 msec per loop

Хотя метод, описанный в ответе на связанный выше вопрос как самый быстрый из кулинарной книги Python, приведен ниже.

import itertools
def erat2( ):
    D = {  }
    yield 2
    for q in itertools.islice(itertools.count(3), 0, None, 2):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            x = p + q
            while x in D or not (x&1):
                x += p
            D[x] = p

def get_primes_erat(n):
  return list(itertools.takewhile(lambda p: p<n, erat2()))

При запуске дает

python -m timeit -n10 -s "import euler" "euler.get_primes_erat(1000000)"
10 loops, best of 3: 697 msec per loop

Мой вопрос: почему люди рекламируют вышеизложенное из кулинарной книги, которая относительно сложна, как идеальный первичный генератор?


python algorithm primes sieve-of-eratosthenes
person cobie    schedule 14.04.2013    source источник
comment
Кто и где рекламирует erat2 как идеальный первичный генератор? Пожалуйста, предоставьте ссылки, чтобы мы могли лучше понять контекст, который вызвал ваш вопрос.   -  person NPE    schedule 15.04.2013
comment
Вы сравнивали свой алгоритм с алгоритмом rwh_primes2?   -  person Martijn Pieters    schedule 15.04.2013
comment
erat2 сравнивали только с кодом OP на этой странице, и Алекс Мартелли только сказал, что решение Cookbook более чем в два раза быстрее по сравнению с решением OP. И ваше решение в два раза медленнее по сравнению с rwh_primes2.   -  person Ashwini Chaudhary    schedule 15.04.2013
comment
Это похоже на небольшую вариацию rwh_primes1.   -  person DSM    schedule 15.04.2013

Ответы (2)


arrow_upward
9
arrow_downward

Я преобразовал ваш код, чтобы он соответствовал сценарию сравнения простых сит @unutbu по адресу Самый быстрый способ перечислить все простые числа ниже N следующим образом:

def sieve_for_primes_to(n):
    size = n//2
    sieve = [1]*size
    limit = int(n**0.5)
    for i in range(1,limit):
        if sieve[i]:
            val = 2*i+1
            tmp = ((size-1) - i)//val 
            sieve[i+val::val] = [0]*tmp
    return [2] + [i*2+1 for i, v in enumerate(sieve) if v and i>0]

На моем MBPro i7 скрипт быстро вычисляет все простые числа ‹ 1000000, но на самом деле в 1,5 раза медленнее, чем rwh_primes2, rwh_primes1 (1.2), rwh_primes (1.19) и PrimeSieveSeq (1.12) (@andreasbriese в конце страницы).

person ABri    schedule 25.09.2013

arrow_upward
3
arrow_downward

Вы должны использовать только "отложенный" вариант этого алгоритма. Сравнивая ваш код тестовый прогон до 10 и 20 млн верхнего предела, как

...
print(len( [2] + [i*2+1 for i, v in 
  enumerate(sieve_for_primes_to(10000000)) if v and i>0]))

с другим, используйте соответствующие числа 664579 и 1270607 простых чисел, чтобы получить, как

...
print( list( islice( (p for p in postponed_sieve() ), n-1, n+1)))

показывает, что ваш код работает "всего" в 3,1x...3,3x раза быстрее. :) Не в 36x раз быстрее, как показывают ваши тайминги по какой-то причине.

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

Здесь, в нижнем диапазоне, важна временная сложность алгоритма, которая должна быть около ~ n^(1+a), a < 0.1...0.2 эмпирические порядки роста, которыми они оба кажутся на самом деле. Играть с игрушечным генератором с ~ n^1.5 или даже ~ n^2 порядками роста просто неинтересно.

person Will Ness    schedule 16.04.2013