具有多次迭代的循环使执行速度异常缓慢

Question

此代码的执行时间约为 1 秒：

start_time = Time.now

prev = 1
(1..1000).each do |i|
  (1..10000).each do |j|
    result = j * prev
    result = result + prev
    result = result - prev
    result = result / prev
    prev = j
  end
end

end_time = Time.now
printf('%f sec', end_time - start_time)

但是当我使用一个循环进行 10000000 次迭代时（而不是上面写的 2 个循环，1000 次和 10000 次迭代），它变得慢得多（大约 4.5 秒）：

start_time = Time.now

prev = 1
(1..10000000).each do |j|
  result = j * prev
  result = result + prev
  result = result - prev
  result = result / prev
  prev = j
end

end_time = Time.now
printf('%f sec', end_time - start_time)

为什么会这样？总迭代次数还是一样。

Answer 1

第二个示例处理的数字比第一个大得多（如@Sergii K 在上面评论的那样）。第二个示例代码可能会达到您系统上的最大 Fixnum 限制。在 32 位系统上，maximum signed integer is 2**(32-1) - 1 = 2147483647 which is much less than the maximum product j * prev in the second example (as opposed to max products in the first example). In a situation like this ruby has to convert the Fixnums to Bignums 内部是第二个示例代码可能比第一个慢的原因。

在 64 位系统上，我希望两个样本大约同时运行，因为最大的整数永远不会达到 Fixnum 限制。这就是为什么大多数其他评论者没有看到时间上有很大差异的原因。

Update：如果最大 Fixnum 数仅为 1073741823，如上面 OP 所评论，那么它必须意味着 OS 本身是 64 位也许安装的 ruby 也是 64 位 ruby，它仍然只使用 4 个字节来存储 Fixnum 数字（而不是真正的 64 位 rubies 中的 8 个）。最大整数值比第二个示例中需要的要少得多，因此它确实必须将较高的数字转换为 Bignums，这就是第二个示例的缓慢来源。

这个你自己对比一下就可以了：

(2**(0.size * 8 -2) -1).class      # => Fixnum vs:
(2**(0.size * 8 -2) -1 + 1).class  # => should be Bignum

具有多次迭代的循环使执行速度异常缓慢

A loop with many iterations makes execution incredibly slow

ruby

loops

execution-time