使用生成器在 python 中制作惰性流

Question

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

汉明数列从 1 开始。
序列中的其余值的形式为 2h、3h 和 5h，其中 h 是任意值海明数.
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();我不知道每次调用 hamming 都可能产生一个新版本的进程是否是一个问题，该进程必须并行运行从而减慢速度。

老实说就像我说的那样，我对运行实际发生的事情一无所知，而且调试让我无处可去，所以如果有更多经验的人能启发我，我将非常感激。

Answer 1

你越深入你的流，你将不得不合并的重复越多。数字 2**4 * 3 **4 = 1296 将在您的多个流中出现 70 次（8 选 4），并且您的程序将花费更多时间合并重复项而不是输出新项。

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

使用生成器在 python 中制作惰性流

Using generators to make lazy streams in python

python

generator

stream