The difference in the complexity of adding and concatenating lists

Question

Consider below the methods of forming a list of thousands of numbers.

def test1(): l = [] for i in range(1000): l = l + [i] return l def test2(): l = [] for i in range(1000): l.append(i) print timeit.repeat(stmt=test1, number=100,repeat=2) print timeit.repeat(stmt=test2, number=100,repeat=2) 

Output:

 [0.30474191033602543, 0.3783786557587963] [0.015134341605235302, 0.023081246200096328] 

Why the append method is about 20 times better than concatenation. AFAIK append has complexity O (1), while concatenation has complexity O (k). While K is here 1.

Is there an obvious thing that I forgot?

Answer 1

Each time you create a new list object by concatenating. This requires copying all the items from the old list to the new one, plus one additional one. So yes, using l = l + [i] is an O (N) algorithm, not O (1).

At least do not use concatenation + ; use += extended concatenation, which is the same as list.extend() with reassignment to the same link:

 def test3(): l = [] for i in range(1000): l += [i] # or use l.extend([i]) return l 

This gives:

 >>> print timeit.repeat(stmt=test1, number=100, repeat=2) [0.1333179473876953, 0.12804388999938965] >>> print timeit.repeat(stmt=test2, number=100, repeat=2) [0.01052403450012207, 0.007989168167114258] >>> print timeit.repeat(stmt=test3, number=100, repeat=2) [0.013209104537963867, 0.011193037033081055]