首页 文章

Ruby中的Lazy Fibonacci序列

提问于
浏览 次
0

如果我想创建一个迭代的懒惰Fibonacci序列来自Python，我可以这样做：

def fib():
    a = 1
    b = 2
    yield a
    yield b
    while True:
        yield a + b
        tmp = a
        a = b
        b = tmp + b

通过简单地添加前两个元素，抓取 next(fib) 将给出序列中的下一个元素，所以如果我想获得前1000个Fibonacci元素，我可以快速完成：

fib = fib()
for i in range(0,1000):
    print(next(fib))

If I try to reproduce that in Ruby with an Enumerator，每次调用fib.next（）时，它会快速扼流，重新计算整个序列：

def fib()
    Enumerator.new do |yielder|
        yielder << 1 << 2
        fib.lazy.zip(fib.lazy.drop(1)).each do |a,b|
            yielder << a + b
        end
    end
end

我发现另一个SO post关于如何用Ruby中的memoization来修复递归的fibonacci，但我很好奇，懒惰的序列和生成器是Ruby中的东西吗？

ruby generator lazy-sequences

1 回答

  • 3

    不要使用递归枚举器，但是在Python中这样做？有一个循环？

    def fib()
  Enumerator.new do |yielder|
    a, b = 1, 2
    yielder << a << b
    loop do
      a, b = b, a + b
      yielder << b
    end
  end
end

    你在Ruby中所做的事情在Python中看起来像这样：

    def fib():
    yield from (1, 2)
    for a, b in zip(fib(), islice(fib(), 1, None)):
        yield a + b

    那也很慢 .

    顺便说一句，比指数时间更糟的是指数量的记忆 . 在尝试计算第32个Fibonacci数时，我的递归Python版本 crashes . 那时我已经有近400万台发电机在运转 . 在尝试计算第20个Fibonacci数时，你的Ruby版本崩溃，错误 can't create fiber (FiberError) . 那时我有近12000根光纤在运行 .

    回复于

相关问题