Улучшение чистого Python главное решето формулой повторения

Я пытаюсь оптимизировать далее решение чемпиона в потоке простого числа путем вынимания сложной формулы для длины подсписка. len () той же подпоследовательности является слишком медленным, как len является дорогим и генерирует, подпоследовательность является дорогой. Это надеется немного ускорять функцию, но я еще не мог устранить подразделение, хотя я делаю подразделение только в операторе условия. Конечно, я мог попытаться упростить расчет длины путем вынимания оптимизации запуска маркировки для n вместо n*n...

Я заменил подразделение / целочисленным делением//, чтобы быть совместимым с Python 3 или

from __future__ import division

Также я был бы интересен, если эта формула повторения могла бы помочь ускорить numpy решение, но у меня нет опыта использования numpy очень.

Если Вы включаете психо для кода, история становится полностью отличающейся, однако и код решета Atkins становится быстрее, чем этот специальный метод разрезания.

import cProfile

def rwh_primes1(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Returns  a list of primes < n """
    sieve = [True] * (n//2)
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]

def primes(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    # recurrence formula for length by amount1 and amount2 Tony Veijalainen 2010
    """ Returns  a list of primes < n """
    sieve = [True] * (n//2)
    amount1 = n-10
    amount2 = 6

    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i//2]:
             ## can you make recurrence formula for whole reciprocal?
            sieve[i*i//2::i] = [False] * (amount1//amount2+1)
        amount1-=4*i+4
        amount2+=4

    return [2] + [2*i+1 for i in xrange(1,n//2) if sieve[i]]

numprimes=1000000
print('Profiling')
cProfile.Profile.bias = 4e-6
for test in (rwh_primes1, primes):
    cProfile.run("test(numprimes)")

Профилирование (не такое различие между версиями)

         3 function calls in 0.191 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.006    0.006    0.191    0.191 <string>:1(<module>)
        1    0.185    0.185    0.185    0.185 myprimes.py:3(rwh_primes1)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}


         3 function calls in 0.192 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.006    0.006    0.192    0.192 <string>:1(<module>)
        1    0.186    0.186    0.186    0.186 myprimes.py:12(primes)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

Интересно путем увеличения предела 10 ** 8 и помещения синхронизации декоратора в функции, удаляющие профилирование:

rwh_primes1 took 23.670 s
primes took 22.792 s
primesieve took 10.850 s

Интересно, если Вы не производите список начал, но возвращаете само решето, время является приблизительно половиной от версии списка числа.