Потребление памяти продукта Python itertools

Документация говорит о том, что декартовая функция продукта

Как это возможно с генераторами? Может ли кто-нибудь показать мне пример с ограниченным объемом памяти для 2 генераторов?

Ответы

Ответ 1

Глядя на исходный код модуля, itertools.product() фактически преобразует каждый аргумент в кортеж:

// product_new() in itertoolsmodule.c
for (i=0; i < nargs ; ++i) {
    PyObject *item = PyTuple_GET_ITEM(args, i);
    PyObject *pool = PySequence_Tuple(item); //<==== Call tuple(arg)
    if (pool == NULL)
        goto error;
    PyTuple_SET_ITEM(pools, i, pool);
    indices[i] = 0;
}

Другими словами, потребление памяти itertools.product() кажется линейным по размеру входных аргументов.

Ответ 2

Ну, это также говорит:

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

Это в значительной степени работает в реализации (Modules/itertoolsmodule.c)

Вот объект состояния:

typedef struct {
    PyObject_HEAD
    PyObject *pools;       /* tuple of pool tuples */
    Py_ssize_t *indices;   /* one index per pool */
    PyObject *result;      /* most recently returned result tuple */
    int stopped;           /* set to 1 when the product iterator is exhausted */
} productobject;

И следующий элемент возвращается функцией product_next, которая использует это состояние и алгоритм, описанный в цитате, для генерации следующего состояния. См. этот ответ, чтобы понять требования к памяти.

Для общего образования вы можете прочитать о том, как создавать генераторы с состоянием из C-расширений здесь.