What are effects on overhead of using list.pop(0)?

user_7332065 0
Viewed 297

Early on in my exploration of Python, I remember being told that using pop on the first element of a list wasn't necessarily bad practice, but was less than optimal. The reason that was given was that basically a new list had to be formed to be able to re-index all of the remaining elements. This doesn't appear to be the case, however:

test_list = [1, 2, 3, 4, 5]

hex(id(test_list))
Out[29]: '0x17d5b172f48'

test_list.pop(0)
Out[30]: 1

hex(id(test_list))
Out[31]: '0x17d5b172f48'

Nonetheless, I'm still wordering if there is some overhead to reassigning indices to the remaining elements, or if there is some other cost to popping from any other element but the last.

EDIT

Honestly, the difference between popping the last and first element does not look all that trivial when working with large lists:

test_list = list(range(int(1e6)))
%timeit test_list.pop(0)

671 µs ± 26 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

test_list = list(range(int(1e5)))
%timeit test_list.pop(0)

The slowest run took 5.01 times longer than the fastest. This could mean that an intermediate result is being cached.
17.3 µs ± 7.91 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

test_list = list(range(int(1e8)))
%timeit test_list.pop()

91.7 ns ± 0.821 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
list python
2 Answers

If you look into the actual pop code in cpython/Objects/listobject.c, you'll see there are memcpy/memmove calls for the case where you're not popping the last element (it's actually done in the call to list_ass_slice).

Hence, it's not a non-trivial expense (certainly not O(1) as suggested in a comment - that may be true for a linked-list type structure but that's not what Python lists are). It's the fact that it's doing the element removal in-place that means that the id won't change but that doesn't mean it's efficient.

For example, consider the list:

    0    1     2     3     4     5     <- index
+-----+-----+-----+-----+-----+-----+
|  A  |  B  |  C  |  D  |  E  |  F  |
+-----+-----+-----+-----+-----+-----+

Popping the last element is usually an O(1) operation since it simply needs to take out F and reduce the size.

However, popping the first element means taking out A and then moving all the elements B..F to the position where A was:

    0    1     2     3     4     <- index
+-----+-----+-----+-----+-----+
|  B  |  C  |  D  |  E  |  F  |
+-----+-----+-----+-----+-----+

But keep in mind it probably won't matter unless your lists get really big. The objects themselves aren't being reconstructed since the list only holds references to them.

user_148600

The list has a buffer that holds references to its values. After pop(0), the remaining references need to be copied down one in this buffer. If you happen to pass certain thresholds a smaller buffer will be allocated and the references will be copied there.

Unless the list is large, it doesn't make much of a difference. If the list is large and you do a lot of pop(0), perhaps reversing it and doing pop() from the end would make sense.

user_6420700
Related