我在玩与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)))))