Tabulation vs. Memoization in Ruby: A Deep Dive

Alessio Bussolari
2 min readNov 2, 2023

--

Tabulation and memoization are both optimization techniques employed, especially in the domain of algorithms and computation. However, they have different approaches and uses. Using Ruby, a language known for its expressiveness, we can demonstrate and differentiate the two.

Tabulation:

What is Tabulation?
Tabulation is a bottom-up dynamic programming technique where you solve all the subproblems first. You then use the solutions of these subproblems to build the solution to bigger problems.

Approach in Ruby:

Let’s consider the classic problem of computing the nth Fibonacci number.

def fibonacci(n)
return n if n <= 1
table = [0, 1]
(2..n).each do |i|
table[i] = table[i - 1] + table[i - 2]
end
table[n]
end

In the above example, we use an array table to store solutions to subproblems. We then combine these solutions to find the desired Fibonacci number.

Memoization:

What is Memoization?
Memoization is a top-down dynamic programming technique where you break down a problem into subproblems. It involves storing the result of expensive function calls and returning the cached result when the same inputs occur again.

Approach in Ruby:

For the same Fibonacci problem:

def fibonacci(n, memo = {})
return n if n <= 1
return memo[n] if memo.has_key?(n)
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
end

Here, we use a memo hash to store results of subproblems. When a result is not in the memo, we compute it and save it to memo for future reference.

Differences:

  • Approach:
    Tabulation: Bottom-up approach. Solve smaller subproblems first.
    Memoization: Top-down approach. Solve bigger problems first by breaking them down.
  • Data Structure:
    Tabulation: Usually employs arrays (but not limited to them).
    Memoization: Commonly uses hashes (dictionaries).
  • Space Efficiency:
    Tabulation: Might sometimes use more space as it solves and stores solutions for all subproblems…

--

--

Alessio Bussolari

Ruby on Rails programmer since 2009. Current CTO at COSMIC SRL, where I lead the team in creating innovative solutions.