A Guide to Memoization in Ruby

Memoization is a programming technique used to optimize the performance of functions by caching their results. In Ruby, memoization is often used to avoid redundant calculations and improve efficiency, especially in situations where a method is called multiple times with the same arguments. This guide will walk you through the basics of memoization in Ruby, including how to implement it with examples.

What is Memoization?

Memoization involves storing the results of expensive function calls and reusing these results when the same inputs occur again. This can significantly speed up performance in scenarios where computations are repeated with identical inputs.

How Ruby Memoization Works

Memoization works by caching the results of method calls in an instance variable. When the method is called with the same parameters, the cached result is returned instead of recalculating the result.

Basic Example
Here’s a simple example to illustrate memoization in Ruby:

class Fibonacci
  def initialize
    @cache = {}
  end

  def fibonacci(n)
    return n if n <= 1
    return @cache[n] if @cache.key?(n)

    @cache[n] = fibonacci(n - 1) + fibonacci(n - 2)
  end
end

fib = Fibonacci.new
puts fib.fibonacci(10) # Output: 55

Explanation:

• We define a Fibonacci class with an instance variable @cache to store previously computed values.
• The fibonacci method checks if the result is already cached using @cache.key?(n). If so, it returns the cached result.
• If the result is not cached, it computes the value and stores it in @cache before returning it.

Memoization with ‘||=’ Operator

Ruby provides a shorthand for memoization using the ‘||=’ operator. This operator assigns a value to a variable only if the variable is nil or false. Here’s how you can use it for memoization:

class ExpensiveCalculation
  def initialize(data)
    @data = data
  end

  def result
    @result ||= perform_expensive_calculation
  end

  private

  def perform_expensive_calculation
    # Simulating an expensive operation
    sleep(2)
    @data * 2
  end
end

calc = ExpensiveCalculation.new(10)
puts calc.result # Takes 2 seconds on first call, then returns instantly on subsequent calls
puts calc.result

Explanation:

• The result method uses the ||= operator to assign the result of perform_expensive_calculation to @result only if @result is nil.
• On subsequent calls to result, the cached value of @result is returned immediately, bypassing the expensive calculation.

Memoization with Blocks

Memoization can also be used with blocks. Here’s an example using a block to cache results:

class Calculator
  def initialize
    @cache = {}
  end

  def memoize(key)
    @cache[key] ||= yield
  end
end

calc = Calculator.new
result = calc.memoize(:square_of_5) { 5 * 5 }
puts result # Output: 25

Explanation:

• The memoize method takes a key and a block. It evaluates the block and caches the result if the key is not already present in @cache.
• On subsequent calls with the same key, the cached result is returned.

Slutsats

Memoization is a powerful technique to enhance performance in Ruby applikationer by avoiding redundant computations. By caching the results of expensive method calls, you can significantly reduce execution time and improve efficiency. Whether you use instance variables, the ||= operator, or memoization with blocks, this technique can be adapted to various scenarios to optimize your code.