python - 使用yield from进行树遍历的时间复杂度是多少？

Question

深度优先树遍历的示例:

class Node:
    def __init__(self, value):
        self._value = value
        self._children = []

    def add_child(self, child):
        self._children.append(child)

    def __iter__(self):
        return iter(self._children)

    def depth_first(self):
        yield self
        for c in self:
            yield from c.depth_first()

我知道 yield from 不会立即消耗生成器，而是将 yield 向上传递给其调用者。

但是这个传递的过程仍然存在，因此yield会从每个节点一直传递到它的根，我们可以通过以下方式来描述运行时间:递归(为了简单起见，假设它是二叉树，但想法是相同的):

T(n) = 2*T(n/2) + Θ(n)

θ(n) 存在是因为该节点必须将从其后代传递的所有 yield 传递给其父节点。由上式推导出的时间复杂度为:

O(nlogn)

但是，如果我根本不使用 yield 或 yield from，树遍历的时间复杂度仅为 O(n)。

我想知道我是否误解了 yield 的工作原理，或者编写这样的递归生成器根本不可行。

Answer 1

来自官方 Python 3.3 版本的产量:https://www.python.org/dev/peps/pep-0380/

Using a specialised syntax opens up possibilities for optimisation when there is a long chain of generators. Such chains can arise, for instance, when recursively traversing a tree structure. The overhead of passing next() calls and yielded values down and up the chain can cause what ought to be an O(n) operation to become, in the worst case, O(n**2).

A possible strategy is to add a slot to generator objects to hold a generator being delegated to. When a next() or send() call is made on the generator, this slot is checked first, and if it is nonempty, the generator that it references is resumed instead. If it raises StopIteration, the slot is cleared and the main generator is resumed.

This would reduce the delegation overhead to a chain of C function calls involving no Python code execution. A possible enhancement would be to traverse the whole chain of generators in a loop and directly resume the one at the end, although the handling of StopIteration is more complicated then.

看起来yield from仍然需要遍历树。但这种遍历是由 C 语言而不是 Python 中的解释器完成的。因此从技术上讲，它仍然是 O(n) 开销，但并不像听起来那么糟糕。