5

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.

StevieD
  • 6,925
  • 2
  • 25
  • 45

4 Answers4

15

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
spickermann
  • 100,941
  • 9
  • 101
  • 131
  • Let's say I change the function to accept three arguments. Is there a good way to automate the generation of the key? – StevieD Aug 14 '18 at 19:00
  • Your code is 2x faster than my code even with print statement stripped out. – StevieD Aug 14 '18 at 19:04
  • 1
    You mean if you used common named arguments, but do not want to list them all? There might be a way: See this [answer](https://stackoverflow.com/a/31234292/2483313). But would use it... – spickermann Aug 14 '18 at 19:05
  • I guess hard-coded it shall be. That looks ugly. Is there a Ruby gem that handles multiple parameter memoization? – StevieD Aug 14 '18 at 19:18
  • 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. – ForeverZer0 Aug 15 '18 at 07:41
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
matthewd
  • 4,332
  • 15
  • 21
  • I'd be nervous about the thread-safety of all of these, but especially so the last one. – matthewd Aug 14 '18 at 18:14
  • 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? – StevieD Aug 14 '18 at 18:32
  • 3
    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. – spickermann Aug 14 '18 at 18:39
  • 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. – matthewd Aug 14 '18 at 18:42
  • I did some benchmarking. My original function with the join is twice as fast as using an object for a key. – StevieD Aug 14 '18 at 18:57
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.

svoop
  • 3,318
  • 1
  • 23
  • 41
0

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
Epigene
  • 3,634
  • 1
  • 26
  • 31