在python中使用[::-1]来反转O(1)列表空间吗?

问题描述 投票:1回答:1

所以,如果我写了:

item_list = item_list[::-1]

这将是O(1)空间吗?我认为item_list [::-1]会导致创建新列表,因此可能是O(n)。是item_list.reverse()然后是在python中使用O(1)空间进行反转的正确方法吗?

python python-3.x list time-complexity reverse
1个回答
0
投票

您是对的,some_list[::-1]创建一个new列表,并且该列表将具有n个“槽”,因此需要O(n)个内存。

此外,在CPython [GitHub]中,它是Python的解释器,.reverse()O(1)内存中完成。确实,如果我们查看reverse method [GitHub],我们将看到:

reverse

因此调用了函数/*[clinic input] list.reverse Reverse *IN PLACE*. [clinic start generated code]*/ static PyObject * list_reverse_impl(PyListObject *self) /*[clinic end generated code: output=482544fc451abea9 input=eefd4c3ae1bc9887]*/ { if (Py_SIZE(self) > 1) reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self)); Py_RETURN_NONE; }

reverse_slice, and this is implemented as [GitHub]

因此,它与两个指针一起工作,一个指针以升序迭代,一个指针以降序迭代,并且这些“交换”值相互之间,直到它们在中间相遇为止。

© www.soinside.com 2019 - 2024. All rights reserved.