Python list.clear 复杂性

Question

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

• 这里没有给出： https : //wiki.python.org/moin/TimeComplexity

• 在文档中据说它与 等效del a[:]，但我不知道这个函数本身的复杂性。是O(n)还是O(1)？

• 我进去看了看listobject.c。找到了这个。

  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;
  }
  

  这里看起来像O(n)，但我不确定这是否是正确的代码。

我正在开发一个具有性能需求的程序，其中一个列表被反复填充和清空，我试图找到清空它的最佳方法（因为只有一种方法可以填充它）。

如果这个功能是O(n)，我每次都会创建一个新列表，它有自己的成本，但我不知道更好的方法。

我想到的另一个问题是 Python 有一个垃圾收集器，所以如果我不释放这些对象（每次都创建新列表，通过重新分配变量名让另一个无人看管），Python 在后台执行删除操作（我是不确定此信息），所以我不会提高应用上述任何方法的速度，因为结果是相同的。

任何知识表示赞赏。谢谢。

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)。