Pythons itertools Produktspeicherverbrauch

Question

Die documentation sagt, dass die kartesische Produkt Funktion

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

Wie das mit Generatoren möglich sein kann? Kann jemand mir ein Beispiel mit einem begrenzten Speicherverbrauch für 2 Generatoren zeigen?

Answer 1

auf den Quellcode des Moduls sucht, wandelt itertools.product() eigentlich jedes Argument in ein Tupel:

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

Mit anderen Worten, itertools.product() ‚s Speicherverbrauch erscheint linear in der Größe der Eingabeargumente zu sein.

Answer 2

Nun, es sagt auch:

Der verschachtelte Schleifen Zyklus wie ein Wegstreckenzähler mit dem ganz rechten Elemente bei jeder Iteration voran. Dieses Muster erzeugt eine lexikographische Reihenfolge, so dass, wenn die Iterables der Eingabe sortiert sind, die Tupel des Produkts in sortierter Reihenfolge ausgegeben werden.

Das ist ziemlich viel, wie es bei der Umsetzung arbeitet (Modules/itertoolsmodule.c)

ist das Zustandsobjekt:

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; 

Und der nächste Punkt wird durch die Funktion product_next, zurückgegeben, die diese verwenden Zustand und der im Zitat beschriebene Algorithmus, um den nächsten Zustand zu erzeugen. Siehe this answer, um die Speicheranforderungen zu verstehen.

Für allgemeine Bildung können Sie lesen, wie Generatoren mit Status von C-Erweiterungen here erstellen.