21

Consider below methods for forming a list of thousand 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 is the append method around 20 times better than concatenation. AFAIK append has O(1) complexity while concatenation has O(k) complexity. While K here is 1.

Is there some obvious thing I overlooked?

1
  • Due to the mistake in the code, this question is not as general as the original title ("...for lists") would suggest, and thus it should not be canonical.
    – smci
    Jul 30, 2018 at 3:58

1 Answer 1

37

You are creating a new list object each time by concatenating. This requires copying all elements from the old list into a new one, plus one extra. So yes, using l = l + [i] is an O(N) algorithm, not O(1).

At the very least, don't use + concatenation; use += augmented concatenation, which is the same thing as list.extend() with a re-assignment to the same reference:

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

This produces:

>>> 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]
7
  • still it's taking [0.047872320772834216, 0.04017255103519537] about 2 times than append.
    – garg10may
    Oct 17, 2015 at 20:58
  • @garg10may: no, it's not. See my timings.
    – Martijn Pieters
    Oct 17, 2015 at 20:58
  • 5
    @garg10may: and O(1) is a class of performance, not a precise measurement; the constant time between different O(1) algorithms can still vary.
    – Martijn Pieters
    Oct 17, 2015 at 21:00
  • 4
    @garg10may: list.append() is absolutely the best approach for adding a single element, no doubt about it.
    – Martijn Pieters
    Oct 17, 2015 at 21:02
  • 6
    @garg10may: += has to do more work; it has to resize the existing object by a variable number of elements, so there is a loop involved. .append() knows there is always 1 element more to be added, simplifying the logic.
    – Martijn Pieters
    Oct 17, 2015 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.