xbe.at

Python / Core language

Memoization for Fibonacci Sequence in Python

6 min read, 16 sections

Contents
  1. Introduction to Memoization
  2. The Fibonacci Sequence
  3. Memoized Fibonacci
  4. Understanding the Performance Gain
  5. Memoization in Practice
  6. Memoization with Multiple Arguments
  7. Memoization in Dynamic Programming
  8. Memoization in Graph Algorithms
  9. Memoization in Tree Traversal
  10. Memoization in String Manipulation
  11. Memoization in Recursive Mathematical Functions
  12. Memoization in Game Theory
  13. Limitations and Considerations
  14. Real-life Example: DNA Sequence Alignment
  15. Real-life Example: Image Processing
  16. Additional Resources

Introduction to Memoization

Memoization is an optimization technique that stores the results of expensive function calls and returns the cached result when the same inputs occur again. This powerful strategy can significantly improve the performance of recursive algorithms or functions with repeated computations.

def memoize(func):
    cache = {}
    def wrapper(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrapper

@memoize
def expensive_function(n):
    # Simulate an expensive computation
    return sum(i for i in range(n))

# Usage
result = expensive_function(1000000)
print(result)  # Output: 499999500000

The Fibonacci Sequence

The Fibonacci sequence is a classic example where memoization shines. Each number is the sum of the two preceding ones, starting from 0 and 1. Let's implement it without memoization first.

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

# Usage
print(fibonacci(30))  # Output: 832040 (takes several seconds)

Memoized Fibonacci

Now, let's apply memoization to our Fibonacci function and observe the performance improvement.

@memoize
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n-1) + fib_memo(n-2)

# Usage
print(fib_memo(30))  # Output: 832040 (instant result)
print(fib_memo(100))  # Output: 354224848179261915075 (still instant)

Understanding the Performance Gain

To visualize the performance difference, let's time both implementations for various inputs.

import time

def time_function(func, *args):
    start = time.time()
    result = func(*args)
    end = time.time()
    return result, end - start

# Compare performance
for n in [20, 30, 35]:
    _, time_regular = time_function(fibonacci, n)
    _, time_memo = time_function(fib_memo, n)
    print(f"n={n}:")
    print(f"  Regular: {time_regular:.6f} seconds")
    print(f"  Memoized: {time_memo:.6f} seconds")
    print(f"  Speedup: {time_regular / time_memo:.2f}x")

Memoization in Practice

Memoization isn't limited to mathematical sequences. It's useful in various scenarios where computations are repeated. Let's consider a function that calculates the number of ways to climb stairs, taking 1 or 2 steps at a time.

@memoize
def climb_stairs(n):
    if n <= 1:
        return 1
    return climb_stairs(n-1) + climb_stairs(n-2)

# Usage
print(climb_stairs(30))  # Output: 1346269
print(climb_stairs(50))  # Output: 20365011074

Memoization with Multiple Arguments

Memoization works well with functions that take multiple arguments. Let's implement a memoized function to calculate the binomial coefficient.

@memoize
def binomial_coefficient(n, k):
    if k == 0 or k == n:
        return 1
    return binomial_coefficient(n-1, k-1) + binomial_coefficient(n-1, k)

# Usage
print(binomial_coefficient(30, 15))  # Output: 155117520
print(binomial_coefficient(50, 25))  # Output: 126410606437752

Memoization in Dynamic Programming

Memoization is a key component of dynamic programming. Let's solve the classic "Longest Common Subsequence" problem using memoization.

@memoize
def lcs(X, Y, m, n):
    if m == 0 or n == 0:
        return 0
    elif X[m-1] == Y[n-1]:
        return 1 + lcs(X, Y, m-1, n-1)
    else:
        return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n))

# Usage
X = "AGGTAB"
Y = "GXTXAYB"
print(lcs(X, Y, len(X), len(Y)))  # Output: 4

Memoization in Graph Algorithms

Memoization can significantly improve the performance of graph algorithms. Let's implement a memoized depth-first search to count the number of paths between two nodes.

@memoize
def count_paths(graph, start, end, visited=None):
    if visited is None:
        visited = set()
    if start == end:
        return 1
    if start in visited:
        return 0
    visited.add(start)
    count = 0
    for neighbor in graph[start]:
        count += count_paths(graph, neighbor, end, visited.copy())
    return count

# Usage
graph = {
    'A': ['B', 'C'],
    'B': ['C', 'D'],
    'C': ['D'],
    'D': ['E'],
    'E': []
}
print(count_paths(graph, 'A', 'E'))  # Output: 3

Memoization in Tree Traversal

Tree traversal algorithms can benefit from memoization, especially when dealing with repeated subtrees. Let's implement a memoized function to count unique binary search trees.

@memoize
def count_unique_bst(n):
    if n <= 1:
        return 1
    count = 0
    for i in range(1, n + 1):
        count += count_unique_bst(i - 1) * count_unique_bst(n - i)
    return count

# Usage
for i in range(1, 11):
    print(f"Unique BSTs with {i} nodes: {count_unique_bst(i)}")

Memoization in String Manipulation

String manipulation problems often involve repeated subproblems. Let's use memoization to solve the "Edit Distance" problem efficiently.

@memoize
def edit_distance(str1, str2, m, n):
    if m == 0:
        return n
    if n == 0:
        return m
    if str1[m-1] == str2[n-1]:
        return edit_distance(str1, str2, m-1, n-1)
    return 1 + min(edit_distance(str1, str2, m, n-1),    # Insert
                   edit_distance(str1, str2, m-1, n),    # Remove
                   edit_distance(str1, str2, m-1, n-1))  # Replace

