在Python中合并惰性流(使用生成器)

Question

我正在使用Python3的函数能力，并尝试实现计算Hamming数的经典算法。第一个汉明数是2，3，5，6，8，10，12，15，16，18，20等等。

我的实现如下：

def scale(s, m):
    return (x*m for x in s)

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

def integers():
    n = 0
    while True:
        n += 1
        yield n

m2 = scale(integers(), 2)
m3 = scale(integers(), 3)
m5 = scale(integers(), 5)

m23 = merge(m2, m3)

hamming_numbers = merge(m23, m5)

问题是合并似乎就是不起作用。在此之前，我以同样的方式实现了Eratosthenes的筛子，它工作得非常好：

def sieve(s):
    it = iter(s)
    x = next(it)
    yield x
    it = iter(sieve(filter(lambda y: x % y, it)))
    while True: yield next(it)

此操作使用与我的合并操作相同的技术。所以我看不出有什么不同。你有什么想法吗？

(我知道所有这些都可以通过其他方式实现，但我的目标正是理解Python的生成器和纯函数功能，包括递归，而不使用类声明或特殊的预构建Python函数。)

UPD:对于Will Ness，这是我用LISP实现的算法(实际上是球拍)：

(define (scale str m)
  (stream-map (lambda (x) (* x m)) str))

(define (integers-from n)
  (stream-cons n
               (integers-from (+ n 1))))

(define (merge s1 s2)
  (let ((x1 (stream-first s1))
        (x2 (stream-first s2)))
    (cond ((< x1 x2)
           (stream-cons x1 (merge (stream-rest s1) s2)))
          ((> x1 x2)
           (stream-cons x2 (merge s1 (stream-rest s2))))
          (else
           (stream-cons x1 (merge (stream-rest s1) (stream-rest s2)))))))


(define integers (integers-from 1))

(define hamming-numbers
  (stream-cons 1 (merge (scale hamming-numbers 2)
                        (merge (scale hamming-numbers 3)
                               (scale hamming-numbers 5)))))

Answer 1

你的算法不正确。您的m2, m3, m5应该扩展hamming_numbers，而不是integers。

主要的问题是:您的merge()为它的两个参数都无条件地调用next()，因此两个都前进了一步。因此，在生成第一个数字之后，例如m23生成器的2，在下一次调用时，它会将第一个参数视为4(,6,8,...)，将第二个参数视为6(,9,12,...).3已经消失了。因此，它总是提取两个参数，并始终返回第一个参数的头部(http://ideone.com/doeX2Q处的测试条目)。

调用iter()完全是多余的，它不会在这里添加任何东西。当我删除它(http://ideone.com/7tk85h)时，程序的工作方式完全相同，并产生完全相同(错误)的输出。通常，iter()用于创建一个惰性迭代器对象，但这里的参数已经是这样的生成器。

也不需要在sieve()中调用iter() (http://ideone.com/kYh7Di)。sieve()已经定义了一个生成器，Python3中的filter()从一个函数和一个迭代器创建迭代器(生成器是可迭代的)。另请参阅例如Difference between Python's Generators and Iterators。

我们可以像这样做合并，而不是：

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)

在定义sieve()函数时，递归本身也不是必需的。事实上，它只会掩盖该代码的一个巨大缺陷。它产生的任何质数都将通过其值低于其值的所有质数进行测试-但只有那些低于其平方根的质数才是真正需要的。我们可以很容易地用非递归风格(http://ideone.com/Qaycpe)来修复它：

def sieve(s):    # call as: sieve( integers_from(2))
    x = next(s)  
    yield x
    ps = sieve( integers_from(2))           # independent primes supply
    p = next(ps) 
    q = p*p       ; print((p,q))
    while True:
        x = next(s)
        while x<q: 
            yield x
            x = next(s)
        # here x == q
        s = filter(lambda y,p=p: y % p, s)  # filter creation postponed 
        p = next(ps)                        #   until square of p seen in input
        q = p*p 

这现在非常非常高效(另请参阅：Explain this chunk of haskell code that outputs a stream of primes )。

递归与否，只是代码的一个语法特征。实际的运行时结构是相同的- filter()适配器被提升到输入流的顶部-要么在适当的时刻，要么太快了(所以我们最终会得到太多的适配器)。

Answer 2

我将提出这种不同的方法-使用Python heapq (min-heapq)和生成器(惰性求值)(如果您不坚持保留merge()函数)

from heapq import heappush, heappop

def hamming_numbers(n):
    ans = [1]

    last = 0
    count = 0

    while count < n:
        x = heappop(ans)

        if x > last:
            yield x

            last = x
            count += 1

            heappush(ans, 2* x)
            heappush(ans, 3* x)
            heappush(ans, 5* x)


    >>> n  = 20
    >>> print(list(hamming_numbers(20)))
       [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36]