ruby-on-rails - 如何修复中止斐波那契数列代码

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

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

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

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

这 5000000 个数字的总位数以及字符(和字节)大约为 2.7 万亿位，即要打印的最终字符串大约需要 2.5 TiByte 的 RAM。在 DIN A4 纸上双面打印出来的结果是一叠 33 公里高的纸，是珠穆朗玛峰高度的 4 倍。

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

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

tl;dr 总结:5000000 个斐波那契数大。