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

Question

所以如果我写:

item_list = item_list[::-1]

这会是 O(1) 空间吗？我认为 item_list[::-1] 导致创建一个新列表，所以这可能是 O(n)。 item_list.reverse() 那么是在python中用 O(1) 空间反转的正确方法吗？

Answer 1

你说得对some_list[::-1]创建一个新列表，该列表将有 n 个“槽”，因此需要 O(n) 内存。

此外在 CPython [GitHub] ，Python 的解释器，.reverse()在 O(1) 内存中完成。事实上，如果我们看一下 reverse method [GitHub] ， 我们看:

/*[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] :

/* Reverse a slice of a list in place, from lo up to (exclusive) hi. */
static void
reverse_slice(PyObject **lo, PyObject **hi)
{
    assert(lo && hi);

    --hi;
    while (lo < hi) {
        PyObject *t = *lo;
        *lo = *hi;
        *hi = t;
        ++lo;
        --hi;
    }
}

因此它使用两个指针，一个按升序迭代，另一个按降序迭代，这些值相互“交换”，直到它们在中途相遇。