Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Difference in complexity of append and concatenate for this list code?

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?

like image 849
garg10may Avatar asked Oct 17 '15 20:10

garg10may


People also ask

What is the difference between append with list and concatenation with lists?

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.

What is the difference between append and concatenate?

"Concatenate" joins two specific items together, whereas "append" adds what you specify to whatever may already be there.

What is the time complexity of concatenation?

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.

What is the time complexity of list append in Python?

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).


1 Answers

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]
like image 177
Martijn Pieters Avatar answered Sep 24 '22 15:09

Martijn Pieters