在Python中合併惰性流（使用生成器）

Question

我在玩Python 3的功能性能力，並試圖實現用於計算漢明數字的經典算法。這是隻有2,3或5個主要因素的數字。第一個漢明數字是2,3,4,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) 

它是合併似乎是行不通的問題。在此之前，我實現埃拉托色尼的篩以同樣的方式，和它的工作完全沒問題：

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：威爾內斯這裏是我實現這個算法在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()它的兩個參數無條件，所以都獲得先進的一步。所以在產生第一個數字之後，例如2爲m23發生器，在下次調用它認爲它的第一個參數爲4(,6,8,...)和2爲6(,9,12,...)。 3已經消失。所以它總是拉出兩個參數，並且總是返回第一個的頭部（測試條目在​​3210）。

調用iter()是完全多餘的，它在這裏沒有增加任何內容。當我刪除它時（http://ideone.com/7tk85h），程序完全相同，併產生完全相同（錯誤）的輸出。通常iter()用於創建惰性迭代器對象，但其參數已經是這種生成器。

您的sieve()也不需要撥打iter()（http://ideone.com/kYh7Di）。 sieve()已經定義了一個生成器，Python 3中的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()適配器在輸入流的頂部懸掛 - 無論是在適當的時候，還是太早（所以我們最終會有太多的結果）。