为什么对于 bytearray 来说 b.pop(0) 比 del b[0] 慢 200 多倍？

Question

让他们竞争 3 次（每次 100 万次弹出/删除）：

\n

from timeit import timeit\n\nfor _ in range(3):\n    t1 = timeit(\'b.pop(0)\', \'b = bytearray(1000000)\')\n    t2 = timeit(\'del b[0]\', \'b = bytearray(1000000)\')\n    print(t1 / t2)\n

\n

时间比例（在线尝试！）：

\n

274.6037053753368\n219.38099365582403\n252.08691226683823\n

\n

为什么pop做同样的事情要慢得多？

\n

Answer 1

当您运行 时b.pop(0)，Python 将按照您的预期将所有元素向后移动 1。这需要 O(n) 时间。

当你这样做时del b[0]，Python只是将对象的起始指针加1。

在这两种情况下，PyByteArray_Resize都会调用调整大小。当新大小小于已分配大小的一半时，分配的内存将收缩。在这种del b[0]情况下，这是复制数据的唯一点。因此，这种情况将花费 O(1) 摊余时间。

相关代码：

bytearray_pop_impl功能：总是调用

memmove(buf + index, buf + index + 1, n - index);

该bytearray_setslice_linear函数del b[0]通过lo == 0, hi == 1,来调用bytes_len == 0。它到达此代码（带有growth == -1）：

if (lo == 0) {
    /* Shrink the buffer by advancing its logical start */
    self->ob_start -= growth;
    /*
      0   lo               hi             old_size
      |   |<----avail----->|<-----tail------>|
      |      |<-bytes_len->|<-----tail------>|
      0    new_lo         new_hi          new_size
    */
}
else {
    /*
      0   lo               hi               old_size
      |   |<----avail----->|<-----tomove------>|
      |   |<-bytes_len->|<-----tomove------>|
      0   lo         new_hi              new_size
    */
    memmove(buf + lo + bytes_len, buf + hi,
            Py_SIZE(self) - hi);
}

Answer 2

我必须承认，我自己对这个时间安排感到非常惊讶。在说服自己它们实际上是正确的之后，我深入研究了 CPython 源代码，我想我找到了答案 - cpythondel bytearr[0:x]通过仅增加指向数组开头的指针来优化：

    if (growth < 0) {
        if (!_canresize(self))
            return -1;

        if (lo == 0) {
            /* Shrink the buffer by advancing its logical start */
            self->ob_start -= growth;

您可以在此处找到del bytearray[...]逻辑（通过和being实现），该逻辑又调用，其中包含上述优化。bytearray_setslicevaluesNULLbytearray_setslice_linear

为了进行比较，bytearray.pop 没有实现此优化 - 请参阅此处的源代码。