Python list.clear 复杂性 [英] Python list.clear complexity
问题描述
Python 3 方法 list.clear() 的复杂度是多少?
What is the complexity of the Python 3 method list.clear() ?
在文档中，据说它与 <代码>删除a[:]，但我不知道这个函数本身的复杂程度.是它 O(n) 还是 O(1) ?
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) ?
我查看了 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)，但我不确定这是否是正确的代码.
Here it seems like O(n), but I am not sure if this is the right code.
我正在开发一个具有性能需求的程序，其中一个列表被反复填充和清空，我试图找到最好的方法来清空它(因为只有一种方法来填充它).
I am developing a program with performance needs, where a list is repeatedly filled and emptied, I am trying to find the best way to empty it (Since there is only one way to fill it).
如果这个函数是O(n)，我只会每次创建一个新列表，它有它自己的成本，但我不知道更好方式.
If this function is O(n), I will just create a new list every time, which has it's own cost, but I don't know a better way.
我想到的另一个问题是 Python 有一个垃圾收集器，所以如果我不释放这些对象(每次都创建新列表，通过重新分配变量名使另一个无人看管)，Python 会在后台进行删除(我不确定这个信息)，所以我不会提高应用上述任何方法的速度，因为结果是相同的.
Another issue crossed my mind is that Python has a garbage collector, so if I don't free these objects(create new lists every time, leaving the other unattended by reassigning the variable name), Python does the deletion in the background(I am not sure about this information), so I won't gain speed applying any of the methods above because result is the same.
任何知识都值得赞赏.谢谢.
Any knowledge is appreciated. Thanks.
推荐答案
您找到的函数与 Python 中的 list.clear() 无关.你需要的是_list_clear(PyListObject *a)，可以找到这里.
The function that you found is not related to list.clear() in Python. What you need is _list_clear(PyListObject *a), and it can be found here.
因此，如果您查看该方法的实现，则如下所示:
So, if you look into an implementation of that method, it looks as follows:
...
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;
}
...
然而，最重要的一行是检索列表大小的一行:
However, the most important lines are one, in which you're retrieving a size of a list:
i = Py_SIZE(a);
还有那些，你要删除一个元素:
And ones, in which you're removing an element:
...
while (--i >= 0) {
Py_XDECREF(item[i]);
}
...
由于Py_XDECREF 的性能不依赖于列表的大小，我们可以将其视为常数或 O(1).由于Py_XDECREF被称为列表时间的大小，所以整体时间复杂度是线性的，所以_list_clear的时间复杂度是O(n).
As performance of Py_XDECREF doesn't depend on the size of the list, we can consider it constant or O(1). Since Py_XDECREF is called size of list times, the overall time complexity is linear and so the time complexity of _list_clear is O(n).
正如@superbrain 所指出的，Py_XDECREF 可能会变得相当重"；对于某些元素(由于可能的递归调用)，虽然它与输入大小没有直接关系，但我们可以通过引入参数 e 来解释这一点 - 减少引用计数的总成本元素.在这种解释中，总时间复杂度为 O(n+e).
As pointed out by @superb rain, Py_XDECREF may turn quite "heavy" for some elements (due to possible recursive calls), and although it's not directly related to the input size, we can account for this by introducing a parameter e - the total cost of decreasing the reference counts of the elements. In this interpretation, the total time complexity is O(n+e).
这篇关于Python list.clear 复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
