26

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?

Improve this question
0

2 Answers 2

Reset to default
20

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]
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Note that += [1] is more like extending; under the hood it uses listobj.extend([1]) in that case.
It's still creating a new list right? Only a list of one element on the RHS. I guess that's why append is still faster.
12

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.

Improve this answer

5 Comments

I'm confused, I learned in functional programming languages such as Haskell that "append" DOES build a new list object each time, so is this meaning specific to Python then?
@GabbyQuattrone that’s behaviour specific to functional languages, where types are never mutable. Mutability is not specific to Python; loads of other languages behave the same.
Why do they not call it cons for construct like in LISP then, if it means adding one item to an existing list?
@GabbyQuattrone: I don't know, you'd have to ask a functional programming expert that question.
@knowledge_is_power because the naming conventions of Haskell and Lisp don't have much bearing on Python, which is in a separate lineage of programming languages. In Haskell, nothing is ever mutated.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.