Optimisations with python data structure generation
This post explores some of the differences in using list comprehensions and generator expressions to build lists in Python. We are going to look at the memory and CPU performance using various Python profiling tools and packages.
Firstly a list comprehension can be built in python using:
which constructs the list for every item in
somedata. The list comprehension may also be built out of a function that returns an item on return, e.g.
[x for x in somefunc()]. The important thing to note in list comprehensions is that the whole list is evaluated at once, this is in contrast to the generator expression which is “short-circuiting” and will exit early if the expression permits it so. Generators can be a useful alternative where an algorithm is likely to finish early if certain conditions are met. For example:
In the case of the list comprehension the entire list is evaluated first, and then run through the
any() function. In the generator case, the
any() test is evaluated every iteration of somefunc(), and if it returns true the any test can return early without having to build the entire list.
In theory then, generator expressions offer a potential performance benefit compared to their list comprehension counterparts. But how does it play out in practice?
We’re going to use an example that builds lists of random strings. Here’s a function that returns a random string:
Now we need a function that builds the lists using each method. First the list comprehension way:
And now a function that uses the generator approach:
Let’s also create some functions for testing ints, just to see if there is any difference with the data type.
Now we are going to test these methods with the
timeit command, built in to the python interpreter. Using IPython, this can be run using the command:
%timit [FUNCTION_NAME(ARGS)]. Help for this command is accessed with
Using our integer list building methods:
So, it would appear at first approximation, the generator approach is slower, at least for building a list of integers this size.
Now let’s investigate the impact on memory use. Memory use is tricky to measure in Python, as objects can have a deeply nested structure, making it diffcult to fully trace the memory footprint of objects. The python interpreter also performs garbage collection atcertain intervals, meaning it can be difficult to reproduce tests of memory consumption.
First we’re going to use the built in
Interestingly, the generator performs better in most cases, execpt for the smallest example with eight strings. With larger lists than this, the generator approach consistently outperforms the list comprehension method in terms of its memory footpring, when building lists of strings and measuring with the
The pympler package is reportedly more accurate at deteriming the true memory footprint of a Python object. USing the
asizeof() method with the same tests as above, we get:
Another option is the
memory_profiler package. This provides another IPython magic command:
%memit, which can be used like so:
asizeof() says the list comprehension is bigger,
memory_profiler says the generator sees the bigger memory footprint…TBC