Optimization
- Dart course
- Advanced
- Lesson 76/83
- 5 min
Learn common optimization techniques.
Optimization and caching
Optimization is changing code so it runs faster. One of the most effective methods is caching: store a result that is computed again and again in a map. When the same input comes, you read from the map instead of recomputing.
The classic example is Fibonacci. fib(n) = fib(n-1) + fib(n-2) in the naive form computes the same subproblem many times; fib(40) makes millions of calls. If you keep a cache map and store each fib(k) result, each value is computed once. This technique is called memoization; it lowers the complexity from exponential to linear.
Memoized fibonacci
The cached fibonacci: keep a map final cache = <int, int>{};. Inside fib(n) first check cache.containsKey(n); if present return cache[n]!. Otherwise compute fib(n-1) + fib(n-2) and store it with cache[n] = result.
fib(10) = 55, fib(20) = 6765. Without cache fib(20) makes 10946 calls; with cache only 20. The ! (null assertion) says the value is not null even though the map returns int?. This pattern is the basis of dynamic programming.
Practice Memoized fibonacci
Define the map final cache = <int, int>{}; (outside main). Write int fib(int n): if n < 2 return n; if cache.containsKey(n) return cache[n]!; else compute fib(n-1) + fib(n-2), store with cache[n] = result, return it. In main add print('fib(10): ${fib(10)}') and print('fib(20): ${fib(20)}').
Starter code
// define the cache map
// write the fib function (with caching)
void main() {
// print fib(10) and fib(20) results
}Sample solution
final cache = <int, int>{};
int fib(int n) {
if (n < 2) return n;
if (cache.containsKey(n)) return cache[n]!;
final result = fib(n - 1) + fib(n - 2);
cache[n] = result;
return result;
}
void main() {
print('fib(10): ${fib(10)}');
print('fib(20): ${fib(20)}');
}Expected output
fib(10): 55 fib(20): 6765
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What does memoization do?
- Encrypts
- Serializes
- Compresses
- Computes with cache Correct answer
Explanation: memoization speeds up repeated computation with a cache.
2 Match the optimization concepts
| Term | Meaning |
|---|---|
cache |
Cache |
fib |
Fibonacci |
containsKey |
Key exists |
memoize |
Memoization |
3 Cache key check
if (____(n)) return cache[n]!;if (cache.containsKey(n)) return cache[n]!;Explanation: cache.containsKey(n) checks if it is in the cache.