CHAPTER
OTHER WAYS TO MAKE THINGS RUN FASTER
After the release of v0.1 of this report some people have asked me to include notes on algorithmic choices and other options. Choosing the right algorithm is incredibly important, often in Python you can improve your run-times by trading some storage space for extra speed by changing the type of container you use.
If you’re not familiar with “Big O Notation” then read up in WikiPedia: http://en.wikipedia.org/wiki/Big_o_notation
There are some notes on algorithmic time complexity here: http://wiki.python.org/moin/TimeComplexity
As you’ll see the act of appending to a list is O(1) (i.e. constant time) but inserting into a list is O(n) (i.e. it can be rather slow if ‘n’ is big!). Similarity testing if an item is in a list is O(n). If all you’re interested in is knowing whether unique items are in a list then you might want to use a set where in costs between O(1) and O(n). The downside is that a set consumes more memory as it has to manage extra data structures that allow for the faster inserts and lookups.
Earlier in this report I showed “A (slightly) faster CPython implementation” where we reduced the number of local dereference operations that CPython would have to perform. Generally it is wise to dereference as infrequently as possible - you can go as far as doing something like local_pow = math.pow to make a local reference to the power function, then you can use local_pow(...) in a tight inner loop rather than math.pow(...).
Don’t take the above as any kind of law - test it by timing the effect! Note that PyPy will probably make this optimisation obsolete!
Do take a look at http://wiki.python.org/moin/PythonSpeed/PerformanceTips - also note that some of the tips are outdated. As mentioned above don’t take anything as a law - make small changes and test for changes in speed. Sometimes you’ll be surprised to discover that things run slower when your intuition said they would go faster!