out-of-core/external-memory python 中的组合数学

Question

我正在迭代搜索 space 有效 Python3 AST。最大递归深度 = 3 时，我的笔记本电脑内存不足。我的实现大量使用生成器，特别是 'yield' 和 itertools.product().

理想情况下，我会用某种迭代深化替换 product() 和最大递归深度，但首先要做的是： out-of-core/external-memory 组合数学有没有图书馆或有用的 SO 帖子？

如果不是...我正在考虑使用 dask 或 joblib 的 delayed()...或者 wendelin-core 的 ZBigArray 的可行性，尽管我不喜欢它的界面外观：

root = dbopen('test.fs')
root['A'] = A = ZBigArray((10,), np.int)
transaction.commit()

基于这个例子，我认为我的解决方案将涉及一个 annotation/wrapper 函数，它急切地将生成器转换为 ZBigArrays，用 root[get_key(function_name, *function_args)] 之类的东西替换 root['A'] 这并不漂亮，因为我的生成器不完全是纯的——输出被打乱了。在我当前的版本中，这应该不是什么大问题，但是之前和下一个版本涉及使用各种 NN 和 RL 而不仅仅是洗牌。

Answer 1

首先，您遇到内存不足错误的原因是 itertools.product() 缓存了中间值。它不知道为您提供生成器的函数是否是幂等的，即使它是幂等的，它也无法仅在给定生成器的情况下推断如何再次调用它。这意味着 itertools.product 必须缓存其传递的每个可迭代对象的值。

这里的解决方案是咬住小的性能子弹，或者编写明确的 for 循环，或者编写您自己的笛卡尔乘积函数，该函数采用将生成每个生成器的函数。例如：

def product(*funcs, repeat=None):
    if not funcs:
        yield ()
        return

    if repeat is not None:
        funcs *= repeat

    func, *rest = funcs
    
    for val in func():
        for res in product(*rest):
            yield (val, ) + res

from functools import partial
values = product(partial(gen1, arg1, arg2), partial(gen2, arg1))

在这里滚动你自己的好处是你还可以改变它通过 C 遍历 A 的方式......维度搜索 space，这样你就可以做一个 breadth-first 搜索而不是迭代加深 DFS。或者，也许选择一些随机的 space-filling 曲线，例如 Hilbert Curve，它将以 local-centric 的方式迭代 product() 中每个维度的所有 indices/depths。

除此之外，我还有一件事要指出 - 您还可以延迟实现 BFS（使用生成器）以避免构建可能会膨胀内存使用量的队列。参见，为方便起见复制如下：

def breadth_first(self):
    yield self
    for c in self.breadth_first():
        if not c.children:
            return  # stop the recursion as soon as we hit a leaf
        yield from c.children

总的来说，使用 semi-coroutines 和零缓存，所有这些都在 python-land 中（与 CPython 的内置和高度优化的 C 相比），您的性能会受到影响。然而，它仍然应该是可行的——算法优化（避免生成语义上无意义的 AST，优先考虑适合你目标的 AST，等等）将比 constant-factor 性能损失产生更大的影响。

out-of-core/external-memory python 中的组合数学

out-of-core/external-memory combinatorics in python

python

out-of-memory

bigdata

itertools

combinatorics