Python的itertools.product内存消耗问题

Question

文档中说，笛卡尔积函数

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

使用生成器如何可能做到有限的内存消耗？能否给我展示一个用2个生成器来实现有限内存消耗的例子？

- fulmicoton

---

可能是 为什么我在使用itertools.product时会出现MemoryError？ 的重复问题。 - Janne Karila

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()的内存消耗似乎与输入参数大小成线性关系。

- NPE

Answer 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扩展创建带有状态的生成器。

- Eli Bendersky