Python Code Optimization

Performance optimization is making a program run faster, and also is closely related to refactoring

Typically, an 80/20 rule applies. A 20% effort is needed to implement the bulk of the program. Then another 80% effort (and budget) is needed to optimize, refactor, extend and/or document the program.

You first need the program to produce correct results (with correct input) before you know what is making it slow. Do not worry about performance during development.


Profiling

I used Python cProfile module to write this custom profile function. The input is the name and parameters of the function that you would like to profile.

def profile(function, *args, **kwargs):
    """ Returns performance statistics (as a string) for the given function.
    """
    def _run():
        function(*args, **kwargs)
    import cProfile as profile
    import pstats
    import os
    import sys; sys.modules['__main__'].__profile_run__ = _run
    id = function.__name__ + '()'
    profile.run('__profile_run__()', id)
    p = pstats.Stats(id)
    p.stream = open(id, 'w')
    p.sort_stats('time').print_stats(20)
    p.stream.close()
    s = open(id).read()
    os.remove(id)
    return s

For using it:

def fibonaci(n):
	if n < 2:
		return 1
	return fibonaci(n-1) + fibonaci(n-2)

def fibonaci_dp(n, cache={}):
	if n not in cache:
		cache[n] = 1 if n < 2 else fibonaci_dp(n-1, cache) + fibonaci_dp(n-2, cache)
	return cache[n]

from profile import profile
print (profile(fibonaci, 30))
print (profile(fibonaci_dp, 30, {}))

After running this file, you will see the output like below:

Tue Jan  1 00:21:02 2019    fibonaci()

         2692540 function calls (4 primitive calls) in 0.558 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
2692537/1    0.558    0.000    0.558    0.558 test_profile.py:1(fibonaci)
        1    0.000    0.000    0.558    0.558 /Users/long-inspectorio/Documents/Projects/example/optimize_code/profile.py:4(_run)
        1    0.000    0.000    0.558    0.558 :1()
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
Tue Jan  1 00:21:02 2019    fibonaci_dp()

         62 function calls (4 primitive calls) in 0.000 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     59/1    0.000    0.000    0.000    0.000 test_profile.py:7(fibonaci_dp)
        1    0.000    0.000    0.000    0.000 /Users/long-inspectorio/Documents/Projects/example/optimize_code/profile.py:4(_run)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 :1()

Once we have isolated the slow parts, we can try to make them faster. To do this, we time them one by one. We can tinker with the source code and verify if the elapsed time increases or decreases.


Dictionaries

Python dictionary uses the hash table. Therefore, finding an item in a dictionary is really fast.

In the hash table,  a lookup operation (e.g., if x in y) is O(1). A lookup operation in a list means that the entire list needs to be iterated, resulting in O(n) for a list of length n.

Follow this code

from time import time
stopwords = [
    'a', 'an', 'and', 'are', 'as', 'at', 'be', 'by',
    'for', 'from', 'has', 'he', 'in', 'is', 'it', 'its',
    'of', 'on', 'that', 'the', 'to', 'was', 'were', 'will', 'with'
]

words = ['Mr.', 'Hat', 'is', 'feeding', 'the', 'black', 'cat', '.']

def find(words, stopwords):
	return [w for w in words if w not in stopwords]

#-----------------------------------------------
t = time()
for i in range(1000000):
	find(words, stopwords)
print("Time running: {}".format(time() - t))


#-----------------------------------------------
t = time()
stopwords_dict = dict.fromkeys(stopwords)
for i in range(1000000):
	find(words, stopwords_dict)
print("Time running: {}".format(time() - t))

Time running in list: 2.40959405899 s
Time running in dictionary: 0.709087133408 s

Because of the advantage of python dictionary, we can use it as a cache when development. Please come back to my example above with fibonaci_dp function.


Sets

Set operations (union, intersection, difference) are faster than iterating over lists:

Syntax Operation Description
set(list1) | set(list2) union New set with values from both list1 and list2.
set(list1) & set(list2) intersection New set with values common to list1 and list2.
set(list1) – set(list2) difference New set with values in list1 but not in li

Example:

For making a list unique

list(set([1, 2, 2, 3]))

Inner for-loops

Consider the following:

v1 = [0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0] * 10
v2 = [0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0] * 10

from time import time
t = time()
for n in range(5000):
	for i in range(len(v1)):
		for j in range(len(v2)):
			x = v1[i] + v2[j]
print("time running: {}".format(time() - t))

The algorithm takes 7.85634684563 seconds to run. It is a hypothetical example, but the point is this: we can make it faster by moving v1[i] outside of the inner loop:

t = time()
for n in range(5000):
	for i in range(len(v1)):
		temp = v1[i]
		for j in range(len(v2)):
			x = temp + v2[j]
print("time running: {}".format(time() - t))

Now it takes 6.6720559597 seconds.

Explanation: In the first implementation, we access v1[i] 5000x100x100 = 50.000.000 times. However, in the second one, we get element i in v1 once before over v2. This means we access v1[i] 5000×100 = 500.000 times only.

Move everything you can outside of the inner loop.


Lazy if-evaluation

Python’s if is lazily evaluated. This means that in: if x and y, condition y will not be tested if x is already False. We can exploit this by checking a fast condition first before checking a slow condition.

Looking this code:

from time import time

abbreviations = ['cf.', 'e.g.', 'ex.', 'etc.', 'fig.', 'i.e.', 'Mr.', 'vs.']
t = time()
for n in range(1000000):
	counter = 0
	for w in ('Mr.', 'Long', 'is', 'chasing', 'the', 'black', 'cat', '.'):
		if w in abbreviations:
			counter += 1
print("time running: {}".format(time()-t))

The algorithm takes 1.2804889679 seconds to run. However, since most of the words are not abbreviations we can optimize it by first checking if a word ends with a period, which is faster than iterating the list of known abbreviations

t = time()
for n in range(1000000):
	counter = 0
	for w in ('Mr.', 'Long', 'is', 'chasing', 'the', 'black', 'cat', '.'):
		if w[-1] == '.' and w in abbreviations:
			counter += 1
print("time running: {}".format(time()-t))

Now it takes 0.991156101227 second


String methods

Regular expressions in Python are fast because they are pushed back to C code. However, in many cases, simple string methods are even faster. Below is a list of interesting string methods. If you do use regular expressions, remember to add source code comments what they do.

Method Description
str[-1] == ‘x’ True if the last character is “x” (but Exception if len(str) == 0).
str.isalpha() True if the string only contains a-z | A-Z characters.
str.isdigit() True if the string only contains 0-9 characters.
str.startswith((‘x’, ‘yz’)) True if the first characters in the string are “x” or “yz”.
str.endswith((‘x’, ‘yz’)) True if the last characters in the string are “x” or “yz”.

 


String concatenation

Format strings are often faster than concatenating values to strings

'<feature term="' + 'cat' + '" weight="' + str(1.0) + '" />'
'<feature term="%s" weight="%s" />' % ('cat', 1.0) # Faster format string.

The second example is faster than the first one.


List comprehension

This code takes 6.6 seconds to finish

words = ['Mr.', 'Long', 'is', 'feeding', 'the', 'black', 'cat', '.']

for n in range(1000000):
    a = []
    for w in words:
        if w != '.': 
            a.append(w.lower())

However, this code takes only 5.3 seconds only.

for n in range(1000000):
    a = [w.lower() for w in words if w != '.']

If + None

if you would to check an object is None or not. The fastest way is

if an_object is not None:

The slower way is

if an_object != None:

the more slower way is

if not an_object:

Leave a Reply

Your email address will not be published. Required fields are marked *