Python list.pop()深入

背景

​ 在一次处理Python中List长度为5W+的特殊场景中，发现函数执行时间很长，大概花费了8秒，明显与平时的执行时间存在较大差距（几乎是毫秒级别）。通过Debug后发现具体耗时较多的代码如下：

while len(nums) > 0:
	first_num = nums.pop(0)		# 最终定位到原因在该行代码
  # 对 first_num 进行一系列的处理
  ...

通常情况下，调用pop()与pop(-1)的时间复杂度都为1，但pop(N) （0<=N<len(list)-1）的时间复杂度却是 N。所以硬生生的把一个原本时间复杂度只有O(n)的变成了O(n²)。

实验

通过下方的实验来确认下pop(0)、pop()与通常的索引取值的性能差距。

# compute_consume_time 是自己自定义的一个函数执行耗时的装饰器
@compute_consume_time()
def list_pop_head(test_list):
    while len(test_list) > 0:
        b = test_list.pop()

@compute_consume_time()
def list_index_head(test_list):
    i = 0
    while i < len(test_list):
        b = test_list[i]
        i += 1

对于上述的两个函数进行不同长度的test_list参数传入后的实验结果如下（未进行多次取平均值，耗时会存在一定的误差）：

# len(test_list) = 10
==== begin list_pop_head===== 
current Func [list_pop_head] run time is 3.814697265625e-05
==== begin list_index_head===== 
current Func [list_index_head] run time is 3.814697265625e-06

# len(test_list) = 10000
==== begin list_pop_head===== 
current Func [list_pop_head] run time is 0.008320093154907227
==== begin list_index_head===== 
current Func [list_index_head] run time is 5.245208740234375e-06

# 当len(test_list) = 500000
==== begin list_pop_head===== 
current Func [list_pop_head] run time is 23.494240045547485
==== begin list_index_head===== 
current Func [list_index_head] run time is 4.76837158203125e-06

# 当len(test_list) = 500000，将 pop(0) 替换为 pop(-1)或pop()后的耗时
current Func [list_pop_last_head] run time is 0.09693312644958496

通过上述实验可以得出如下结论：

• 在处理List长度为50W的场景时，pop(0)的性能已经比直接通过索引的方式差了将近500W倍（23.49/4.76e-06），
• 在处理List长度为50W的场景时，pop(0)比pop()或者pop(-1)的性能也差了将近242倍（23.49/0.0969）。

原来也没去研究过pop内部的原理，所以一直误以为pop()的时间复杂度都是1。┑(￣。。￣)┍

pop 实现原理

由于pop是内置函数，通过c实现的，具体的实现代码 cPython3.7如下：

/*[clinic input]
list.pop
    index: Py_ssize_t = -1
    /
Remove and return item at index (default last).
Raises IndexError if list is empty or index is out of range.
[clinic start generated code]*/

static PyObject *
list_pop_impl(PyListObject *self, Py_ssize_t index)
/*[clinic end generated code: output=6bd69dcb3f17eca8 input=b83675976f329e6f]*/
{
    PyObject *v;
    int status;

    if (Py_SIZE(self) == 0) {
        /* Special-case most common failure cause */
        PyErr_SetString(PyExc_IndexError, "pop from empty list");
        return NULL;
    }
    if (index < 0)
        index += Py_SIZE(self);
    if (index < 0 || index >= Py_SIZE(self)) {
        PyErr_SetString(PyExc_IndexError, "pop index out of range");
        return NULL;
    }
    v = self->ob_item[index];
    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;
    }
    Py_INCREF(v);
    status = list_ass_slice(self, index, index+1, (PyObject *)NULL);
    if (status < 0) {
        Py_DECREF(v);
        return NULL;
    }
    return v;
}

从代码中可以得出以下几个点：

• 默认情况下, pop() 的默认值是-1，所以pop() 等同于 pop(-1)；
• 调用pop()时传入的参数为i（即是后面条件判断中的index的值），如果满足 index == Py_SIZE(self) - 1，代码就直接走 list_resize() 结束了整个函数；
• 否则代码会通过 list_ass_slice() 方法。（emm，尝试了下去看该方法然而碰壁了，有点多没太看懂😂）

网上查了一些解释（个人猜测：pop本质上是调用了list_ass_slice才会存在时间复杂度从 1 => N。）：

pop(0) is slower than pop():
When pop is called on the end of the list it takes O(1) but when pop is called on the first element in the list or anywhere in the middle it is O(n). The reason for this lies in how Python chooses to implement lists. When an item is taken from the front of the list, in Python’s implementation, all the other elements in the list are shifted one position closer to the beginning. This may seem silly to you now, but if you look at Table 2 you will see that this implementation also allows the index operation to be O(1). This is a tradeoff that the Python implementors thought was a good one.

总结

​ 在平常使用库函数的时候也要注意去了解下自己常用的库函数的时间复杂度，否则可能由于不恰当的使用方式而导致整个代码存在明显的性能瓶颈。