1

我写了一些看起来像这样的代码：

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

@cachedResults 包含我写的一个二维数组类（在几分钟内），这个函数的目的是确保我永远不必为任何给定的 (x,y) 调用 Math.hypot 两次。[这可以使用对称性和其他东西进一步优化，但无论如何]

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

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

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

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

4

3 回答 3

4

为你做 160000 次任何事情需要大约 15 秒吗？在您的系统上对它进行基准测试，只返回 x；很可能hypot操作（用C实现）比解释器开销可以忽略不计。

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

peregrino:$ time ruby​​ src/memoized_hypot.rb

真实0m1.714s
用户 0m1.436s
系统 0m0.080s
peregrino:$ time ruby​​ src/plain_hypot.rb

实际0m0.495s
用户 0m0.364s
系统 0m0.060s
peregrino:$ time ruby​​ src/empty_hypo.rb

实际0m0.369s
用户 0m0.220s
系统 0m0.068s

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

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

peregrino:$ time ruby​​ src/inline_hypot.rb

实际0m0.365s
用户 0m0.236s
系统 0m0.044s

这是

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

而不是

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

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

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

于 2009-10-07T08:43:59.397 回答
3

试试这个：

def initialize
  @cachedResults = {}
end

def get(x, y)
   @cachedResults["#{x}:#{y}"] ||= Math.hypot(x, y)
end
于 2009-10-07T05:40:36.700 回答
1

在这种情况下，我不认为这里的记忆会提高很多。

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

于 2009-10-07T05:26:24.813 回答