如何以非平凡的方式组合两个发电机

Question

我有一个生成所有正整数的生成器,它是2的幂,另一个生成所有3的幂的整数.我现在需要用它们来生成2 ^ i*3 ^ j形式的整数,其中i,j > = 0,0按递增顺序排列.

我认为使用生成器的目的是减少内存消耗.我一直试图这样做一段时间但无济于事.请帮忙.

Answer 1

使用自读流

您可以使用自读流来解决此问题:

   -----------        -----------
   |  pow 2  |------->|         |
   -----------        |         |
                      |  merge  |-------+------------>
   -----------        |         |       |
.->|   x 3   |------->|         |       |
|  -----------        -----------       |
\_______________________________________/

第一个流产生2的幂,而第二个流确保所有生成的数字乘以3并重新注入输出.合并运算符确保输出已排序.

请注意,我们必须使用1"播种"输出流,否则第一个元素将在评估时尝试生成自身.

这是代码:

(require srfi/41)

(define (merge s1 s2)
  (stream-match s1 ((x . xs)
    (stream-match s2 ((y . ys)
      (if (< x y)
        (stream-cons x (merge xs s2))
        (stream-cons y (merge ys s1))))))))

(define (the-stream)
  (letrec ((s
    (stream-cons 1 (merge (stream-map     (lambda (x) (* 3 x)) s)
                          (stream-iterate (lambda (x) (* 2 x)) 2)))))
  s))

与我的其他提议相比,它非常简单快速,因为除了单调性之外 , 它还使用了问题的算术属性.我错了,它也可以推广(即将推出)

$ mzscheme -f feedback.scm -e '(display (stream->list (stream-take 20 (the-stream))))'
(1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96)

$ time mzscheme -f feedback.scm -e '(display (stream-ref (the-stream) 10000))'
161968247347450370721577384417107686788864605658546176
real    0m1.746s
user    0m1.344s
sys     0m0.156s

使用生成器和队列

我们也可以用python的生成器来实现它,但是我们需要使用队列来存储在反馈循环中等待的数字:

# Merge the output of two generators
def merge(g1, g2):
    v1 = g1.next()
    v2 = g2.next()
    while 1:
        if v1 < v2:
            yield v1
            v1 = g1.next()
        else:
            yield v2
            v2 = g2.next()

# Generates the powers of 2, starting with n
def pow2(n):
    while 1: yield n; n *= 2

# Generates values shifted from the given 'q' and multiplied by 3
def mul3(q):
    while 1: yield q.pop(0) * 3

# The generator we want
def pow23():
    q = []
    v = 1
    g = merge(pow2(2), mul3(q))
    while 1:
        yield v
        q.append(v)
        v = g.next()

g23 = pow23()
for i in range(10000): g23.next()
print g23.next()

这有点不太优雅(恕我直言),但生成器更轻量级:

$ time python feedback.py 
161968247347450370721577384417107686788864605658546176
real    0m0.150s
user    0m0.112s
sys     0m0.012s

值得一提的是,我已经完成了一个方案实现(使用闭包作为生成器),它显示了大致相同的性能.