0

赤黒い木の上を歩き、さまざまなノード情報を ( list にstorage) 保存するために使用している再帰的な方法があります。

def _walk (self, storage, func, starting_node) :
    if starting_node is not self._nil :
        self._walk(storage, func, starting_node.left)
        storage.append(func(starting_node))
        self._walk(storage, func, starting_node.right)

ただし、このメソッドを再実装して、ジェネレーターを構築したいと思います (私が理解していることから、これは時間とメモリの両方を節約するはずです)。それを行う「最良の」方法は何ですか？

4

2 に答える 2

2 
def _walk (self, func, starting_node) :
    if starting_node is not self._nil :
        for x in self._walk(func, starting_node.left) :
            yield x
        yield func(starting_node)
        for x in self._walk(func, starting_node.right) :
            yield x
于 2012-11-05T03:49:52.697 に答える
2

ウォーキングからアクションを分離することから始めます

def _walk (self, starting_node) :
    if starting_node is not self._nil :
        for x in self._walk(starting_node.left):
            yield x
        yield starting_node
        for x in self._walk(starting_node.right):
            yield x

def traverse(self):
    starting_node = ???     # maybe these are passed as
    func = ???              # parameters to traverse
    for node in self._walk(starting_node):
        yield func(node)

traverseとほぼ同等です

imap(func, self._walk(starting_node))

またはこのジェネレータ式

(func(x) for x in self._walk(starting_node))

末尾再帰を手動で最適化することにより、使用されるスタックの量を減らすことができます

def _walk (self, starting_node) :
    while starting_node is not self._nil :
        for x in self._walk(starting_node.left):
            yield x
        yield starting_node
        starting_node = starting_node.right
于 2012-11-05T03:44:52.457 に答える