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?
It is also important to realize that with append, the original list is simply modified. On the other hand, with concatenation, an entirely new list is created.
"Concatenate" joins two specific items together, whereas "append" adds what you specify to whatever may already be there.
String concatenation It can be a bit surprising, but this code actually runs in O(N2) time. The reason is that in Java strings are immutable, and as a result, each time you append to the string new string object is created.
Time Complexity for Append in Python This function has constant time complexity i.e. O(1), because lists are randomly accessed so the last element can be reached in O(1) time that's why the time taken to add the new element at the end of the list is O(1).
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]
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With