[PYTHON] 반복적 인 수식으로 순수 Python 프라임 시브 개선하기

반복적 인 수식으로 순수 Python 프라임 시브 개선하기

하위 목록 길이에 대한 복잡한 수식을 꺼내서 소수 스레드의 챔피언 솔루션을 더욱 최적화하려고합니다. 동일한 서브 시퀀스의 len ()은 너무 느리고 len은 비싸고 서브 시퀀스를 생성하는 것은 비용이 많이 든다. 이 기능은 약간 속도가 빨라지지만 조건부 내에서만 부분을 수행하지만 아직 부분을 제거 할 수는 없습니다. 물론 n * n 대신 n의 시작 마킹을 최적화하여 길이 계산을 단순화하려고 할 수 있습니다.

파이썬 3과 호환되도록 나누기 / 정수 나누기로 교체했습니다.

from __future__ import division

또한이 재발생 수식이 수치스러운 해결책의 속도를 높이는 데 도움이된다면 흥미로울 것이지만 나는 numpy를 많이 사용하지 않은 경험이 있습니다.

코드에 psyco를 사용하면 이야기가 완전히 달라 지지만 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

흥미롭게도 소수 목록을 작성하지 않고 시브 자체를 반환하면 시간은 숫자 목록 버전의 절반 정도입니다.

해결법

1. ==============================

   1.당신은 바퀴 최적화를 할 수 있습니다. 2와 3의 배수는 소수가 아니므로 전혀 저장하지 마십시오. 그런 다음 5에서 시작하여 2,4,2,4,2,4 등의 단계로 증가시켜 2와 3의 배수를 건너 뛸 수 있습니다.

   당신은 바퀴 최적화를 할 수 있습니다. 2와 3의 배수는 소수가 아니므로 전혀 저장하지 마십시오. 그런 다음 5에서 시작하여 2,4,2,4,2,4 등의 단계로 증가시켜 2와 3의 배수를 건너 뛸 수 있습니다.

   아래는 C ++ 코드입니다. 희망이 도움이됩니다.

   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;
               }
           }
       }
   }
   

2. ==============================

   2.속도 향상을 위해 C ++을 사용하기로 결정했다면 파이썬 체를 C ++로 이식했습니다. 전체 토론은 여기에 있습니다 : Eratosthenes의 최적화 된 시브 (Sieve of Eratosthenes)를 Python에서 C ++로 이식하는 것.

   속도 향상을 위해 C ++을 사용하기로 결정했다면 파이썬 체를 C ++로 이식했습니다. 전체 토론은 여기에 있습니다 : Eratosthenes의 최적화 된 시브 (Sieve of Eratosthenes)를 Python에서 C ++로 이식하는 것.

   인텔 Q6600, 우분투 10.10, g ++ -O3 및 N = 100000000으로 컴파일하면 415ms가 소요됩니다.

   #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);
   }
   
   // https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
   // 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);
       }
   
   }
   

from https://stackoverflow.com/questions/3285443/improving-pure-python-prime-sieve-by-recurrence-formula by cc-by-sa and MIT license