3 ms·
In real code I've only actually seen memoization used as a cache. That leaves cache validation to some higher level which is in a poor position to do it very we
by jmull 2y ago
In real code I've only actually seen memoization used as a cache. That leaves cache validation to some higher level which is in a poor position to do it very well. In my experience, most often it means someone has to figure out what things to manually restart, and when.
- kazinator 2y agoYou mean invalidation? Speaking of invalidation, the memoized Fibonacci will work even with a cache of 1 item that is replaced each time. (By work, I mean slash exponential time to linear.) If you calculate fib(n - 2) first and cache it, evacuating everything else in the process, that is good enough: when f(n - 1) needs f(n - 2), it finds it instead of recursing, and so the multply-and-surrender logic is disrupted, resulting in time proportional to n.