Dart
Optimization
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.
Exercise 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)}').
Show example 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)}');
}
Test yourself
-
What does memoization do?
- Encrypts
- Serializes
- Compresses
- Computes with cache
Show answer
Computes with cache — memoization speeds up repeated computation with a cache.
-
Match the optimization concepts
- cache
- Cache
- fib
- Fibonacci
- containsKey
- Key exists
- memoize
- Memoization
-
Cache key check
if (____(n)) return cache[n]!;
Show answer
if (cache.containsKey(n)) return cache[n]!;
Next lesson: Profiling
