Ruby中的惰性斐波那契数列 [英] Lazy Fibonacci Sequence in Ruby

问题描述

如果我想创建一个迭代的懒惰斐波那契序列，来自Python，我可以做这样的事情:

Coming from Python if I wanted to create an iterative lazy Fibonacci sequence, I could do something like this:

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个斐波那契元素，我可以快速地做到这一点:

Grabbing next(fib) will give me the next element in the sequence by simply adding the previous two elements, so if I want to get the first 1000 Fibonacci elements, I can do that quickly:

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

如果我尝试使用枚举器在Ruby中重现它，它会迅速阻塞，重新计算每次调用fib.next()时，整个序列:

If I try to reproduce that in Ruby with an Enumerator, it quickly chokes, recalculating the entire sequence each time we call 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帖子关于如何在Ruby中使用备忘录来修复递归斐波那契，但我很好奇，在Ruby中，惰性序列和生成器是否有用?

I found another SO post on how to fix a recursive fibonacci with memoization in Ruby, but I am curious, are lazy sequences and generators a thing in Ruby?

推荐答案

不使用递归枚举器，但是否像Python中那样?有循环吗?

Don't use recursive enumerators but do it like in Python? With a loop?

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中看起来像这样:

What you did there in Ruby looks in Python like this:

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

那也很慢.

顺便说一句，比指数时间差的是指数存储量.当我尝试计算第32个斐波那契数时，该递归Python版本崩溃了.到那时，我已经有将近400万台发电机在运行.当您尝试计算第20个斐波那契数时，您的Ruby版本崩溃了，错误为can't create fiber (FiberError).那时我有将近12000根光纤在运行.

Btw, worse than the exponential time is the exponential amount of memory. That recursive Python version crashes for me when trying to compute the 32nd Fibonacci number. At that point I already have almost 4 million generators running. And your Ruby version crashes for me when trying to compute the 20th Fibonacci number, with error can't create fiber (FiberError). At that point I have almost 12000 fibers running.

这篇关于Ruby中的惰性斐波那契数列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！