Python list.clear() 时间和空间复杂度？

Question

我正在写一篇关于 Pythonlist.clear()方法的博文，其中我还想提到底层算法的时间和空间复杂度。我预计时间复杂度为O(N)，迭代元素并释放内存？但是，我发现一篇文章提到它实际上是一个O(1)操作。然后，我在 CPython 实现中搜索了该方法的源代码，找到了一个我认为是 的实际内部实现的方法list.clear()，但是，我不确定它是。下面是该方法的源代码：

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

我可能是错的，但对我来说它看起来像O(N)。另外，我在这里发现了一个类似的问题，但那里没有明确的答案。只是想确认实际时间和空间复杂的list.clear()，也许有点解释配套的答案。任何帮助表示赞赏。谢谢。

Answer 1

正如您正确注意到的，CPython 的实现list.clear是 O(n)。的代码遍历的元素，以便减少每一个的引用计数，没有一种方法来避免它。毫无疑问，这是一个 O(n) 操作，并且，给定一个足够大的列表，您可以测量花费的时间clear()作为列表大小的函数：

import time

for size in 1_000_000, 10_000_000, 100_000_000, 1_000_000_000:
    l = [None] * size
    t0 = time.time()
    l.clear()
    t1 = time.time()
    print(size, t1 - t0)

输出显示线性复杂度；在我使用 Python 3.7 的系统上，它打印以下内容：

1000000 0.0023756027221679688
10000000 0.02452826499938965
100000000 0.23625731468200684
1000000000 2.31496524810791

每个元素的时间当然很小，因为循环是用 C 编码的，每次迭代都做很少的工作。但是，正如上面的测量结果所示，即使是很小的每个元素因素最终也会加起来。小的每元素常量不是忽略操作成本的原因，或者同样适用于将列表元素移入 的循环l.insert(0, ...)，这也非常有效 - 但很少有人会声称在开头插入是 O (1). （并且clear可能会做更多的工作，因为 decref 将为引用计数实际上为零的对象运行任意的析构函数链。）

在哲学层面上，人们可能会争辩说，在评估复杂性时应该忽略内存管理的成本，否则就不可能确定地分析任何事情，因为任何操作都可能触发 GC。这个论点是有道理的；GC 确实偶尔且不可预测地出现，其成本可以考虑在所有分配中摊销。类似地，复杂度分析往往会忽略复杂度，malloc因为它所依赖的参数（如内存碎片）通常与分配大小甚至与已分配块的数量没有直接关系。但是，如果list.clear只有一个分配的块，则不会触发 GC，并且代码仍在访问每个列表元素。即使假设 O(1) malloc 和摊销 O(1) GC，list.clear 仍然需要与列表中元素数量成正比的时间。

从问题链接的文章是关于 Python 语言的，并没有提到特定的实现。不使用引用计数的 Python 实现（例如 Jython 或 PyPy）可能具有真正的 O(1) list.clear，并且对它们而言，文章中的声明是完全正确的。所以，在概念层面解释 Python 列表时，说清除列表是 O(1) 并没有错——毕竟，所有对象引用都在一个连续的数组中，你只释放一次。这是您的博客文章可能应该提出的观点，这就是链接文章想要表达的意思。过早考虑引用计数的成本可能会使读者感到困惑，并让他们对 Python 的列表产生完全错误的想法（例如，他们可以想象它们是作为链表实现的）。

最后，在某些时候，人们必须接受内存管理策略确实会改变某些操作的复杂性。例如，在 C++ 中销毁链表从调用者的角度来看是 O(n)；在 Java 或 Go 中丢弃它是 O(1)。并且不是垃圾收集语言只是将相同的工作推迟到以后的琐碎意义上 - 移动收集器很可能只会遍历可达对象并且确实永远不会访问丢弃链表的元素。引用计数使得丢弃大型容器在算法上类似于手动收集，而 GC 可以将其删除。虽然 CPythonlist.clear必须接触每个元素以避免内存泄漏，但 PyPy 的垃圾收集器很可能永远不会需要做任何事情，因此有一个真正的 O(1) list.clear。