Python concatenation vs append speed on lists

Question

Taking this snippet from interactivepython.org:

def test1():  # concat
    l = []
    for i in range(1000):
        l = l + [i]

def test2():  # append
    l = []
    for i in range(1000):
        l.append(i)

---

concat  6.54352807999 milliseconds
append  0.306292057037 milliseconds

Where the bottom block is the run time.

It says concatenation is O(k), where k is the "length of the list being concatenated". I'm not sure if this means the list you are adding to (original), or the list you are going to be adding. But in both these loops it seems like you are just performing 1 step per iteration. So why is append so much faster?

Answer 1

If you change test1 to:

def test1():  # concat
    l = []
    for i in range(1000):
        l += [i] 

the times will be much closer and you are actually doing what append is doing not creating a new list each time.

In [26]: %timeit test1()
10000 loops, best of 3: 169 µs per loop

In [27]: %timeit test2()
10000 loops, best of 3: 115 µs per loop

If you put print id in your code you will see in test1 you are creating a new object each time but in test2 it is always the same list:

In [41]: test1()
139758194625352
139758206001808
139758205966960
139758194625352
139758206001808
139758205966960
139758194625352
139758206001808
139758205966960
139758194625352
Out[41]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

In [42]: test2()
139758206002600
139758206002600
139758206002600
139758206002600
139758206002600
139758206002600
139758206002600
139758206002600
139758206002600
139758206002600
Out[42]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Answer 2

Because the concatenation has to build a new list object each iteration:

Creating a new list each time is much more expensive than adding one item to an existing list.

Under the hood, .append() will fill in pre-allocated indices in the C array, and only periodically does the list object have to grow that array. Building a new list object on the other hand has to allocate a C array each and every time.