Take the 2-minute tour ×

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?

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)

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?)

share|improve this question
add comment

3 Answers

up vote 4 down vote accepted

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.

share|improve this answer
+1 - never optimize before determining where the code actually spends its time. –  Sarah Mei Oct 7 '09 at 9:38
I second Sarah's statement. I just wanted to use native memoization instead of creating a new one. –  khelll Oct 7 '09 at 13:14
I agree with Sarah's statement. I knew that but I thought that I would be clever anyway. Not a clever move. And your breakdown makes perfect sense so I'm marking it as the answer. I'm too new with ruby, I need to play with it a bit more until I can judge it properly. Still, Thankyou. –  Robert Massaioli Oct 7 '09 at 22:41
Oh and I purposely picked a computer that I knew was very slow to run my code on in an attempt to make the results more obvious. –  Robert Massaioli Oct 7 '09 at 22:42
add comment

Try this:

def initialize
  @cachedResults = {}

def get(x, y)
   @cachedResults["#{x}:#{y}"] ||= Math.hypot(x, y)
share|improve this answer
The point here being that you want your cache lookup to be the fastest thing possible. The native Hash class is probably a lot faster than a 2D Array class you wrote in a few minutes! –  glenn mcdonald Oct 7 '09 at 13:04
Agreed, and nice, I'm new to ruby and still learning the common ways to do things. Even so I should have known to use the inbuilt hash function. ty, i'll learn from this mistake. (+1) –  Robert Massaioli Oct 7 '09 at 22:45
add comment

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.

share|improve this answer
Yeah I just took a look at it myself just to be sure. Thanks. –  Robert Massaioli Oct 7 '09 at 22:45
add comment

Your Answer


