Python中dict.clear()的时间复杂度为O(1)是如何实现的？

Question

根据https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt，dict.clear()的时间复杂度为O(1)。据我所知，dict.clear()和dict = {}不同，因为dict.clear()会对同一个dict进行更改，而dict = {}会创建一个新的dict。现在，如果dict.clear()正在清除同一dict对象，那么它如何能够在O(1)内完成呢？

- Harsh Sharma

---

也许可以通过破坏内部数据结构并让垃圾回收器处理肮脏的非O(1)工作来实现。这不是循环遍历元素并逐个删除。 - Jean-François Fabre

PyDict_Clear 函数的实现可以在此处找到：https://github.com/python/cpython/blob/master/Objects/dictobject.c#L1636。 - timgeb

对我来说，for (i = 0; i < n; i++) Py_CLEAR(oldvalues[i]); 看起来并不像 O(1)…似乎我错了。 - Jean-François Fabre

有趣的是，这里没有讨论clear的复杂度。https://wiki.python.org/moin/TimeComplexity - Jean-François Fabre

Answer 1

一些声称其为O(1)的理由：

实际上，clear()方法只是将内部字典结构分配给新的空值（可以在源代码中看到）。看似O(n)的部分是因为减少引用计数和其他与GC相关的事情。但这纯粹是CPython使用的GC方法（即引用计数）的函数；你可以想象不同的方法，不需要像这样显式地清理，或者清理会发生得更晚（甚至被摊销掉）。由于理想情况下clear()方法的时间复杂度不应取决于底层GC方法，因此所有与GC相关的部分都被省略，使其变为“O(1)” 。在我看来，这主要是一个定义性的论点，但这至少是一些理由。

- arshajii

Answer 2

我最初认为dict.clear只是执行了一些引用减少操作，让垃圾收集器处理不干净的非O(1)工作，但是看了源代码（感谢提供链接的timgeb），似乎并不是这样的：

   oldvalues = mp->ma_values;
    if (oldvalues == empty_values)
        return;
    /* Empty the dict... */
    dictkeys_incref(Py_EMPTY_KEYS);
    mp->ma_keys = Py_EMPTY_KEYS;
    mp->ma_values = empty_values;
    mp->ma_used = 0;
    mp->ma_version_tag = DICT_NEXT_VERSION();
    /* ...then clear the keys and values */
    if (oldvalues != NULL) {
        n = oldkeys->dk_nentries;
        for (i = 0; i < n; i++)
            Py_CLEAR(oldvalues[i]);

我看到的是，如果字典有值，那么循环会逐渐减少这些值的引用，并将指针设置为NULL。因此，看起来是O(n)而不是O(1)，因为它取决于值的数量。

当您像这样分配一个新字典d = {}时，这是O(1)，但垃圾收集器必须在不再引用旧对象时删除它。除非Python突然退出，否则可能不正确。

- Jean-François Fabre