Project: Program Performance

Exercises 14.5 and 14.6 describe two of the improvements that can be made to the efficiency of Listing 14.1. Because they reduce the number of loop executions, they must make the program faster, but by how much? Is the improvement significant? Measuring program performance is one way to analyze the impact of changes made to your code.

In Python, we can get reasonably accurate timings using this function from the time module:

The standard way to use a clock is to surround the code you want to measure with two calls to the clock, like this:

 start = time.clock()

 sieve(10000)

 stop = time.clock()

 elapsed = stop − start

The variable elapsed will then hold the time it took to execute the function. Be sure not to put any other code between the two calls to the clock.

Exercises

1. Discuss the difficulties in accurately measuring a program’s execution time. What other factors might influence the elapsed time?
2. Write a function primelist(n) that uses isprime() from Listing 8.1 instead of the sieve to return a list of primes less than or equal to n. Test that this function returns the same list as sieve().
3. A list of boolean values can be used to implement the sieve rather than a list of integers. If the name of the boolean list is primes, then the idea is that

   primes[i] = True	If i is not crossed off (potential prime).
   primes[i] = False	If i is crossed off (not prime).

   Write a function sieve2(n) to compute and return the boolean list that results from using this technique to implement the sieve.

4. Write a function test(plist, blist, n) that returns True if the list of integer primes less than or equal to n in plist is the same as that represented by the boolean list blist. Return False otherwise.
5. Measure the performance of these approaches to finding a list of primes for n = 20000:

    sieve(n)

    primelist(n)

    sieve2(n)

   Report and discuss your results.