Python list.clear() 时间和 space 复杂度？
Python list.clear() time and space complexity?
我正在写一篇关于 Python list.clear() 方法的博文，其中我还想提及底层算法的时间和 space 复杂性。我预计时间复杂度为 O(N)，遍历元素并释放内存？但是，我发现了一个 article，其中提到它实际上是一个 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)。另外，我发现了一个类似的问题here，但那里没有明确的答案。只想确认 list.clear() 的实际 时间和 space 复杂性 ，也许还有一些支持答案的解释。任何帮助表示赞赏。谢谢。
忽略内存管理是O(1)。说是O(N)的内存管理核算不太对，因为内存管理的核算很复杂。
大多数时候，出于大多数目的，我们将内存管理的成本与触发它的操作的成本分开处理。否则，几乎所有你可能做的事情都会变成 O（谁知道呢），因为几乎任何操作都可能触发垃圾收集过程或昂贵的析构函数或其他东西。哎呀，即使在像 C 这样具有 "manual" 内存管理的语言中，也不能保证任何特定的 malloc 或 free 调用都会很快。
有一种观点认为重新计数操作应该区别对待。毕竟，list.clear 显式执行了与列表长度相等的多个 Py_XDECREF 操作，即使没有对象被释放或最终确定，重新计数本身也必然会花费与列表长度成比例的时间列表。
如果计算 Py_XDECREF 操作 list.clear 显式执行，但忽略任何可能由重新计数操作触发的析构函数或其他代码，并且您假设 PyMem_FREE 是常数时间，那么 list.clear 是 O(N)，其中 N 是列表的原始长度。如果您不考虑所有内存管理开销，包括显式 Py_XDECREF 操作，则 list.clear 是 O(1)。如果计算所有内存管理成本，那么 list.clear 的运行时间不能渐近地受列表长度的任何函数限制。
正如您正确注意到的那样，list.clear 的 CPython 实现是 O(n)。 code 遍历元素以减少每个元素的引用计数，没有办法避免它。毫无疑问，这是一个 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, ...) 中的列表元素的 loop，这也非常有效 - 但很少会声称在开始时插入是 O(1)。 （并且 clear 可能会 more 起作用，因为 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) 并没有错——毕竟所有的对象引用都在一个连续的数组中，你只释放它一次。这就是您的博客 post 可能应该提出的观点，这也是链接文章试图表达的意思。过早考虑引用计数的成本可能会使您的读者感到困惑，并让他们对 Python 的列表产生完全错误的想法（例如，他们可能会认为它们是作为链表实现的）。
最后，在某些时候必须接受内存管理策略确实改变了一些操作的复杂性。例如，在C++中销毁一个链表，从调用者的角度来看是O(n)；在 Java 或 Go 中丢弃它是 O(1)。而不是在垃圾收集语言的琐碎意义上只是 postponing 相同的工作以备后用 - 移动收集器很可能只会遍历可到达的对象并且实际上永远不会访问丢弃的链表的元素.引用计数使得丢弃大型容器在算法上类似于手动收集，而 GC 可以将其删除。虽然 CPython 的 list.clear 必须接触每个元素以避免内存泄漏，但 PyPy 的垃圾收集器 never 很可能需要做任何事情排序，因此具有真正的 O(1) list.clear.
快速 time 检查表明它是 O(n)。
让我们执行以下操作并预先创建列表以避免开销：
import time
import random
list_1000000 = [random.randint(0,10) for i in range(1000000)]
list_10000000 = [random.randint(0,10) for i in range(10000000)]
list_100000000 = [random.randint(0,10) for i in range(100000000)]
现在检查清除这四个不同大小的列表所花费的时间如下：
start = time.time()
list.clear(my_list)
end = time.time()
print(end - start))
结果：
list.clear(list_1000000) takes 0.015
list.clear(list_10000000) takes 0.074
list.clear(list_100000000) takes 0.64
需要更稳健的时间测量，因为每次 运行 时这些数字都会出现偏差，但结果表明执行时间随着输入大小的增长几乎呈线性增长。因此我们可以得出 O(n) 的复杂性。
正如其他答案所指出的，清除长度为 n 的列表需要 O(n) 时间。但我认为这里还有一个关于 amortized 复杂性的额外观点。
如果您从一个空列表开始，并以任意顺序执行 N append 或 clear 操作，则总共 运行所有这些操作的时间始终为 O(N)，平均每次操作为 O(1)，无论列表在过程中有多长，无论这些操作中有多少是clear.
和clear一样，append的最坏情况也是O(n)次，其中n是列表的长度。那是因为当底层数组的容量需要增加时，我们必须分配一个新数组并将所有内容复制过来。但是复制每个元素的成本可以是 "charged" 到 append 操作之一，该操作使列表达到需要调整数组大小的长度，这样 N append 从空列表开始的操作总是需要 O(N) 时间。
同样，在 clear 方法中减少元素引用计数的成本可以是 "charged" 到首先插入该元素的 append 操作，因为每个元素都可以只被清除一次。结论是，如果您在算法中使用列表作为内部数据结构，并且您的算法在循环中反复清除该列表，那么为了分析算法的时间复杂度，您应该计算 clear列为 O(1) 操作，就像您在相同情况下将 append 算作 O(1) 操作一样。
我正在写一篇关于 Python list.clear() 方法的博文，其中我还想提及底层算法的时间和 space 复杂性。我预计时间复杂度为 O(N)，遍历元素并释放内存？但是，我发现了一个 article，其中提到它实际上是一个 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)。另外，我发现了一个类似的问题here，但那里没有明确的答案。只想确认 list.clear() 的实际 时间和 space 复杂性 ，也许还有一些支持答案的解释。任何帮助表示赞赏。谢谢。
忽略内存管理是O(1)。说是O(N)的内存管理核算不太对，因为内存管理的核算很复杂。
大多数时候，出于大多数目的，我们将内存管理的成本与触发它的操作的成本分开处理。否则，几乎所有你可能做的事情都会变成 O（谁知道呢），因为几乎任何操作都可能触发垃圾收集过程或昂贵的析构函数或其他东西。哎呀，即使在像 C 这样具有 "manual" 内存管理的语言中，也不能保证任何特定的 malloc 或 free 调用都会很快。
有一种观点认为重新计数操作应该区别对待。毕竟，list.clear 显式执行了与列表长度相等的多个 Py_XDECREF 操作，即使没有对象被释放或最终确定，重新计数本身也必然会花费与列表长度成比例的时间列表。
如果计算 Py_XDECREF 操作 list.clear 显式执行，但忽略任何可能由重新计数操作触发的析构函数或其他代码，并且您假设 PyMem_FREE 是常数时间，那么 list.clear 是 O(N)，其中 N 是列表的原始长度。如果您不考虑所有内存管理开销，包括显式 Py_XDECREF 操作，则 list.clear 是 O(1)。如果计算所有内存管理成本，那么 list.clear 的运行时间不能渐近地受列表长度的任何函数限制。
正如您正确注意到的那样，list.clear 的 CPython 实现是 O(n)。 code 遍历元素以减少每个元素的引用计数，没有办法避免它。毫无疑问，这是一个 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, ...) 中的列表元素的 loop，这也非常有效 - 但很少会声称在开始时插入是 O(1)。 （并且 clear 可能会 more 起作用，因为 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) 并没有错——毕竟所有的对象引用都在一个连续的数组中，你只释放它一次。这就是您的博客 post 可能应该提出的观点，这也是链接文章试图表达的意思。过早考虑引用计数的成本可能会使您的读者感到困惑，并让他们对 Python 的列表产生完全错误的想法（例如，他们可能会认为它们是作为链表实现的）。
最后，在某些时候必须接受内存管理策略确实改变了一些操作的复杂性。例如，在C++中销毁一个链表，从调用者的角度来看是O(n)；在 Java 或 Go 中丢弃它是 O(1)。而不是在垃圾收集语言的琐碎意义上只是 postponing 相同的工作以备后用 - 移动收集器很可能只会遍历可到达的对象并且实际上永远不会访问丢弃的链表的元素.引用计数使得丢弃大型容器在算法上类似于手动收集，而 GC 可以将其删除。虽然 CPython 的 list.clear 必须接触每个元素以避免内存泄漏，但 PyPy 的垃圾收集器 never 很可能需要做任何事情排序，因此具有真正的 O(1) list.clear.
快速 time 检查表明它是 O(n)。
让我们执行以下操作并预先创建列表以避免开销：
import time
import random
list_1000000 = [random.randint(0,10) for i in range(1000000)]
list_10000000 = [random.randint(0,10) for i in range(10000000)]
list_100000000 = [random.randint(0,10) for i in range(100000000)]
现在检查清除这四个不同大小的列表所花费的时间如下：
start = time.time()
list.clear(my_list)
end = time.time()
print(end - start))
结果：
list.clear(list_1000000) takes 0.015
list.clear(list_10000000) takes 0.074
list.clear(list_100000000) takes 0.64
需要更稳健的时间测量，因为每次 运行 时这些数字都会出现偏差，但结果表明执行时间随着输入大小的增长几乎呈线性增长。因此我们可以得出 O(n) 的复杂性。
正如其他答案所指出的，清除长度为 n 的列表需要 O(n) 时间。但我认为这里还有一个关于 amortized 复杂性的额外观点。
如果您从一个空列表开始，并以任意顺序执行 N append 或 clear 操作，则总共 运行所有这些操作的时间始终为 O(N)，平均每次操作为 O(1)，无论列表在过程中有多长，无论这些操作中有多少是clear.
和clear一样，append的最坏情况也是O(n)次，其中n是列表的长度。那是因为当底层数组的容量需要增加时，我们必须分配一个新数组并将所有内容复制过来。但是复制每个元素的成本可以是 "charged" 到 append 操作之一，该操作使列表达到需要调整数组大小的长度，这样 N append 从空列表开始的操作总是需要 O(N) 时间。
同样，在 clear 方法中减少元素引用计数的成本可以是 "charged" 到首先插入该元素的 append 操作，因为每个元素都可以只被清除一次。结论是，如果您在算法中使用列表作为内部数据结构，并且您的算法在循环中反复清除该列表，那么为了分析算法的时间复杂度，您应该计算 clear列为 O(1) 操作，就像您在相同情况下将 append 算作 O(1) 操作一样。