使用生成器在 python 中创建惰性流

Question

我一直在弄乱 python 中的流，并尝试生成汉明数（所有素因数为 2、3 或 5 的数字）。 Dijkstra 描述的这样做的标准方法是观察：

1. 汉明数序列从 1 开始。
2. 序列中其余值的形式为 2h、3h 和 5h，其中 h 是任意值 汉明数。
3. h 是通过输出值 1，然后将 2h、3h 和 5h 合并在一起生成的。

我的实现是这样的：

def hamming():
    yield 1
    yield from merge(scale_stream(hamming(), 2), scale_stream(hamming(), 3))

def merge(s1, s2):
  x1, x2 = next(s1), next(s2)
  while True:
    if x1 < x2:
        yield x1
        x1 = next(s1)
    elif x1 > x2:
        yield x2
        x2 = next(s2)
    else:
        yield x1
        x1, x2 = next(s1), next(s2)

def scale_stream(stream, scalar):
    for e in stream:
        yield e * scalar

def stream_index(stream, n):
    for i, e in enumerate(stream):
        if i+1 == n:
            return e

print(stream_index(hamming(), 300))

这确实正确地生成了汉明数流，但是无论出于何种原因，它生成的时间越长，花费的时间就越多，尽管理论上时间复杂度应该是 O(N)。

我之前玩过其他流，但我对它们的直觉非常弱，所以我不知道这里发生了什么。我认为问题出在我定义 hamming(); 的递归方式上。我不知道每次对汉明的调用都可能产生一个必须并行运行的新版本的进程，从而减慢它的速度，这是否是一个问题。

老实说，就像我说的那样，我的进程非常糟糕当我运行它和调试时实际发生的情况的想法对我毫无帮助，所以如果有更多经验的人可以启发我，我将非常感激。

Answer 1

您进入流的距离越远，您需要合并的重复项就越多。数字 2**4 * 3 **4 = 1296 将在您的多个流中出现 70 次（8 选择 4），并且您的程序将花费更多的时间来合并重复项，而不是输出新项目。

你走得越远，你要处理的重复就越多。没有理由期望您的程序是线性的。