2

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)
Conner M.
  • 1,954
  • 3
  • 19
  • 29
  • You were told a fairy tale. Python lists are efficient in adding and removing elements at any position. – Klaus D. Aug 17 '20 at 05:40

2 Answers2

6

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.

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
  • Popping the first element should be trivial as well, since you can just move up the pointer by one "slot" to already allocated memory. – Jan Christoph Terasa Aug 17 '20 at 05:47
  • 1
    @Jan: what it *can* do and what it *does* do appear to be two different things. – paxdiablo Aug 17 '20 at 05:49
  • See also https://wiki.python.org/moin/TimeComplexity This is what is officially stated, and it says O(k), with k being the argument. – Jan Christoph Terasa Aug 17 '20 at 05:50
  • This is the way it was originally explained to me. – Conner M. Aug 17 '20 at 06:04
  • Apparently, after some testing, the information in the wiki is wrong, and it should state O(n-k) in the wiki, since it is as you say moving the whole array (n-1) in case of `.pop(0)`, but only 1 element in case of `.pop(len(l)-1))`. This can be confirmed by some quick time testing. – Jan Christoph Terasa Aug 17 '20 at 06:05
  • 1
    @Jan, that table not very good use of the complexity metric. Since it's supposed to represent the effort required based on some input, `k` is the wrong argument (since it relies on both `k` *and* the list size `n`). `O(n-k)` might be better but it's really `O(n)`. – paxdiablo Aug 17 '20 at 06:06
  • @paxdiablo Thanks for clarifying. I am thinking now how to improve the table in the wiki, since is the first thing you stumble upon when searching for the time complexity of operations, and if the information contradicts the *actual* source code, having such a page is not very helpful indeed, since you still have to look up the implementation, anyway. – Jan Christoph Terasa Aug 17 '20 at 06:10
  • 1
    @Jan, I'd consider getting rid of the `k` altogether in at least some of those. They seem to more indicate execution time based on size and where you're deleting, rather than time complexity - in CompSci, the latter is really how the *data size* affects the time taken. A useful estimation rule of thumb is to average the running time over *all* values of `k`, and you'll still see that it increases linearly with `n`. – paxdiablo Aug 17 '20 at 06:16
  • 1
    I created an account for the wiiki and am writing a mail to the staff. The statement in the wiki says __"The Average Case assumes parameters generated uniformly at random.__", so to me that would mean any value for k has equal probability, and thus the average case is `.pop(len(l)/2)`, which is O(n/2) = O(n). – Jan Christoph Terasa Aug 17 '20 at 06:31
  • 1
    @paxdiablo Done: https://wiki.python.org/moin/TimeComplexity – Jan Christoph Terasa Aug 18 '20 at 05:24
0

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.

tdelaney
  • 73,364
  • 6
  • 83
  • 116