looping versus comprehension

Steven D'Aprano steve+comp.lang.python at pearwood.info
Thu Jan 31 06:17:32 CET 2013


On Thu, 31 Jan 2013 02:49:31 +1100, Chris Angelico wrote:

> it's worth
> noting that list appending is not going to be O(N*N), because it's going
> to allow room for expansion.

This is true for list.append, which is amortized constant time. But it is 
not true for list addition, alist + blist, which is O(N**2) and hence 
gets really, really slow:

steve at runes:~$ python -m timeit "L = []" "for i in xrange(1000): L = L + [1]"
100 loops, best of 3: 3.08 msec per loop
steve at runes:~$ python -m timeit "L = []" "for i in xrange(5000): L = L + [1]"
10 loops, best of 3: 71 msec per loop
steve at runes:~$ python -m timeit "L = []" "for i in xrange(25000): L = L + [1]"
10 loops, best of 3: 2.06 sec per loop


Notice that as the number of list additions goes up by a factor of 5, 
the time taken goes up by a factor of 25.

-- 
Steven



More information about the Python-list mailing list