在 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)内存。

此外，在Python 的解释器CPython [GitHub] 中，它.reverse()是在O(1)内存中完成的。事实上，如果我们查看reverse方法 [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，它被实现为 [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;
    }
}

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