python
exercises
exercises.py🐍python
"""
Python Performance - Exercises
Practice profiling, optimization, and efficient coding techniques
"""
import time
import timeit
import functools
from typing import List, Dict, Any, Optional, Callable
from collections import deque
# ============================================================
# EXERCISE 1: Timer Decorator
# ============================================================
"""
Create a decorator that measures and prints the execution time
of any function. Support optional number of runs for averaging.
"""
def timed(runs: int = 1):
"""
Decorator to time function execution.
Args:
runs: Number of times to run for averaging
Example:
@timed(runs=3)
def slow_function():
time.sleep(0.1)
return "done"
# Output: slow_function: avg 0.1003s over 3 runs
"""
def decorator(func):
@functools.wraps(func)
def wrapper(*args, **kwargs):
# YOUR CODE HERE
pass
return wrapper
return decorator
# Test
# @timed(runs=3)
# def test_function():
# time.sleep(0.05)
# return "done"
# result = test_function()
# ============================================================
# EXERCISE 2: Memoization with TTL
# ============================================================
"""
Create a memoization decorator with time-to-live (TTL) support.
Cached values should expire after the specified number of seconds.
"""
def memoize_with_ttl(ttl_seconds: float):
"""
Decorator for caching function results with expiration.
Args:
ttl_seconds: Cache lifetime in seconds
Example:
@memoize_with_ttl(5.0)
def fetch_data(key):
# expensive operation
return data
fetch_data("a") # Computed
fetch_data("a") # Cached
time.sleep(6)
fetch_data("a") # Computed again (expired)
"""
def decorator(func):
cache = {}
@functools.wraps(func)
def wrapper(*args):
# YOUR CODE HERE
# Store (result, timestamp) in cache
# Check if entry exists and hasn't expired
pass
wrapper.cache = cache
wrapper.clear_cache = lambda: cache.clear()
return wrapper
return decorator
# Test
# @memoize_with_ttl(0.5)
# def expensive_call(x):
# time.sleep(0.1)
# return x * 2
# ============================================================
# EXERCISE 3: Optimize Duplicate Finder
# ============================================================
"""
The following function finds duplicates in a list.
It's O(n²). Optimize it to O(n).
"""
def find_duplicates_slow(items: list) -> list:
"""SLOW: O(n²) implementation - DO NOT MODIFY, this is for comparison."""
duplicates = []
for i, item in enumerate(items):
for j in range(i + 1, len(items)):
if items[j] == item and item not in duplicates:
duplicates.append(item)
return duplicates
def find_duplicates_fast(items: list) -> list:
"""
FAST: O(n) implementation.
Find all items that appear more than once.
Returns:
List of duplicate items (each appearing once)
Example:
>>> find_duplicates_fast([1, 2, 3, 2, 4, 3, 5])
[2, 3]
"""
# YOUR CODE HERE
pass
# Verify correctness and compare performance
# test_data = list(range(1000)) + list(range(100))
# assert sorted(find_duplicates_slow(test_data)) == sorted(find_duplicates_fast(test_data))
# ============================================================
# EXERCISE 4: Optimize String Building
# ============================================================
"""
Optimize this function that builds a large string from parts.
The current implementation is O(n²) due to string concatenation.
"""
def build_report_slow(items: List[Dict]) -> str:
"""SLOW: O(n²) due to string concatenation."""
report = "=== Report ===\n"
for item in items:
report += f"Name: {item['name']}\n"
report += f"Value: {item['value']}\n"
report += "-" * 20 + "\n"
return report
def build_report_fast(items: List[Dict]) -> str:
"""
FAST: O(n) implementation.
Build the same report but efficiently.
Example:
>>> items = [{"name": "A", "value": 1}, {"name": "B", "value": 2}]
>>> print(build_report_fast(items))
=== Report ===
Name: A
Value: 1
--------------------
...
"""
# YOUR CODE HERE
pass
# ============================================================
# EXERCISE 5: Efficient Queue Implementation
# ============================================================
"""
Implement a queue that supports O(1) operations for:
- enqueue (add to back)
- dequeue (remove from front)
- peek (view front)
- size
"""
class EfficientQueue:
"""
A queue with O(1) operations.
Example:
>>> q = EfficientQueue()
>>> q.enqueue(1)
>>> q.enqueue(2)
>>> q.peek()
1
>>> q.dequeue()
1
>>> len(q)
1
"""
def __init__(self):
# YOUR CODE HERE - use deque for O(1) operations
pass
def enqueue(self, item: Any):
"""Add item to back of queue. O(1)"""
pass
def dequeue(self) -> Any:
"""Remove and return front item. O(1). Raise IndexError if empty."""
pass
def peek(self) -> Any:
"""View front item without removing. O(1). Raise IndexError if empty."""
pass
def __len__(self) -> int:
"""Return number of items."""
pass
def __bool__(self) -> bool:
"""Return True if queue has items."""
pass
# ============================================================
# EXERCISE 6: LRU Cache from Scratch
# ============================================================
"""
Implement an LRU (Least Recently Used) cache without using
functools.lru_cache. Use OrderedDict for O(1) operations.
"""
from collections import OrderedDict
class LRUCache:
"""
Least Recently Used cache with O(1) get/set operations.
Example:
>>> cache = LRUCache(capacity=2)
>>> cache.put("a", 1)
>>> cache.put("b", 2)
>>> cache.get("a") # "a" is now most recently used
1
>>> cache.put("c", 3) # Evicts "b" (least recently used)
>>> cache.get("b")
None
"""
def __init__(self, capacity: int):
# YOUR CODE HERE
pass
def get(self, key: str) -> Optional[Any]:
"""
Get value for key. Returns None if not found.
Marks key as recently used.
"""
pass
def put(self, key: str, value: Any):
"""
Set value for key.
If at capacity, evict least recently used item.
"""
pass
def __contains__(self, key: str) -> bool:
"""Check if key exists in cache."""
pass
# ============================================================
# EXERCISE 7: Optimize Search Function
# ============================================================
"""
This function checks if any item in a large list matches certain criteria.
Optimize it using early termination and appropriate data structures.
"""
def slow_search(items: List[Dict], search_ids: List[int]) -> bool:
"""SLOW: Check if any item's id is in search_ids."""
matches = []
for item in items:
for search_id in search_ids:
if item['id'] == search_id:
matches.append(item)
return len(matches) > 0
def fast_search(items: List[Dict], search_ids: List[int]) -> bool:
"""
FAST: Check if any item's id is in search_ids.
Uses set for O(1) lookup and early termination.
Example:
>>> items = [{"id": 1}, {"id": 2}, {"id": 3}]
>>> fast_search(items, [5, 6, 2])
True
"""
# YOUR CODE HERE
pass
# ============================================================
# EXERCISE 8: Memory-Efficient Data Processing
# ============================================================
"""
Process a large dataset using generators to minimize memory usage.
"""
def process_data_memory_heavy(data: List[int]) -> List[int]:
"""MEMORY HEAVY: Creates multiple intermediate lists."""
# Step 1: Filter
filtered = [x for x in data if x > 0]
# Step 2: Transform
transformed = [x * 2 for x in filtered]
# Step 3: Filter again
result = [x for x in transformed if x < 1000]
return result
def process_data_memory_efficient(data):
"""
MEMORY EFFICIENT: Use generators for lazy evaluation.
Process data without creating intermediate lists.
Args:
data: Iterable of integers
Yields:
Processed values one at a time
Example:
>>> list(process_data_memory_efficient([1, -2, 3, 600]))
[2, 6] # 1*2=2, 3*2=6 (600*2=1200 filtered out)
"""
# YOUR CODE HERE - use generator expressions or yield
pass
# ============================================================
# EXERCISE 9: Batch Processing Optimization
# ============================================================
"""
Process items in batches for better performance.
"""
def process_one_by_one(items: List[str], processor: Callable) -> List[Any]:
"""SLOW: Process items one at a time with function call overhead."""
results = []
for item in items:
results.append(processor(item))
return results
def process_in_batches(
items: List[str],
processor: Callable,
batch_size: int = 100
) -> List[Any]:
"""
FASTER: Process items in batches to reduce overhead.
Args:
items: List of items to process
processor: Function that can process a list of items
batch_size: Number of items per batch
Returns:
Combined results from all batches
Example:
>>> def batch_processor(batch):
... return [x.upper() for x in batch]
>>> process_in_batches(["a", "b", "c"], batch_processor, batch_size=2)
["A", "B", "C"]
"""
# YOUR CODE HERE
pass
# ============================================================
# EXERCISE 10: Profile and Optimize
# ============================================================
"""
The following function has multiple performance issues.
Profile it, identify the bottlenecks, and create an optimized version.
Issues to find:
1. Inefficient string operations
2. Unnecessary repeated calculations
3. Poor data structure choice
4. Redundant operations
"""
def analyze_text_slow(text: str, keywords: list) -> dict:
"""SLOW: Analyze text for keyword occurrences."""
result = {
'word_count': 0,
'char_count': 0,
'keyword_counts': {},
'unique_words': []
}
# Count characters
for char in text:
result['char_count'] += 1
# Count words and find unique
words = text.lower().split()
for word in words:
result['word_count'] += 1
if word not in result['unique_words']:
result['unique_words'].append(word)
# Count keywords
for keyword in keywords:
count = 0
text_lower = text.lower() # Recalculated each time!
for word in text_lower.split():
if word == keyword.lower():
count = count + 1
result['keyword_counts'][keyword] = count
return result
def analyze_text_fast(text: str, keywords: list) -> dict:
"""
FAST: Optimized text analysis.
Returns:
Same structure as analyze_text_slow but computed efficiently.
Optimizations to apply:
- Use len() for counting
- Process text once
- Use set for unique words
- Use Counter for keyword counts
"""
# YOUR CODE HERE
pass
# ============================================================
# CHALLENGE: Implement a Profiled Function Registry
# ============================================================
"""
Create a registry that tracks function performance statistics.
"""
class ProfiledRegistry:
"""
Registry that tracks execution statistics for registered functions.
Example:
>>> registry = ProfiledRegistry()
>>>
>>> @registry.register
... def my_function(x):
... return x * 2
>>>
>>> my_function(5) # Tracked
10
>>> my_function(10) # Tracked
20
>>>
>>> stats = registry.get_stats("my_function")
>>> print(f"Calls: {stats['call_count']}")
Calls: 2
>>> print(f"Avg time: {stats['avg_time']:.4f}s")
"""
def __init__(self):
# YOUR CODE HERE
pass
def register(self, func: Callable) -> Callable:
"""Decorator to register and track a function."""
pass
def get_stats(self, func_name: str) -> Dict[str, Any]:
"""
Get statistics for a function.
Returns:
{
'call_count': int,
'total_time': float,
'avg_time': float,
'min_time': float,
'max_time': float,
}
"""
pass
def get_all_stats(self) -> Dict[str, Dict[str, Any]]:
"""Get stats for all registered functions."""
pass
def reset_stats(self, func_name: Optional[str] = None):
"""Reset stats for one or all functions."""
pass
# ============================================================
# SOLUTIONS (Uncomment to check your work)
# ============================================================
"""
# Solution 1: Timer Decorator
def timed(runs: int = 1):
def decorator(func):
@functools.wraps(func)
def wrapper(*args, **kwargs):
total_time = 0
result = None
for _ in range(runs):
start = time.perf_counter()
result = func(*args, **kwargs)
total_time += time.perf_counter() - start
avg_time = total_time / runs
print(f"{func.__name__}: avg {avg_time:.4f}s over {runs} runs")
return result
return wrapper
return decorator
# Solution 2: Memoize with TTL
def memoize_with_ttl(ttl_seconds: float):
def decorator(func):
cache = {}
@functools.wraps(func)
def wrapper(*args):
now = time.time()
if args in cache:
result, timestamp = cache[args]
if now - timestamp < ttl_seconds:
return result
result = func(*args)
cache[args] = (result, now)
return result
wrapper.cache = cache
wrapper.clear_cache = lambda: cache.clear()
return wrapper
return decorator
# Solution 3: Fast Duplicate Finder
def find_duplicates_fast(items: list) -> list:
seen = set()
duplicates = set()
for item in items:
if item in seen:
duplicates.add(item)
seen.add(item)
return list(duplicates)
# Solution 4: Fast Report Builder
def build_report_fast(items: List[Dict]) -> str:
parts = ["=== Report ==="]
for item in items:
parts.append(f"Name: {item['name']}")
parts.append(f"Value: {item['value']}")
parts.append("-" * 20)
return "\\n".join(parts)
# Solution 5: Efficient Queue
class EfficientQueue:
def __init__(self):
self._data = deque()
def enqueue(self, item: Any):
self._data.append(item)
def dequeue(self) -> Any:
if not self._data:
raise IndexError("Queue is empty")
return self._data.popleft()
def peek(self) -> Any:
if not self._data:
raise IndexError("Queue is empty")
return self._data[0]
def __len__(self) -> int:
return len(self._data)
def __bool__(self) -> bool:
return bool(self._data)
# Solution 6: LRU Cache
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key: str) -> Optional[Any]:
if key not in self.cache:
return None
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key: str, value: Any):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)
def __contains__(self, key: str) -> bool:
return key in self.cache
# Solution 7: Fast Search
def fast_search(items: List[Dict], search_ids: List[int]) -> bool:
search_set = set(search_ids)
return any(item['id'] in search_set for item in items)
# Solution 8: Memory Efficient Processing
def process_data_memory_efficient(data):
filtered = (x for x in data if x > 0)
transformed = (x * 2 for x in filtered)
return (x for x in transformed if x < 1000)
# Solution 10: Fast Text Analysis
from collections import Counter
def analyze_text_fast(text: str, keywords: list) -> dict:
text_lower = text.lower()
words = text_lower.split()
word_counts = Counter(words)
keywords_lower = {k.lower() for k in keywords}
return {
'word_count': len(words),
'char_count': len(text),
'keyword_counts': {k: word_counts.get(k.lower(), 0) for k in keywords},
'unique_words': list(set(words))
}
"""
if __name__ == "__main__":
print("Performance Optimization Exercises")
print("=" * 50)
print("\nComplete the exercises above to practice:")
print("- Timing and profiling")
print("- Caching strategies")
print("- Algorithm optimization")
print("- Memory efficiency")
print("- Data structure selection")
print("\nUncomment the solutions to check your work!")