22

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
  • 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
    Commented Jul 30, 2018 at 3:58

1 Answer 1

39

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
    Commented Oct 17, 2015 at 20:58
  • @garg10may: no, it's not. See my timings. Commented 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. Commented Oct 17, 2015 at 21:00
  • 4
    @garg10may: list.append() is absolutely the best approach for adding a single element, no doubt about it. Commented 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. Commented Oct 17, 2015 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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