`yield from` 的时间复杂度是 O(1) 吗？

Question

考虑以下代码片段。

from typing import Iterable


def geometric_progression(
    start: float, multiplier: float, num_elements: int
) -> Iterable[float]:
    assert num_elements >= 0
    if num_elements > 0:
        yield start
        yield from geometric_progression(
            start * multiplier, multiplier, num_elements - 1
        )

这个函数returns从start开始每次乘以multiplier的几何级数的第一个num_elements。很容易看出最后一个元素将通过一个 yield-statement 和 num_elements-1 yield-from-statements 传递。此函数是否具有 O(num_elements) 时间复杂度，或者由于 "ladder" 深度为 0、1、2 的嵌套 yield-from 语句而具有 O(num_elements**2) 时间复杂度，...， num_elements-2, num_elements-1?

编辑：我想出了一个更简单的代码片段来演示我的要求。

from typing import Iterable, Any

def identity_with_nested_yield_from(depth: int, iterable: Iterable[Any]) -> Iterable[Any]:
    assert depth >= 1
    if depth == 1:
        yield from iterable
    else:
        yield from identity_with_nested_yield_from(depth-1, iterable)

这个函数是O(depth + length of iterable)，还是O(depth * length of iterable)？

Answer 1

yield from 是 formally equivalent 到 response = yield child.send(response) 的循环，加上错误传播和处理。在迭代中使用时，response 始终是 None，没有错误是 propagated/handled。这相当于一个 for 循环。

# `yield from child` without error handling/response
for x in child:
    yield x

因此，每个 yield from 具有迭代其参数的 time/space 复杂性。堆叠 yield from 大小 n child 总共 m 次因此时间复杂度为 O(nm).

Answer 2

我可以发誓有一个优化可以缩短这些类型的 yield from 链，但测试显示没有这样的优化，而且我在我认为优化的地方找不到任何东西已实施。

yield from 链的每个级别上的生成器必须单独暂停和恢复，以在链上和下传递 yield 和 send 值。您的函数具有 O(num_elements**2) 时间复杂度。此外，一旦调用堆栈达到 1000 的深度，它就会发生堆栈溢出。

`yield from` 的时间复杂度是 O(1) 吗？

Does `yield from` have O(1) time complexity?

python

yield-from