CPython 是如何实现 pop(0) 的？

Question

考虑以下示例：

L = [1,2,3]
print(id(L))
L.pop(0)
print(id(L))

这输出：

1196816830600
1196816830600

pop(0) 从 L 中删除左侧元素。我不知道 CPython 如何在后台执行此操作并保持相同的 ID。但是我们可以从时间上看出它比 pop() 做了更多的工作。例如：

def popzero(L):
    for _ in range(10**4):
        L.pop(0)
        
def pop(M):
    for _ in range(10**4):
        M.pop()

L = [*range(10**6)]
%time popzero(L)
M = [*range(10**6)]
%time pop(M)

这给出：

Wall time: 13.2 s
Wall time: 997 µs

CPython 是否正在制作列表的新副本？如果是，它如何保持相同的 ID？还是将现有列表中的所有元素逐一移动？还是它在做别的事情？

Answer 1

我对 C 语言一无所知，但想分享我的见解，评论太长了。

那是 pop 实现。

如果 pop arg 是列表中的最后一个元素，它会调用 list_resize，这似乎并不太复杂。

    if (index == Py_SIZE(self) - 1) {
        status = list_resize(self, Py_SIZE(self) - 1);
        if (status >= 0)
            return v; /* and v now owns the reference the list had */
        else
            return NULL;

否则调用list_ass_slice。正好里面有评论

/* Because [X]DECREF can recursively invoke list operations on this list, we must postpone all [X]DECREF activity until after the list is back in its canonical shape. Therefore we must allocate an additional array, 'recycle', into which we temporarily copy the items that are deleted from the list. :-( */

我认为这是临时分配的性能损失所在。

Answer 2

您在问两个不同的问题。

为什么出栈前后列表ID一样？正如@Naman Chikara 在评论中解释的那样，这是因为即使对象发生变化，可变对象的 ID 也不会发生变化。
为什么 pop() 比 pop(0) 快很多？答案是here:

Here's my guess: pop() removes rightmost list element by shortening the length of the list by 1. pop(0) removes leftmost element by shifting the rest of the elements one place left and then shortening the length of the list by 1. It is the shifting that is taking a lot of time.

与许多语言一样，add/remove 数组右侧的项目比左侧更容易。

CPython 是如何实现 pop(0) 的？

How does CPython implement pop(0)?

python

cpython