Python list comprehension expensive

Question

Im trying to find the effeciency of list comprehension but it look like its more expensive than a normal function operation. Can someone explain?

def squares(values):
    lst = []
    for x in range(values):
        lst.append(x*x)
    return lst

def main():
    t = timeit.Timer(stmt="lst = [x*x for x in range(10)]")
    print t.timeit()
    t = timeit.Timer(stmt="squares",setup="from __main__ import squares")
    print t.timeit()

    lst = [x*x for x in range(10)]
    print lst
    print squares(10)



----Output:---
2.4147507644
0.0284455255965
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

For the same output, the normal function calculates in very less time compared to the list comprehension.

I thought the list comprehension is more effecient.

The answers below explain your results - but it's worth noting the why the list comp is faster - the loop is performed at a lower level, which means it can be done more efficiently. — Gareth Latty, Jan 02 '13 at 15:35
@Lattyware: No, the loop is actually not the difference; it's the `.append()` call in the non-comp version that takes the speed. It needs to be looked up and called each time in the loop, and the list is grown for that one element each time. The comp can just build the list in one go. — Martijn Pieters, Jan 02 '13 at 15:40

Martijn Pieters · Answer 1 · 2013-01-02T15:52:18.773

You are never calling your squares function, so it is not doing anything.

List comprehensions are in fact faster:

>>> import timeit
>>> def squares(values):
...     lst = []
...     for x in range(values):
...         lst.append(x*x)
...     return lst
... 
>>> def squares_comp(values):
...     return [x*x for x in range(values)]
... 
>>> timeit.timeit('f(10)', 'from __main__ import squares as f')
3.9415171146392822
>>> timeit.timeit('f(10)', 'from __main__ import squares_comp as f')
2.3243820667266846

If you use the dis module to look at the bytecode for each function, you can see why:

>>> import dis
>>> dis.dis(squares)
  2           0 BUILD_LIST               0
              3 STORE_FAST               1 (lst)

  3           6 SETUP_LOOP              37 (to 46)
              9 LOAD_GLOBAL              0 (range)
             12 LOAD_FAST                0 (values)
             15 CALL_FUNCTION            1
             18 GET_ITER            
        >>   19 FOR_ITER                23 (to 45)
             22 STORE_FAST               2 (x)

  4          25 LOAD_FAST                1 (lst)
             28 LOAD_ATTR                1 (append)
             31 LOAD_FAST                2 (x)
             34 LOAD_FAST                2 (x)
             37 BINARY_MULTIPLY     
             38 CALL_FUNCTION            1
             41 POP_TOP             
             42 JUMP_ABSOLUTE           19
        >>   45 POP_BLOCK           

  5     >>   46 LOAD_FAST                1 (lst)
             49 RETURN_VALUE        
>>> dis.dis(squares_comp)
  2           0 BUILD_LIST               0
              3 LOAD_GLOBAL              0 (range)
              6 LOAD_FAST                0 (values)
              9 CALL_FUNCTION            1
             12 GET_ITER            
        >>   13 FOR_ITER                16 (to 32)
             16 STORE_FAST               1 (x)
             19 LOAD_FAST                1 (x)
             22 LOAD_FAST                1 (x)
             25 BINARY_MULTIPLY     
             26 LIST_APPEND              2
             29 JUMP_ABSOLUTE           13
        >>   32 RETURN_VALUE

The squares function looks up the .append() method of the list in each iteration, and calls it. The .append() function has to grow the list by one element each time it is called.

The list comprehension on the other hand doesn't have to do that work. Instead, python uses the LIST_APPEND bytecode, which uses the C API to append a new element to the list, without having to do the lookup and a python call to the function.

@SamueleMattiuzzo I deleted mine (no point having the same thing twice), so vote ahead on this one. — Gareth Latty, Jan 02 '13 at 15:34
AFAIK list comprehension are faster because operations are done in parallel — toutpt, Jan 02 '13 at 15:43
@toutpt: Where did you get *that* idea? It doesn't do anything in parallel. — Martijn Pieters, Jan 02 '13 at 15:43
@MartijnPieters taking out the time for an import - it's slower? By how much? — Jon Clements, Jan 02 '13 at 15:47
@JonClements: Using `def squares_map(values):\n values=range(values)\n return map(operator.mul, values, values)\n` it's competitive at 2.5397000312805176. The list comp still wins. — Martijn Pieters, Jan 02 '13 at 15:48
@MartijnPieters -- Now how does the timing compare if you make `values` a large number reducing the penalty of looking up `map` (which the list-comprehension gets to avoid because of it's special syntax)? If speed is really the only concern, you can also reduce the penalty of looking up `operator.mul`, but these optimizations are rarely useful... — mgilson, Jan 02 '13 at 15:51
As a side note, I would prefer the list comprehension in this case for ease of reading compared to a multi-argument `map` which seems to be a python idiom which isn't very commonly used. — mgilson, Jan 02 '13 at 15:53
@mgilson: For larger numbers of `value`, the list comp is only getting faster, I'm afraid. The `operator.mul` lookup is only done *once* for each function call, it doesn't matter much if I bind that to a global name `map` first. — Martijn Pieters, Jan 02 '13 at 15:55
@MartijnPieters in my memory (was sure to have read it on the web long time ago) but I'm wrong. — toutpt, Jan 02 '13 at 16:47

Python list comprehension expensive

1 Answers1

Linked

Related