python - 高效递归迭代器: Possible?

Question

这个问题困扰我很久了。我想要一个二叉树(或类似的嵌套结构)上的迭代器，它高效、简单且Pythonic。例如，对于这样的用法:

for value in values(root):
    do_something_with_value(value)

print(sum(values(root)))

这里root是树的根节点，节点有.value、.left和.right。 values 应该为我提供树值所需的迭代器/可迭代对象。

设 n 为树中的节点数，h 为树的高度。

尝试 1:太慢

def values(root):
    if root:
        yield from values(root.left)
        yield root.value
        yield from values(root.right)

简单、Pythonic、懒惰，并且只占用 O(h) 空间。 应该就是这样。但是......它是堆叠的生成器，每个值都是通过整个生成器堆栈产生的。因此，整个迭代在最坏情况下需要 O(n²) 时间，即使在最好情况下也需要 O(n log n) 时间。

尝试 2:太复杂

def values(root):
    stack = []
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        yield root.value
        root = root.right

使用节点堆栈进行迭代。只需要 O(h) 空间和 O(n) 时间，但它比上面的完全自然的递归要复杂得多。

尝试 3:太大

def values(root):
    result = []
    def collect_values(root):
        if root:
            collect_values(root.left)
            result.append(root.value)
            collect_values(root.right)
    collect_values(root)
    return result

这会收集半全局列表中的所有值。自然递归和 O(n) 时间，但遗憾的是 O(n) 空间并且并不懒惰。

尝试 4:无法让它工作

我想也许我可以滥用半全局生成器，而不是半全局列表。作为一种从内部递归直接到外部的管道。递归会将值发送到其中，外部可以获取它们。像这样的事情:

def values(root):
    pipe = magic_generator_pipe()
    def iterate(root):
        if root:
            iterate(root.left)
            pipe.send(root.value)
            iterate(root.right)
    iterate(root)
    yield from pipe

但我无法让它工作，而且我不确定这是否可能。

尝试 5:也许

有线程或asyncio的东西吗？我的另一个想法是 values 函数启动一个新线程。该线程递归地迭代树并将值传递给 values 函数中的主线程，该函数将它们生成给原始的外部调用者。他们适本地锁定彼此。但我对此没有太多经验。

问题

有没有办法实现我想要的一切？

1. Python式的惰性迭代器
2. 总时间为 O(n)
3. O(h) 空间
4. 自然递归

所以本质上我想要类似尝试 1 的东西，但是速度要快。因为我已经使用递归 yield from 来解决几个问题，并且总是对时间复杂度感到不好。

澄清一下:“太复杂”我真正指的是迭代算法(它并不那么复杂，但与自然递归相比)。仅以“技术”方式“复杂”的解决方案(例如使用额外的线程或@chepner 的蹦床想法)仍然会很有趣。我只是坚持自然递归(或类似的算法简单的东西)和其他三个目标。

Answer 1

我的方法可能不会令您满意，因为它是您正在做的事情的反转，即使用回调。您将回调方法传递给能够迭代该结构的函数，以便为遇到的每个值调用该回调方法。在此示例中，函数 walk 是通过 callback 函数调用的。在本例中，该结构是一棵被遍历的树，并且对于每个节点值，都会调用回调函数。

def walk(root, callback):

    def tree_walk(node):
        if node['left']:
            tree_walk(node['left'])
        callback(node['value'])
        if node['right']:
            tree_walk(node['right'])

    tree_walk(root)


node4 = {'value': 4, 'left': None, 'right': None}
node3 = {'value': 3, 'left': node4, 'right': None}
node2 = {'value': 2, 'left': None, 'right': None}
node1 = {'value': 1, 'left': node2, 'right': node3}

def do_something_with_value(value):
    print('value:', value)

walk(node1, do_something_with_value)

打印:

value: 2
value: 1
value: 4
value: 3