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

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

16 голосов
/ 20 июля 2010

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

Я заменил деление / на целочисленное деление // для совместимости с Python 3 или

from __future__ import division

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

Если вы включили psyco для кодаОднако история становится совершенно другой, и ситовый код Аткинса становится быстрее, чем эта специальная техника нарезки. 

import cProfile

def rwh_primes1(n):
    # /2029352/samyi-bystryi-sposob-perechislit-vse-prostye-chisla-nizhe-n#2029364
    """ 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):
    # /2029352/samyi-bystryi-sposob-perechislit-vse-prostye-chisla-nizhe-n#2029364
    # 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

Интересно, что если вы не создаете список простых чисел, а возвращаете само сито, время составляет примерно половину от версии списка чисел.

Ответы [ 2 ]

1 голос
/ 13 апреля 2011

Вы можете сделать оптимизацию колеса.Кратные 2 и 3 не являются простыми числами, поэтому не храните их вообще.Затем вы можете начать с 5 и пропустить кратные 2 и 3, увеличивая с шагом 2,4,2,4,2,4 и т. Д.Надеюсь, это поможет. 

void sieve23()
{
    int lim=sqrt(MAX);
    for(int i=5,bit1=0;i<=lim;i+=(bit1?4:2),bit1^=1)
    {
        if(!isComp[i/3])
        {
            for(int j=i,bit2=1;;)
            {
                j+=(bit2?4*i:2*i);
                bit2=!bit2;
                if(j>=MAX)break;
                isComp[j/3]=1;
            }
        }
    }
}
0 голосов
/ 13 апреля 2011

Если вы решите, что собираетесь улучшить C ++, я перенес сито Python на C ++.Полное обсуждение можно найти здесь: Портирование оптимизированного сита эратосфена с Python на C ++ .

На Intel Q6600, Ubuntu 10.10, скомпилировано с g++ -O3 и с N = 100000000 это занимает 415мс. 

#include <vector>
#include <boost/dynamic_bitset.hpp>

// http://vault.embedded.com/98/9802fe2.htm - integer square root
unsigned short isqrt(unsigned long a) {
    unsigned long rem = 0;
    unsigned long root = 0;

    for (short i = 0; i < 16; i++) {
        root <<= 1;
        rem = ((rem << 2) + (a >> 30));
        a <<= 2;
        root++;

        if (root <= rem) {
            rem -= root;
            root++;
        } else root--;

    }

    return static_cast<unsigned short> (root >> 1);
}

// /2029352/samyi-bystryi-sposob-perechislit-vse-prostye-chisla-nizhe-n#2029364
// https://stackoverflow.com/questions/5293238/porting-optimized-sieve-of-eratosthenes-from-python-to-c/5293492
template <class T>
void primesbelow(T N, std::vector<T> &primes) {
    T i, j, k, sievemax, sievemaxroot;

    sievemax = N/3;
    if ((N % 6) == 2) sievemax++;

    sievemaxroot = isqrt(N)/3;

    boost::dynamic_bitset<> sieve(sievemax);
    sieve.set();
    sieve[0] = 0;

    for (i = 0; i <= sievemaxroot; i++) {
        if (sieve[i]) {
            k = (3*i + 1) | 1;
            for (j = k*k/3; j < sievemax; j += 2*k) sieve[j] = 0;
            for (j = (k*k+4*k-2*k*(i&1))/3; j < sievemax; j += 2*k) sieve[j] = 0;
        }
    }

    primes.push_back(2);
    primes.push_back(3);

    for (i = 0; i < sievemax; i++) {
        if (sieve[i]) primes.push_back((3*i+1)|1);
    }

}
...