Ruby 数学函数记忆

Question

我编写了一些如下所示的代码：

def get(x, y)
   @cachedResults.set(x,y, Math.hypot(x, y)) if @cachedResults.get(x,y).nil?
   @cachedResults.get(x,y)
end

其中 @cachedResults 包含我编写的 2D Array 类（几分钟内），该函数的目的是确保我永远不必为任何给定的 (x ，y）。 [这可以使用对称性和其他东西进一步优化，但无论如何]

所以我调用了该函数并让它运行 160000 次；它只用了 15 秒多一点就跑了。然后，为了看看它比非 Memoized 版本快了多少，我将代码更改为：

def get(x, y)
   Math.hypot(x, y)
end

而且，令我惊讶的是，再次运行只花了 15 秒多一点的时间。完全相同的时间。所以我的问题是，Ruby 中的数学函数是否自然地被记忆化了？如果是这样，ruby 的记忆化程度如何？

（如果不是，那么你为什么认为我始终得到这个结果？）

Answer 1

你是否需要大约 15 秒才能完成某件事 160000 次？在您的系统上对其进行基准测试，仅返回 x；与解释器开销相比，hypot 操作（用 C 实现）很可能可以忽略不计。

对于使用 khell 的 memoized get 方法的 ruby​​ 1.8.7，在 get 方法内调用该函数，并仅在 get 方法内返回 x，迭代 100000 次：

peregrino:$ time ruby src/memoized_hypot.rb 

real    0m1.714s
user    0m1.436s
sys 0m0.080s
peregrino:$ time ruby src/plain_hypot.rb 

real    0m0.495s
user    0m0.364s
sys 0m0.060s
peregrino:$ time ruby src/empty_hypo.rb 

real    0m0.369s
user    0m0.220s
sys 0m0.068s

kheill 的 memoization 在每次调用时都会创建一个字符串，这比调用 C 的成本要高得多每次调用时都会使用库的hypot 函数。

调用hypot 和仅返回x 之间的差异表明hypot 仅贡献了25% 的运行时间。这不是您应该优化的代码 - 相反，如果可以的话，请尝试内联对库的调用，而不是将其包装在另一个方法中。

peregrino:$ time ruby src/inline_hypot.rb 

real    0m0.365s
user    0m0.236s
sys 0m0.044s

这

100000.times{ |i| Math.hypot(i,6) }   

不是

100000.times{ |i| foo.get(i,6) }   

foo 是一个带有发布方法的对象。

---

这些时间是在上网本（Asus eeepc 900）上进行的，上网本的速度不是很快，所以它们比您的时间快得多，这有点奇怪。因此，其他因素可能会主导您的结果。

Answer 2

试试这个：

def initialize
  @cachedResults = {}
end

def get(x, y)
   @cachedResults["#{x}:#{y}"] ||= Math.hypot(x, y)
end

Answer 3

在这种情况下，我不期望这里的记忆会有很大提高。

Math.hypot 所做的只是 sqrt(x**2 + y**2)。它不是对已计算值的递归调用。