Algorithms intro: Profiling python code

When developing software and implementing algorithms its always important to be as efficient as possible, to have the most elegant solution that is concise, understandable to others, but most importantly uses the resources it has in the most efficient way.

This post extends the previous http://jseller.blogspot.ca/2016/11/algorithms-intro-implementing-math-proof.html and profiles the algorithms we created to implement Euclids GCD method

Profiling

With python and most every language has some profiling tools to check various computer resources; most frequently this is the memory used and CPU cycles consumed. For our algorithm post we are just concerned with the time any of our algorithms take to execute.

import cProfile, pstats, io

#you can run any code as a string to be executed:
cProfile.run('fill_rectangle_with_squares(Rectangle(24000,19453))')

#but the profile object can also be enabled and disabled to run many lines.
pr = cProfile.Profile()
pr.enable()
fill_rectangle_with_squares(Rectangle(2400000,194530))
pr.disable()
pr.print_stats()

With

If there are many lines, this can get a little difficult keeping the first two and last two in the same spot, or accidentally deleted the cleanup part. Python has a 'with' statement to make this nice and clean. http://effbot.org/zone/python-with-statement.htm

import cProfile, pstats, io
class profile_block:
    def __enter__(self):
        self.profile = cProfile.Profile()
        self.profile.enable()
        #set things up
        #return thing
    def __exit__(self, type, value, traceback):
        #tear things down
        self.profile.disable()
        self.profile.print_stats()

Try running a few versions and look at the output. It will probably take some larger numbers until you can see a change. The times depends on the machine, but by using the 'with' block we know the disable and printing will always happen, and the code is nicer.

with profile_block():
    fill_rectangle_with_squares(Rectangle(24000000,19453003))

with profile_block():
    fill_rectangle_with_squares_iterative(24000000,19453003)

Running the different approaches with the large example show a 3x difference with the optimized version.

with profile_block():
    fill_rectangle_with_squares_iterative(2400000223334219423423424234240,1945303434230234234242322)

with profile_block():
    greatest_common_divisor(2400000223334219423423424234240,1945303434230234234242322)

The output. This is a big improvement between our two versions.

fill 2400000223334219423423424234240, 1945303434230234234242322 with squares 
smallest square found 2, 2 
         6 function calls in 0.989 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 euclid.py:104(__exit__)
        1    0.000    0.000    0.000    0.000 euclid.py:22(__init__)
        2    0.000    0.000    0.000    0.000 euclid.py:25(__str__)
        1    0.989    0.989    0.989    0.989 euclid.py:55(fill_rectangle_with_squares_iterative)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

greatest common divisor 2
         3 function calls in 0.386 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 euclid.py:104(__exit__)
        1    0.386    0.386    0.386    0.386 euclid.py:77(greatest_common_divisor)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

Wrap it up

From the first part of this post we solved the problem with computation and in this case it was a classic, Euclid Greatest Common Denominator method. His proof in Elements uses only geometry, but we also used geometry as a handy tool to visualize and understand the proof.

What we wanted to find out though, was how to validate this method with computation, and understand which approach works best.

As recursive implementations can more closely model the real world scenario, we have to keep in mind that this is being solved with computation, so our iterative approach is able to take advantage of the computing power at hand.

Finding out how well that actually performed is the job of profiling, and a well measured system, or just a small part of it, can go a long way to understanding how to write efficient code.