python - Python の itertools 製品のメモリ消費量

Question

ドキュメントによると、デカルト積関数

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

ジェネレーターでそれがどのように可能になるのでしょうか? 2 つのジェネレーターのメモリ消費量が制限されている例を誰かに見せてもらえますか?

Answer 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()のメモリ消費量は、入力引数のサイズに比例しているように見えます。

Answer 2

さて、それはまた言います：

ネストされたループは走行距離計のように循環し、反復ごとに右端の要素が進みます。このパターンは、入力の iterable がソートされている場合、積のタプルがソートされた順序で発行されるように、辞書式の順序付けを作成します。

これは、実装でどのように機能するかです ( 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 拡張機能から状態を使用してジェネレーターを作成する方法についてここで読むことができます。