如何修复中止斐波那契数列代码

Question

我正在尝试获取包含 500 万个元素的斐波那契数列。

当我将 1000 作为参数传递时，此代码异常中止。

def self.fibo_seq(limit)
  result_array = [0,1]
  return result_array if limit < 2
   while result_array.length <= limit
     result_array << result_array[-1] + result_array[-2]
   end
  return result_array
end
res= Multiple.fibo_seq(5_000_000)
print res

Error: [1]    22382 killed     ruby fibo.rb

示例输出：

# >> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, , 1...] upto 5 Million elements

Answer 1

这可能比替代方案更好。第 5 百万个斐波那契数将有大约一百万位数字。忽略计算它的时间，存储所有这些将占用 1 TB 的内存和至少另外 2 TB 的内存或存储空间用于输出。

最重要的是，如果你想这样做，你不能在普通的台式机上做，也不应该在 Ruby 中做。

对于那些问我如何得到号码的人：

根据维基百科 https://en.wikipedia.org/wiki/Fibonacci_number#Magnitude 数字的数量大约是 n 的 0.2090 倍，因此对于 5 来说，百万分之一的数字大约是一百万个数字。我没有仔细研究 Ruby 的 BigNumber 实现，但我假设每个字节有 2 位数字，这是十进制算术的最简单表示。您可以在其中打包更多位（10 位中的 3 位数字而不是 8 位中的 2 位数字）但它不会改变这里的结果。

对于整个数组，我只是使用了算术级数和的标准公式。 (n/2)*(a0 + an)：5,000,000 / 2 * 1,000,000 或 2.5e12 位数字。每字节 2 位数字，这将是大约 1 TB 的内部存储器（不计算 Ruby 通过其内部结构和间接增加的开销）。

如果将其打印出来或存储起来，您可以指望每个字节有 1 个数字（UTF-8），这样就需要 2.5 TB，不包括 4,999,999 个逗号。

Answer 2

这个程序的问题可能是内存限制。但是你真的需要所有这些数字吗？如果是，那么您最好获得更多硬件。

否则，如果您只需要序列中的第 500 万个数字，您可以通过仅存储最后两个数字来大大加快程序速度。

改进的最后一步：在常数时间内计算斐波那契数列的任意成员！ - “Find The Millionth Fibonacci in Java”。

Answer 3

生成一个 5M 的斐波那契数列是一个问题，因为涉及内存和时间。

生成它后，下一个问题将变成重复使用这些结果，这样您就不必重复两次。即使它适合，将序列存储在内存中也是愚蠢的，因为代码或机器崩溃会强制重新生成值，如果您需要 5,000,000，您可能会等待很长时间才能让应用程序准备好做一些有用的事情，所以把它们在磁盘上，或者在一个平面文件中，或者在一个数据库中，您可以在其中相对快速地检索您需要的特定值。

这是生成一个平面文件的简单代码，我测试了多达 25,000 个文件，然后才厌倦并停止它。对于那个测试来说它似乎做得很好，但我想它会随着 Ruby 的改变而变慢。不知道上限是多少，也没有耐心去了解

limit = ARGV.shift.to_i

puts "#{limit} iterations"

File.open('fibonacci.out', 'w') do |fo|
  ary = [0, 1]
  fo.puts ary
  break if limit < 2

  (limit - ary.length).times do |i|
    next_nbr = ary[-1] + ary[-2]
    ary.shift
    ary.push(next_nbr) 

    fo.puts next_nbr
    print 2 + i, "\r"
  end

  puts
end

你可能会通过摆脱 ary 来获得一点速度。

运行与

ruby test.rb 5

导致 "fibonacci.out" 包含：

这似乎是正确的。

有用于数据库的斐波那契生成器，但如果它们是递归的，你最终会取出你的 DBM，因为它试图生成大数字，所以使用一个简单的生成器，然后将值存储到 table 似乎更多合理。

Answer 4

使用 YARV 的 Integer 实现存储前 5000000 个斐波那契数在 64 位平台上正好使用 1084762047712 字节（假设每字节 8 位）。这接近 1 TiByte（准确地说是 0.9865853351 TiByte）。这只是数字本身的 space，还有数组的开销（几个字节）和数组内部的指针（略小于 5000000 乘以 8，或略高于 38 MiByte） .

计算这 5000000 个数字，即使没有存储它们（只记住最后 2 个以避免重新计算），在我 2011 年后期的 MacBook Pro 上花费了 20 多分钟。在分配 1 TiByte RAM 的同时计算它们会慢得多。如果您没有 1 TiByte 的 RAM，并且 OS 开始换出到磁盘，它会慢几个数量级，即使您有通过 FibreChannel 连接的固态硬盘 RAID。

为了打印数组，需要先将其表示为字符串。即使只是逗号和 spaces 而没有 数字也已经是 4999999*2 个字符，这需要接近 10 MiByte 的 RAM（假设是单字节字符集）。如果您尝试只打印逗号和 space，则需要大约 2500 页 DIN A4 纸，如果双面打印则需要 1250 张。办公用纸通常以 500 张一叠的形式出售，每叠大约 5 厘米高，因此您有 2.5 叠大约 12.5 厘米高 仅用于逗号和 spaces.

5000000 个数字的总位数，即字符（和字节），大约为 2.7 万亿位，即要打印的最终字符串大约需要 2.5 TiByte 的 RAM。双面打印在 DIN A4 上将得到一叠 33 公里高的纸，是珠穆朗玛峰高度的 4 倍。

总而言之，在您调用 print 时，您的程序需要大约 3.5 TiByte 的 RAM。

打印到控制台实际上出奇地慢，在我的标准 macOSTerminal.app 上，我得到大约 1MiByte/s，这意味着不仅计算 5000000 个数字需要至少几十分钟，甚至不计算分配所有这些对象和所有 RAM 的时间，您的程序不仅会使用 3.5 TiByte 的 RAM，仅在终端上显示最终数组的操作将花费大约 一个月.

tl;dr 总结：5000000 斐波那契数大.

如何修复中止斐波那契数列代码

How to fix aborting Fibonacci sequence code

ruby

arrays

memory-leaks

ruby-on-rails

fibonacci