What is the complexity of the Python 3 method list.clear() ?

• It is not given here: https://wiki.python.org/moin/TimeComplexity

• 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) ?

• I took a look in listobject.c. Found this.

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

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

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.

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.

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 onthis 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 emptyat 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]);}
...

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

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