Consommation de mémoire du produit itertools de Python

Question

El documentation dit que la fonction du produit cartésien

the actual implementation does not build up intermediate results in memory.

Comment cela peut-il être possible avec des générateurs ? Quelqu'un peut-il me montrer un exemple avec une consommation de mémoire limitée pour 2 générateurs ?

Answer 1

En regardant le code source du module, itertools.product() convertit en fait chaque argument en un tuple :

// 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;
}

En d'autres termes, itertools.product() La consommation de mémoire de l'application semble être linéaire par rapport à la taille des arguments d'entrée.

Answer 2

Eh bien, ça dit aussi :

Les boucles imbriquées tournent comme un odomètre avec l'élément le plus à droite avançant à chaque itération. Ce modèle crée un ordre lexicographique lexicographique, de sorte que si les itérables de l'entrée sont triés, les tuples sont émis dans l'ordre trié.

C'est à peu près comme cela que cela fonctionne dans l'implémentation ( Modules/itertoolsmodule.c )

Voici l'objet d'état :

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;

Et l'élément suivant est renvoyé par la fonction product_next qui utilise cet état et l'algorithme décrit dans la citation pour générer l'état suivant. Voir cette réponse pour comprendre les besoins en mémoire.

Pour une formation générale, vous pouvez lire comment créer des générateurs avec état à partir d'extensions C aquí .