Ruby Maths Function Memoization

Question

Hi All,

I wrote some code that looks like this:

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

Where @cachedResults contained a 2D Array class i wrote (in a few minutes) and the purpose of this function is to make sure that I never have to call Math.hypot twice for any given (x,y). [This could be optimised further using symmetry and other things but whatever]

So I called the function and let it run 160000 times; it ran in just over 15 seconds. Then, to see how much faster it was than the non Memoized version, i changed the code to this:

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

And, much to my surprise, it took just over 15 seconds to run again. The exact same time. So my question is, are the maths functions in ruby naturally Memoized? And, if so, to what extent is ruby Memoized?

(If not then why do you think I am getting this result consistently?)

Answer 1

I won't expect a memorization here will improve a lot in this case.

What Math.hypot do is just sqrt(x**2 + y**2). It is not an recursive call to already caculated value.

Answer 2

Try this:

def initialize
  @cachedResults = {}
end

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

Answer 3

Does it take around 15 seconds to do anything 160000 times for you? Benchmark it on your system just returning x; it may well be that the hypot operation ( implemented in C ) is negligible than the interpreter overhead.

For ruby 1.8.7 with khell's memoized get method, calling the function inside a get method, and just returning x inside a get method, with 100000 iterations:

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's memoization creates a string on every call, which is much more costly than calling the C library's hypot function on every call.

The difference between the calling hypot and just returning x indicates that hypot is only contributing 25% of the runtime. It's not the code you should be optimising - instead try inlining the call to the library if you can rather than wrapping it in another method.

peregrino:$ time ruby src/inline_hypot.rb 

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

which is

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

rather than

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

where foo is an object with the methods posted.

---

These times were on a netbook ( Asus eeepc 900 ) which isn't massively speedy, so it's a bit odd that they are much faster than your times. So something else might be dominating your results.