shouldn't list comprehension be faster than for loops?

[Steven D'Aprano]

On Sat, 19 Dec 2009 12:28:32 +1100, Ryan Kelly wrote:

>> Anything else being equal, list comprehensions will be the faster
>> becuase they incur fewer name and attribute lookups. It will be the
>> same as the difference between a for loop and a call to map. A list
>> comprehension is basically an enhancement of map.
> 
> Not so.  If you use the "dis" module to peek at the bytecode generated
> for a list comprehension, you'll see it's very similar to that generated
> for an explicit for-loop.  The byte-code for a call to map is very
> different.

"Very similar" and "very different" byte-code mean very little regarding 
speed.


> Basically:  both a for-loop and a list-comp do the looping in python
> bytecode, while a call to map will do the actual looping in C.

This is a classic example of the confirmation fallacy -- if you say that 
for-loops and list-comps are very similar, you need to actually check the 
byte-code of both. You don't. You need to compare the byte-code of all 
three operations, not just two of them, e.g.:

dis.dis(compile("map(f, seq)", '', 'exec'))
dis.dis(compile("[f(x) for x in seq]", '', 'exec'))
dis.dis(compile("L = []\nfor x in seq: L.append(f(x))", '', 'exec'))

But in fact just looking at the byte-code isn't helpful, because it tells 
you nothing about the relative speed of each operation. You need to 
actually time the operations.

>>> from timeit import Timer
>>> t1 = Timer("map(len, 'abcdefgh')", setup='')
>>> t2 = Timer("[len(c) for c in 'abcdefgh']", setup='')
>>> t3 = Timer("""L = []
... for c in 'abcdefgh':
...     L.append(len(c))
... """, setup='')
>>>
>>> min(t1.repeat())
3.9076540470123291
>>> min(t2.repeat())
4.5931642055511475
>>> min(t3.repeat())
7.4744069576263428


So, on my PC, with Python 2.5, with this example, a for-loop is about 60% 
slower than a list comp and about 90% slower than map; the list comp is 
about 20% slower than map.

But that only holds for *that* example. Here's another one:


>>> def f(x):
...     return 1+2*x+3*x**2
...
>>> values = [1,2,3,4,5,6]
>>> t1 = Timer("map(f, values)", setup='from __main__ import f, values')
>>> t2 = Timer("[f(x) for x in values]", 
... setup='from __main__ import f, values')
>>> 
>>> t3 = Timer("""L = []
... for x in values:
...     L.append(f(x))
... """, setup='from __main__ import f, values')
>>>
>>> min(t1.repeat())
7.0339860916137695
>>> min(t2.repeat())
6.8053178787231445
>>> min(t3.repeat())
9.1957418918609619


For this example map and the list comp are nearly the same speed, with 
map slightly slower; but the for-loop is still significantly worse.

Of course, none of these timing tests are terribly significant. The 
actual difference in time is of the order of a millionth of a second per 
call to map compared to the list comp or the for-loop, for these small 
examples. Most of the time you shouldn't care about time differences of 
that magnitude, and write whatever is easiest.


-- 
Steven