पुनरावृत्ति सूत्र द्वारा शुद्ध पायथन प्राइम चलनी में सुधार

Question

मैं उप-सूची लंबाई के लिए जटिल सूत्र को निकालकर प्राइम नंबर थ्रेड में चैंपियन समाधान को और अनुकूलित करने की कोशिश कर रहा हूं। लेन के महंगे महंगे हैं और बाद में उत्पन्न होने के बाद भी वही अनुक्रम का लेन बहुत धीमा है। यह फ़ंक्शन को थोड़ा तेज़ करने लगता है लेकिन मैं अभी तक विभाजन को दूर नहीं कर सका, हालांकि मैं केवल कथन कथन के अंदर विभाजन करता हूं। बेशक मैं शुरुआती के अनुकूलन बाहर निकालने के लिए n के बजाय n * n चिह्नित करके लंबाई गणना को आसान बनाने की कोशिश कर सकते ...

मैं प्रतिस्थापित विभाजन/पूर्णांक विभाजन // से अजगर 3 या

के साथ संगत होना करने के लिए

from __future__ import division 

यह भी दिलचस्प होगा अगर यह पुनरावृत्ति सूत्र numpy समाधान को तेज करने में मदद कर सकता है, लेकिन मुझे numpy का उपयोग करने का अनुभव नहीं है।

यदि आप कोड के लिए psyco सक्षम करते हैं, तो कहानी पूरी तरह से अलग हो जाती है, हालांकि और अटकिन्स चलनी कोड इस विशेष स्लाइसिंग तकनीक से तेज़ हो जाता है।

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)") 

रूपरेखा 10 ** से 8 सीमा बढ़ाने और कार्यों के लिए समय डेकोरेटर डालने की रूपरेखा को निकाल कर (संस्करणों के बीच नहीं इतना अंतर)

  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} 

दिलचस्प बात यह है:

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

दिलचस्प बात यह है कि यदि आप प्राइम्स की सूची नहीं बनाते हैं लेकिन चावल खुद को वापस कर देते हैं तो समय संख्या सूची संस्करण से लगभग आधा है।

Answer 1

आप एक व्हील अनुकूलन कर सकते हैं। 2 और 3 के गुणक प्राइम नहीं हैं, इसलिए उन्हें बिल्कुल स्टोर न करें। फिर आप 5 से शुरू कर सकते हैं और 2,4,2,4,2,4 आदि के चरणों में वृद्धि करके 2 और 3 के गुणकों को छोड़ सकते हैं ..

नीचे इसके लिए एक सी ++ कोड है। उम्मीद है की यह मदद करेगा।

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

Answer 2

आप तय कर सकते हैं, तो आप सेल्सियस तक ++ जा रहे हैं गति में सुधार करने, मैं सी ++ के लिए अजगर चलनी स्थलांतरित किया। पूरी चर्चा यहां पाई जा सकती है: Porting optimized Sieve of Eratosthenes from Python to C++।

इंटेल Q6600, उबंटू 10.10 पर, g++ -O3 के साथ संकलित और एन = 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); 
} 

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

}