Использует ли [:: - 1] в python для обращения к списку O (1) пробел? - PullRequest
Новая
       14

Использует ли [:: - 1] в python для обращения к списку O (1) пробел?

4 голосов
/ 01 марта 2020

Итак, если бы я написал: 

item_list = item_list[::-1]

Было бы это O (1) пробел? Я думаю, что item_list [:: - 1] приводит к созданию нового списка, так что это может быть O (n). Является ли item_list.reverse () подходящим методом для возврата с пробелом O (1) в python?

1 Ответ

6 голосов
/ 01 марта 2020

Вы правы, что some_list[::-1] создает новый список, и этот список будет иметь n"слотов", и, следовательно, потребуется O (n) memory.

Кроме того, в CPython [GitHub] , интерпретатор Python, .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)
        <b>reverse_slice(</b>self->ob_item, self->ob_item + Py_SIZE(self)<b>)</b>;
    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;
    }
}

Таким образом, он работает с двумя указателями, один из которых выполняет итерацию в порядке возрастания, а другой - в порядке убывания, и эти «меняйте» значения друг с другом, пока они не встретятся на полпути.

...