Почему обновление списка происходит быстрее при использовании понимания списка, а не выражения генератора? - PullRequest
Новая
       56

Почему обновление списка происходит быстрее при использовании понимания списка, а не выражения генератора?

0 голосов
/ 24 апреля 2019

Согласно этот ответ списки работают лучше, чем генераторы в ряде случаев, например, при использовании вместе с str.join (поскольку алгоритм должен передавать данные дважды).

В следующем примере использование понимания списка , по-видимому, дает лучшую производительность, чем использование соответствующего выражения генератора, хотя интуитивно понимание списка происходит с накладными расходами выделения и копирования в дополнительную память, которую генератор обходит. 

In [1]: l = list(range(2_000_000))

In [2]: %timeit l[:] = [i*3 for i in range(len(l))]
190 ms ± 4.65 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [3]: %timeit l[:] = (i*3 for i in range(len(l)))
261 ms ± 7.14 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [4]: %timeit l[::2] = [i*3 for i in range(len(l)//2)]
97.1 ms ± 2.07 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [5]: %timeit l[::2] = (i*3 for i in range(len(l)//2))
129 ms ± 2.21 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [6]: %timeit l[:len(l)//2] = [i*3 for i in range(len(l)//2)]
92.6 ms ± 2.34 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [7]: %timeit l[:len(l)//2] = (i*3 for i in range(len(l)//2))
118 ms ± 2.17 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

Почему понимание списка позволяет в этих случаях повысить производительность?

1 Ответ

4 голосов
/ 24 апреля 2019

Этот ответ касается только реализации CPython. Использование понимания списка быстрее, поскольку генератор сначала все равно преобразуется в список. Это сделано потому, что длина последовательности должна быть определена за до продолжения замены данных, и генератор не может сказать вам его длину.

Для назначения фрагмента списка эта операция обрабатывается забавно названным list_ass_slice. Существует специальная обработка для назначения списка или кортежа, здесь - они могут использовать PySequence_Fast ops.

Эта является 3.7 реализацией PySequence_Fast, где вы можете ясно увидеть проверку типов для списка или кортежей: 

PyObject *
PySequence_Fast(PyObject *v, const char *m)
{
    PyObject *it;

    if (v == NULL) {
        return null_error();
    }

    if (PyList_CheckExact(v) || PyTuple_CheckExact(v)) {
        Py_INCREF(v);
        return v;
    }

    it = PyObject_GetIter(v);
    if (it == NULL) {
        if (PyErr_ExceptionMatches(PyExc_TypeError))
            PyErr_SetString(PyExc_TypeError, m);
        return NULL;
    }

    v = PySequence_List(it);
    Py_DECREF(it);

    return v;
}

Выражение генератора не выполнит эту проверку типа и перейдет к резервному коду, где оно преобразуется в объект списка, так что длина может быть предопределена .

В общем случае желательна заранее определенная длина для эффективного распределения хранилища списков, а также для предоставления полезных сообщений об ошибках с расширенным назначением срезов: 

>>> vals = (x for x in 'abc')
>>> L = [1,2,3]
>>> L[::2] = vals  # attempt assigning 3 values into 2 positions
---------------------------------------------------------------------------
                                          Traceback (most recent call last)
...
ValueError: attempt to assign sequence of size 3 to extended slice of size 2
>>> L  # data unchanged
[1, 2, 3]
>>> list(vals)  # generator was fully consumed
[]
...