7

I'm wondering if there is a more "Ruby-like" way to memoize functions with multiple parameters in Ruby. Here's a way that I came up with that works but not sure if it's the best approach:

@cache = {}
def area(length, width)  #Just an example, caching is worthless for this simple function
  key = [length.to_s, width.to_s].join(',')
  if @cache[key]
    puts 'cache hit!'
    return @cache[key]
  end
  @cache[key] = length * width
end

puts area 5, 3
puts area 5, 3
puts area 4, 3
puts area 3, 4
puts area 4, 3

The parameters are joined with a comma which is then used as a key for storage in the @cache variable.

Improve this question
0

4 Answers 4

Reset to default
16

When you do not need to print Cache hit! than I would do something like this:

def area(length, width)
  @cache ||= {}
  @cache["#{length},#{width}"] ||= length * width
end

Or if you need some output, but a Cache miss! is fine too:

def area(length, width)
  @cache ||= {}

  @cache.fetch("#{length},#{width}") do |key| 
    puts 'Cache miss!'
    @cache[key] = length * width
  end
end

If you want to accept even more arguments you might want to use something like this:

def area(*args)
  @cache ||= {}
  @cache[args] ||= args.inject(:*)
end
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Let's say I change the function to accept three arguments. Is there a good way to automate the generation of the key?
Your code is 2x faster than my code even with print statement stripped out.
You mean if you used common named arguments, but do not want to list them all? There might be a way: See this answer. But would use it...
I guess hard-coded it shall be. That looks ugly. Is there a Ruby gem that handles multiple parameter memoization?
If performance is an issue, hashing the arguments and using an integer for a key would be far better. Something like length.hash ^ width.hash. It could also be easily adapted to handle variable number of arguments: args.inject { |r, n | r ^ n.hash }. The likelihood of a hash collision would be super rare. You could always throw in a prime number to reduce those odds even more.
4

You can use the array directly:

def area(length, width)
  key = [length, width]
  if @cache[key]
    puts 'cache hit!'
    return @cache[key]
  end
  @cache[key] = length * width
end

Or use nested hashes:

def area(length, width)
  c = (@cache[length] ||= {})
  if c[width]
    puts 'cache hit!'
    return c[width]
  end
  c[width] = length * width
end
Improve this answer

5 Comments

I'd be nervous about the thread-safety of all of these, but especially so the last one.
Nifty trick with the first one. So the array automatically gets converted to a string? What's the issue with threading, exactly? What can go wrong? Two different cache data structures will be built?
No, the array isn't automatically converted into a string. There is no need to do that. Because every object can be used as a hash key: symbols, integer, or even huge complex data structures.
In general at best you could have multiple threads calculating the same value... but with the nested hash form one call could clear out a different width's calculation [for the same length], for example.
I did some benchmarking. My original function with the join is twice as fast as using an object for a key.
2

On Ruby 2.7 and up, positional arguments and keyword arguments are isolated which has an impact on how to implement multi-argument memoization. For a generic implementation, I'd do something like this:

def my_method(*args, **kwargs)
  (@my_method_cache ||= {})[args.hash ^ kwargs.hash] ||= begin
    (...)
  end
end

Replace (...) with the expensive calculation done by my_method.

Improve this answer

Comments

1

While @spickermann's answer is good and @matthewd's answer touches upon it, the elephant in the room is memoization of falsey values. Naive ||= will not cut it.

Consider:

def memoises_truthy(arg1, arg2)
  @memo ||= {}
  memo_key = "#{arg1.hash}_#{arg2.hash}"

  @memo[memo_key] ||= begin
    puts "Crunching #{arg1} && #{arg2}"
    arg1 && arg2 
  end
end

> memoises_truthy(:a, :b)
Crunching a && b
=> :b
> memoises_truthy(:a, :b)
=> :b
> memoises_truthy(false, false)
Crunching false && false
=> false
> memoises_truthy(false, false)
Crunching false && false # noo, cache miss!
=> false

A more robust approach is to check the presence of the cache key, even if the value is falsey.

def memoises_all(arg1, arg2)
  @memo ||= {}
  memo_key = "#{arg1.hash}_#{arg2.hash}"

  return @memo[memo_key] if @memo.key?(memo_key) # a simple guard for cache hit.
  
  @memo[memo_key] = begin
    puts "Crunching #{arg1} && #{arg2}"
    arg1 && arg2 
  end
end

> memoises_all(:a, :b)
Crunching a && b
=> :b
> memoises_all(:a, :b)
=> :b
 memoises_all(false, false)
Crunching false && false
=> false
memoises_all(false, false)
=> false
Improve this answer

1 Comment

Nice catch! I think using an array as the hash key lookup is possible too! and from this article might cover the same catch? Like this: memo_key = [arg1.hash, arg2.hash]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.