python - 暂停(序列化)和恢复递归生成器堆栈的解决方法？

Question

我有一个递归生成器函数，它创建一个 ChainMap 上下文树，并最终在树的末尾对上下文执行某些操作。看起来像这样(parent_context 是一个 ChainMap，hierarchy 是一个列表):

def recursive_generator(parent_context, hierarchy):
    next_level = hierarchy[0]
    next_level_contexts = get_contexts(next_level) # returns a list of dicts

    for context in next_level_contexts:
        child_context = parent_context.new_child().update(context)
        if next_level == hierarchy[-1]:
            yield do_something(**child_context)
        else:
            yield from recursive_generator(child_context, hierarchy[1:])

现在我想标记层次结构的一个级别，以便操作在完成该级别后暂停，将状态序列化到磁盘，以便稍后从它停止的地方获取。有没有办法在不失去递归的优雅的情况下做到这一点？

我知道你不能 pickle 生成器，所以我考虑重构为一个迭代器对象。但我认为 yield from 对于这里的递归是必要的(编辑:至少没有一些繁琐的堆栈管理)，所以我认为它需要是一个生成器，不是吗？有解决办法吗？

Answer 1

您似乎正在使用 DFS 探索一棵树。所以你可以在内存中构建树并使 DFS 显式。然后只需存储树并在最左边的节点重新启动(我想？)。

这实际上是“繁琐的堆栈管理”，但它有一张有助于实现它的漂亮图片(至少对我而言，将您的问题视为树的 DFS 使得实现看起来相当明显 - 在我想到之前就像那样，它看起来很复杂 - 但我可能会遗漏一些东西)。

抱歉，如果这很明显且不够......

[编辑]

class Inner:

    def __init__(self, context, hierarchy):
        self.children = []
        next_level = hierarchy[0]
        next_level_contexts = get_contexts(next_level)
        for context in next_level_contexts:
            child_context = parent_context.new_child().update(context)
            if next_level == hierarchy[-1]:
                self.children.append(Leaf(context))
            else:
                self.children.append(Inner(child_context, hierarchy[1:]))

    def do_something(self):
        # this will do something on the left-most leaf                         
        self.children[0].so_something()

    def prune(self):
        # this will remove the left-most leaf                                  
        if isinstance(self.children[0], Leaf):
            self.children.pop(0)
        else:
            self.children[0].prune()
            if not self.children[0]:
                self.children.pop(0)

    def __bool__(self):
        return bool(self.children)

class Leaf:

    def __init__(self, context):
        self.context = context

    def do_something(): 
        do_something(**self.context)

上面的代码还没有经过测试。我最终为节点使用了类，因为元组看起来太困惑了。您通过创建父节点来创建树。然后您可以通过调用 do_something 来“做某事”，之后您将需要使用 prune 删除“完成”的叶子:

tree = Inner(initial_context, initial_hierarchy)
while tree:
    tree.do_something()
    tree.prune()

我很确定它会包含错误，但希望它足以展示这个想法。抱歉，我不能做更多，但我需要重新种植植物....

ps 有趣的是，您可以使用生成器编写代码，但不知道 DFS 是什么。您可能会喜欢阅读“算法设计手册”——它既是教科书又是引用书，它不会把您当成白痴(我也没有接受过计算机科学方面的正规教育，但我认为这是一本好书)。

[编辑为先更改为最左侧，我认为这是您之前的设置]

alko 有一个很好的观点...