2

我正在使用 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：对于 Will Ness，这是我在 LISP 中实现的算法（实际上是 Racket）：

(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)))))
4

2 回答 2

3

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

主要问题是：你无条件地merge()调用它的两个参数，所以两者都前进了一步。因此，在生成第一个数字之后，例如对于生成器，在下一次调用时，它会看到它的第一个参数 as和第二个参数 as 。已经没了。所以它总是拉出它的两个参数，并总是返回第一个的头部（http://ideone.com/doeX2Q的测试条目）。next()2m234(,6,8,...)6(,9,12,...)3

调用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()适配器被提升到输入流的顶部——要么是在适当的时候，要么是太快了（所以我们最终会得到太多的适配器）。

于 2013-02-01T14:29:53.730 回答
1

我将提出这种不同的方法 - 使用 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]
于 2020-11-30T02:03:24.773 回答