5

考虑以下代码片段。

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
        )

该函数返回几何级数中的第一个，以每次num_elements开始start并乘以。multiplier很容易看出最后一个元素将通过一个 yield-statement 和num_elements-1yield-from-statements 传递。该函数是否具有O(num_elements)时间复杂度，或者它是否具有O(num_elements**2)时间复杂度是由于深度为 0、1、2、...、...、...的嵌套 yield-from-statements 的“阶梯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)？

4

2 回答 2

4

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

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

于 2020-05-04T12:18:13.903 回答
1

yield from形式上等价于 的循环，response = yield child.send(response)加上错误传播和处理。当在迭代中消耗时，response总是None并且没有错误被传播/处理。这相当于一个for循环。

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

因此，每个都yield from具有迭代其参数的时间/空间复杂性。yield from因此，将一个大小的子项堆叠n总m次数的时间复杂度为O(nm).

于 2020-05-04T12:17:46.920 回答