4

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:])

ここで、階層の 1 つのレベルにフラグを立てて、そのレベルの終了後に操作を中断し、状態をディスクにシリアル化して、後で中断したところから取得したいと考えています。再帰の優雅さを失わずにこれを行う方法はありますか?

ジェネレーターをピクルできないことはわかっているので、イテレーター オブジェクトにリファクタリングすることを考えました。しかし、ここでの再帰には必要だと思いyield fromます(編集:少なくともスタックの面倒な管理なしで)ので、ジェネレーターである必要があると思いますか?これに対する回避策はありますか?

4

2 に答える 2

2

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には良い点があります...

于 2013-11-03T00:46:07.970 に答える
1

これが私がやったことです:

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 child_context
        else:
            yield from recursive_generator(child_context, hierarchy[1:])

def traverse_tree(hierarchy):
    return list(recursive_generator(ChainMap(), hierarchy)

def do_things(contexts, start, stop):
    for context in contexts[start:stop]:
        yield do_something(**context)

次に、 によって返されたリストをピクルしtraverse_tree、後でロードして、 で分割して実行できますdo_things。もちろん、これはすべてクラス内にあり、さらに多くのことが行われていますが、これがその要点になります。

于 2013-11-03T19:42:28.507 に答える