合并懒惰流(使用发电机)中的Python(Merge of lazy streams (using

2019-07-19 03:20发布

我在玩与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()两个自变量无条件,所以得到先进的一步。 是这样就产生第一数量,例如,后2m23发生器,在下次调用它看到其第一参数作为4(,6,8,...)和第二为6(,9,12,...)3已经消失了。 所以它总是拉它的两个参数,始终(在测试条目,则返回1号的头http://ideone.com/doeX2Q )。

调用iter()完全是多余的,但这里没有任何增加。 当我将其删除( http://ideone.com/7tk85h ),该程序的工作原理完全一样,准确地产生相同的(错误的)输出。 通常iter()用于创建一个懒惰的迭代器对象,但在这里它的参数已经是这样的发电机。

有没有必要打电话给iter()在你的sieve()以及( http://ideone.com/kYh7Di )。 sieve()已经定义了一个发生器,和filter()在Python 3从一个函数创建一个迭代器和一个可迭代(发电机可迭代)。 又见例如Python的发电机和迭代器之间的差异 。

我们可以做合并这个样子,而不是:

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 

这是现在很多很多, 有效(见: 说明这个块的Haskell代码输出素数的流 )。

递归与否,是的代码只是句法特征。 实际运行时间结构是一样的- filter()在适当的时刻,无论是,还是太很快(所以我们想最终的方式太多了) -在输入流的顶部吊装适配器。



文章来源: Merge of lazy streams (using generators) in Python