# Usage
str1 = "kitten"
str2 = "sitting"
print(edit_distance(str1, str2, len(str1), len(str2)))  # Output: 3

Memoization in Recursive Mathematical Functions

Complex mathematical functions with recursive definitions can greatly benefit from memoization. Let's implement the Catalan number sequence using memoization.

@memoize
def catalan(n):
    if n <= 1:
        return 1
    res = 0
    for i in range(n):
        res += catalan(i) * catalan(n-i-1)
    return res

# Usage
for i in range(10):
    print(f"Catalan({i}) = {catalan(i)}")

Memoization in Game Theory

Game theory algorithms often involve exploring many possible game states. Memoization can help reduce redundant calculations. Let's implement a memoized function to solve the coin game problem.

@memoize
def coin_game(coins, i, j):
    if i > j:
        return 0
    return max(
        coins[i] + min(coin_game(coins, i+2, j), coin_game(coins, i+1, j-1)),
        coins[j] + min(coin_game(coins, i+1, j-1), coin_game(coins, i, j-2))
    )

# Usage
coins = [20, 30, 2, 10]
print(coin_game(tuple(coins), 0, len(coins) - 1))  # Output: 40

Limitations and Considerations

While memoization is powerful, it's not always the best solution. Consider these factors:

  1. Memory usage: Memoization trades space for time.
  2. Input size: For small inputs, the overhead might outweigh the benefits.
  3. Function purity: Memoization works best with pure functions.
  4. Cache invalidation: Ensure the cache is cleared or updated when necessary.
def memoize_with_limit(func, max_size=100):
    cache = {}
    def wrapper(*args):
        if args in cache:
            return cache[args]
        if len(cache) >= max_size:
            cache.clear()  # Clear cache when it reaches the limit
        result = func(*args)
        cache[args] = result
        return result
    return wrapper

@memoize_with_limit
def limited_memo_func(n):
    # Some expensive computation
    return sum(i for i in range(n))

# Usage
print(limited_memo_func(1000))  # Output: 499500
print(limited_memo_func(1000))  # Cached result

Real-life Example: DNA Sequence Alignment

In bioinformatics, sequence alignment is a common task. Let's use memoization to implement a simple DNA sequence alignment algorithm.

@memoize
def dna_align(seq1, seq2, i, j, gap_penalty=-1):
    if i == 0:
        return j * gap_penalty
    if j == 0:
        return i * gap_penalty
    if seq1[i-1] == seq2[j-1]:
        return dna_align(seq1, seq2, i-1, j-1)
    return max(
        dna_align(seq1, seq2, i-1, j) + gap_penalty,
        dna_align(seq1, seq2, i, j-1) + gap_penalty,
        dna_align(seq1, seq2, i-1, j-1) + gap_penalty
    )

# Usage
seq1 = "ATCG"
seq2 = "ATACG"
alignment_score = dna_align(seq1, seq2, len(seq1), len(seq2))
print(f"Alignment score: {alignment_score}")  # Output: Alignment score: -1

Real-life Example: Image Processing

In image processing, we often need to apply filters or transformations to pixels. Let's use memoization to optimize a simple edge detection algorithm.

@memoize
def detect_edge(image, x, y):
    if x == 0 or y == 0 or x == len(image) - 1 or y == len(image[0]) - 1:
        return 0
    gradient_x = abs(image[x+1][y] - image[x-1][y])
    gradient_y = abs(image[x][y+1] - image[x][y-1])
    return max(gradient_x, gradient_y)

# Simulated image (2D list of pixel intensities)
image = [
    [0, 0, 0, 0, 0],
    [0, 50, 50, 50, 0],
    [0, 50, 100, 50, 0],
    [0, 50, 50, 50, 0],
    [0, 0, 0, 0, 0]
]

# Detect edges
edge_image = [[detect_edge(tuple(map(tuple, image)), x, y) for y in range(5)] for x in range(5)]

for row in edge_image:
    print(row)

Additional Resources

For those interested in diving deeper into memoization and its applications, here are some valuable resources:

  1. "Dynamic Programming and Memoization: Bottom-Up vs Top-Down Approaches" by Ivaylo Ivanof (arXiv:2003.12959) https://arxiv.org/abs/2003.12959
  2. "Efficient Dynamic Programming Using Memoization" by Richard E. Korf (arXiv:1604.05197) https://arxiv.org/abs/1604.05197

These papers provide in-depth analyses of memoization techniques and their applications in various computational problems.

More in Core language

  1. Python Concepts and Code Examples for Intermediate to Expert18 min

    The bias-variance tradeoff is a fundamental concept in machine learning that describes the relationship between a model's ability to minimize bias...

  2. Leveraging super() for Flexible Inheritance in Python7 min

    The super() function provides a clean way to access methods from parent classes in Python, enabling proper inheritance chains. It automatically handles...

  3. Python Fundamentals and Applications10 min

    Time series analysis is a crucial technique for understanding and predicting sequential data. This presentation explores advanced methods using TensorFlow...

  4. Leveraging Python Type Annotations8 min

    Python's type annotations provide a way to explicitly declare types for variables, function parameters, and return values. This helps catch type-related bugs...

  5. Python Namespace Types and Scopes5 min

    Python namespaces are containers that hold mappings of names to objects. There are four types of namespaces in Python: Built-in, Global, Enclosing, and...

  6. Leveraging Python Descriptors for Robust Attribute Management12 min

    Descriptors are a powerful feature in Python that provide a way to customize attribute access in classes. They enable fine-grained control over how...