2 ms·
If I had a dollar for every time someone who had 30 seconds of accumulated knowledge about Dynamic Programming tried to argue with me that caching and memoizati
by hinkley 3y ago
If I had a dollar for every time someone who had 30 seconds of accumulated knowledge about Dynamic Programming tried to argue with me that caching and memoization are the same thing, I'd have enough for a nerf bat to hit them with.
(Briefly: memoization is local shared state, caches are global shared state, which is a whole other set of problems. And caching is hoping you'll need something eventually, where as memoization is knowing you will need it immediately.)
A couple years ago I watched a very long video on Dynamic Programming and learned a new term: Tabulation. If memoization is encountering a common sub-problem and holding onto it, tabulation is seeking them out, answering the sub-problems before they can come up organically.
It's much harder to derive the tabulation answer, but I find it's usually easier to reason about after the fact. Which is enormously helpful when you go back to add new features or fix old bugs.
Look-Up Tables are fixed-size tabulations. The space complexity of tabulation is often ≥ O(n), while LUT are a fixed size, but big enough to reduce the computation time by a constant factor, like 10 or 100.
- sakras 3y agoIt sounds like your distinction of tabulation vs memoization is similar to the concept of bottom-up vs top-down DP. Bottom-up: build the table up eagerly, top-down: recurse down and fill in the table lazily.
- hinkley 3y agoYeah I'm not sure how widespread his nomenclature was. I was just glad to have more vocabulary for people who have trivialized the entire discipline down to 'caching'.