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 回答