Homework Module: Cache Optimization and Fibonacci Performance Comparison

This module contains two main tasks:

1. Cache Optimization: This task involves optimizing data access using an LRU cache. It generates a random array and queries, then compares the execution time with and without caching.

2. Fibonacci Performance Comparison: This task compares the performance of calculating Fibonacci numbers using an LRU cache and a Splay Tree. It measures the execution time for each approach and plots a graph to visualize the results.

Tasks Overview

Task 1: Cache Optimization

• Objective: Optimize data access using an LRU cache.
• Implementation:
  • Generate a random array of size 100,000.
  • Generate 50,000 queries of type "Range" and "Update".
  • Implement functions for calculating the sum of elements with and without caching.
  • Compare execution times with and without caching.

Task 2: Fibonacci Performance Comparison

• Objective: Compare the performance of calculating Fibonacci numbers using LRU cache and Splay Tree.
• Implementation:
  • Implement Fibonacci calculation functions using LRU cache and Splay Tree.
  • Measure execution time for each approach.
  • Plot a graph comparing the execution times.
  • Display a table of results.

Requirements

• Python 3.x
• matplotlib for plotting
• colorama for colored terminal output
• timeit for measuring execution time (included in Python standard library)

Results