Why is l.insert (0, i) slower than l.append (i) in python?

Question

I tested two different ways to access a list in python.

import timeit value = [i for i in range(100)] def rev1(): v = [] for i in value: v.append(i) v.reverse() def rev2(): v = [] for i in value: v.insert(0, i) print timeit.timeit(rev1) print timeit.timeit(rev2) 

Interestingly, the second method, which inserts a value into the first element, is much slower than the first.

 20.4851300716 73.5116429329 

Why is this? From an operating point of view, inserting an element into the head does not seem so expensive.

Answer 1

insert is an O(n) operation, since it requires that all elements in the position or after the insertion position has been shifted by one. append , on the other hand, is usually O(1) (and O(n) in the worst case scenario where more space needs to be allocated). This explains the significant time difference.

The temporary difficulties of these methods are described in detail here .

I quote:

Internally, the list is represented as an array; the biggest costs grow beyond the current size of the placement (because everything should move), or from inserting or deleting somewhere near the beginning (because everything after that should move).

Now, returning to your code, we can see that rev1() is an implementation of O(n) , whereas rev2() is actually O(n 2 ) , so it makes sense that rev2() will be much slower.

Answer 2

In Python, lists are implemented as arrays. If you add one element to the array, the reserved space for the array simply expands. If you add an item, all items will shift by 1, and it will be very expensive.

Answer 3

you can confirm this by reading about python lists on the internet. Python implements the list as an array, where the size of the array is actually usually larger than the size of your current list. Unused items are at the end of the array and represent new items that can be added to the end of the list, and not to the beginning. Python uses a classic approach with amortized cost, so on average adding to the end of the list takes O (1) times if you make a bunch of additions, although sometimes one addition causes the array to become full, so a new larger array needs to be created. and all data will be copied to a new array. On the other hand, if you always insert at the beginning of the list, then in the base array you need to move all the elements at the same index to make room for a new element at the beginning of the array. So, to summarize, if you create a list by doing N attachments, then the total runtime will be O (N), if you always add new items to the end of the list, and that will be O (N ^ 2) if you always add to the beginning list.