Python列表清空的复杂度

Question

Python 3方法list.clear()的复杂度是什么？

• It is not given here: https://wiki.python.org/moin/TimeComplexity

• In the documentation it is said to be equivalent with del a[:], but I do not know the complexity of this function itself. Is it O(n) or O(1) ?

• I took a look in listobject.c. Found this.

  int
  PyList_ClearFreeList(void)
  {
      PyListObject *op;
      int ret = numfree;
      while (numfree) {
          op = free_list[--numfree];
          assert(PyList_CheckExact(op));
          PyObject_GC_Del(op);
      }
      return ret;
  }
  

  Here it seems like O(n), but I am not sure if this is the right code.

我正在开发一个有性能需求的程序，其中一个列表需要反复填充和清空。我正在尝试找到最好的清空方式（因为只有一种填充方式）。

如果这个函数是O(n)，那么我会每次创建一个新的列表，虽然这有一定的成本，但我不知道更好的方法。

另一个问题是Python有垃圾收集器，所以如果我不释放这些对象（每次创建新的列表，通过重新分配变量名来忽略旧列表），Python会在后台进行删除（我对此信息不确定），因此我不会因为应用上述任何方法而获得速度提升，因为结果是相同的。

非常感谢您的帮助。

- Rockybilly

Answer 1

你找到的函数与 Python 中的 list.clear() 没有关系。你需要的是 _list_clear(PyListObject *a)，你可以在 这里 找到它。

因此，如果你查看该方法的实现，它应该如下所示：

...
static int
_list_clear(PyListObject *a)
{
    Py_ssize_t i;
    PyObject **item = a->ob_item;
    if (item != NULL) {
        /* Because XDECREF can recursively invoke operations on
           this list, we make it empty first. */
        i = Py_SIZE(a);
        Py_SIZE(a) = 0;
        a->ob_item = NULL;
        a->allocated = 0;
        while (--i >= 0) {
            Py_XDECREF(item[i]);
        }
        PyMem_FREE(item);
    }
    /* Never fails; the return value can be ignored.
       Note that there is no guarantee that the list is actually empty
       at this point, because XDECREF may have populated it again! */
    return 0;
}
...

然而，最重要的一行是你检索列表大小的那一行：

i = Py_SIZE(a);

还有一种情况是，你需要移除一个元素：

...
    while (--i >= 0) {
        Py_XDECREF(item[i]);
    }
...

由于Py_XDECREF的性能不取决于列表的大小，因此我们可以将其视为常数或O(1)。由于Py_XDECREF被调用了列表大小次，因此总体时间复杂度是线性的，因此_list_clear的时间复杂度为O(n)。

正如@superb rain所指出的那样，对于某些元素来说，Py_XDECREF可能会变得非常“沉重”（由于可能存在递归调用），尽管它与输入大小没有直接关系，但我们可以通过引入参数e来解决这个问题-减少元素引用计数的总成本。在这种解释下，总时间复杂度为O(n+e)。

- Anatolii