Databases
StackOverflow2013
Postsdbo
POImproving pure Python prime sieve by recurrence formula
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POImproving pure Python prime sieve by recurrence formula
    primarykey
    data
    text
    <p>I am trying to optimize further the champion solution in prime number thread by taking out the complex formula for sub-list length. len() of the same subsequence is too slow as len is expensive and generating the subsequence is expensive. This looks to slightly speed up the function but I could not yet take away the division, though I do the division only inside the condition statement. Of course I could try to simplify the length calculation by taking out the optimization of starting marking for n instead of n*n...</p> <p>I replaced division / by integer division // to be compatible with Python 3 or </p> <pre><code>from __future__ import division </code></pre> <p>Also I would be interesting if this recurrence formula could help to speed up the numpy solution, but I have not experience of using numpy much.</p> <p>If you enable psyco for the code, the story becomes completely different, however and Atkins sieve code becomes faster than this special slicing technique.</p> <pre><code>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 &lt; 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 &lt; 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)") </code></pre> <p>Profiling (not so much difference between versions)</p> <pre><code> 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 &lt;string&gt;:1(&lt;module&gt;) 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 &lt;string&gt;:1(&lt;module&gt;) 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} </code></pre> <p>Interestingly by increasing the limit to 10**8 and putting timing decorator to functions removing the profiling:</p> <pre><code>rwh_primes1 took 23.670 s primes took 22.792 s primesieve took 10.850 s </code></pre> <p>Interestingly if you do not produce list of primes but return the sieve itself the time is around half from number list version.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USTony Veijalainen
    1. USTony Veijalainen
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    3. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    3. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POImproving pure Python prime sieve by recurrence formula
      1. USunutbu
      1. VTFavorite
    2. VO
      singulars
      1. POImproving pure Python prime sieve by recurrence formula
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POImproving pure Python prime sieve by recurrence formula
      1. This table or related slice is empty.
      1. VTUpMod
    1. COjust saw your recurrence improvement today, nice ideia if i have time i will pursue a variation of it, did you saw the code for primes2 ? (a pure python version of my fastest numpy solution) http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/
      singulars
      1. POImproving pure Python prime sieve by recurrence formula
      1. USRobert William Hanks
    2. COI love python, but if you want to improve speed, rewrite it in C
      singulars
      1. POImproving pure Python prime sieve by recurrence formula
      1. USRuggero Turra
    3. CODid you profile your code? I yes, please post the results. If not, how can you know what to optimize?
      singulars
      1. POImproving pure Python prime sieve by recurrence formula
      1. US9000
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload