| September 10, 2001 | Quantitative Analysis of Memoization | Slide #6 |
h is the hit rate
f is the time it takes to call the original function
K is the average cache management overhead
Average time spent per call to m: (1-h)f + K
The average time for the unmemoized function is f
Time saved (per call) by memoizing: f - (1-h)f - K
Equals hf - K
hf is the benefit. K is the cost.
We want hf > K
| Next | |
Copyright © 2001 M-J. Dominus |