[Tutor] Understanding cProfile output

[Dave Angel]

On 09/20/2012 05:15 PM, ranveer raghuwanshi wrote:
> Thanks for the input everyone.
> 
> @Dave, I basically implemented the sieve of eratosthenes to fiind the
> number of prime numbers in a given range. So, yes I am looking for
> suggestions to speed it up.
> 

Please don't top-post on this forum.  It puts your response out of order
with the parts you quote.  Put your remarks AFTER the quotes.

There are some very clever algorithms out there, and probably the
fastest is to download a list of primes from some website  (I'm sure we
could find it by searching)  I don't pretend to know which is the best one.

But if you just want your algorithm tweaked, I could suggest that you
could greatly reduce the number of comparisons by doing the modulo only
on the PRIMES below max_check.  Reverse your two loops, so the inner
loop is the one that loops over the divisors.  Don't do all that list
manipulation, just solve the problem.

In the code below, your algorithm is prime1().  Then I have prime2() and
prime3(), which are equivalent algorithms, yielding approximately 25-
and 35-fold improvement.  I'm sure there are better algorithms, and ones
that don't involve such large lists.  But these are true to the original
concept, of the sieve.

from math import floor,sqrt
import time as timer

def prime1(limit):
    count = int(floor(sqrt(100000)))
    max_check = range(2,count+1)
    original_list = range(2,100001)

    for j in max_check:
        temp_list=[]
        for i in original_list:
            if i%j==0 and j<i:
                temp_list.append(i)
            else:
                pass
        original_list = list(set(original_list) - set(temp_list))
        temp_list = []

    #print original_list
    print len(original_list)

def prime2(limit):
    original_list = range(limit+1)
    original_list[1] = 0

    count = int(sqrt(limit))
    i = 0
    for value in original_list:
        if value:
            for n in xrange(2*value, limit+1, value):
                original_list[n] = 0

    original_list =  sorted(original_list)
    ind = original_list.index(2)
    final = original_list[ind:]
    print "---", final[:10]
    print final[-10:]
    print len(final)

#This version uses slice to zero the items
def prime3(limit):
    ZEROES = [0] * (limit/2 +1)
    original_list = range(limit+1)
    original_list[1] = 0

    count = int(sqrt(limit))
    i = 0
    for value in original_list:
        if value:
            sz = int(limit/value) - 1
            original_list[2*value: limit+1: value] = ZEROES[:sz]

    original_list =  sorted(original_list)
    ind = original_list.index(2)
    final = original_list[ind:]
    print "---", final[:10]
    print final[-10:]
    print len(final)




start = timer.time()
limit = 10**5
prime1(limit)
print timer.time() - start
start = timer.time()
print "------------"
prime2(limit)
print timer.time() - start
start = timer.time()
print "------------"
prime3(limit)
print "------------"
print timer.time() - start
start = timer.time()





-- 

DaveA