4 ms·

No disrespect to the dude that I learned Haskell from, but a) he doesn’t achieve his original goal and b) the goal is much less practically useful than he impli

by moomin 3y ago

No disrespect to the dude that I learned Haskell from, but a) he doesn’t achieve his original goal and b) the goal is much less practically useful than he implies. In practice an awful lot of the functions you want to memoize a) involve continuations and b) want some way of evicting things from the cache. Haskell has no end of cute tricks for doing deterministic functions, it’s just that deterministic functions are programming’s easy mode.

hinkley 3y ago
Memoization is also entry level DP, and too easily confused with caching (if I had a dollar for every time someone equated the two, I could buy a baseball bat to knock heads). If you want the power of dynamic programming you need to get at least as far as tabulation.
- hinkley 3y ago
  Cowards. Respond if you have problems. I’ve just gone through removing “memoization” from two parts of our code that were difficult to understand even without the caching layer. The reason I did the second one is because the first one went so well I wanted to see if it was a fluke. In doing the first, what I did was replace depth first execution with a tree scan. At the end I had a set of actions that needed to happen, and why. Essentially a plan for the execution. That’s a great spot for a breakpoint if the code or a test are failing, but it also yields you a set with all of the duplicates removed, instead of a graph. And in this case the number of data operations to combine all of the data is n+1 instead of > nlog(n) based on the number of duplicates. It also pointed out other optimizations that were possible. In the second case it also surfaces a potential ordering problem, and the added wrinkle was that some warning messages were being repeated, quite confusing to other developers. Those could be reduced from eight to three. In both cases memory usage was reduced (and in the one case the code was a bottleneck for starting short lived processes) because you don’t cache anything that is used once. There is no clever trick you need to work out. It just works, and the mechanism is perfectly readable and reason-able.
  - nequo 3y ago
    Your HN karma is nearly 33 thousand. Why get so aggressive about a few down votes? I was among those who down voted your earlier comment, and I did so because of the talk about knocking heads with a baseball bat.
    - hinkley 3y ago
      This account is over 3000 days old so that’s less than eleven imaginary internet points per day. Which is really how it mostly goes. Three points here, six points there. Nothing much for a couple of days, then something up or down. It’s not the points it’s the conversation. One of the few times this year I scored highly, I said virtually the same thing in two parts of the same post. Nothing sarcastic, no dark humor, something like +40 points and responses for one, no responses and oblivion for the other. I only know they former because the latter made me curious. Popularity is weird, not that I’m probably telling you anything new. There are some ideas that are only popular here for a certain crowd, and if they see it first you’re good, if they don’t it’s either gone, or you come back a few hours later to see you’ve swung from -2 to +5. It’s a nice vindication but your flow is gone and so I never feel like those conversations get as far. Maybe that person is a kook, or maybe you’ve had a narrow experience. Or they have. Maybe if you talk about it you’ll learn which. One of those topics, based on previous experience (here, elsewhere, and I’m person”, seems to be, “DP is much more than caching”. Anyway, thanks for replying.
- lostmsu 3y ago
  I've been taught DP via tabulation and struggled to get it. Then I learned the memoization trick and I am never coming back simply because memoization is much easier to reason about, and the resulting code is often much cleaner. As the result, I would only resort to tabulation if I need to match some performance goal and memoization does not cut it.

by moomin 3y ago

hinkley 3y ago

Memoization is also entry level DP, and too easily confused with caching (if I had a dollar for every time someone equated the two, I could buy a baseball bat to knock heads). If you want the power of dynamic programming you need to get at least as far as tabulation.

hinkley 3y ago
Cowards. Respond if you have problems. I’ve just gone through removing “memoization” from two parts of our code that were difficult to understand even without the caching layer. The reason I did the second one is because the first one went so well I wanted to see if it was a fluke. In doing the first, what I did was replace depth first execution with a tree scan. At the end I had a set of actions that needed to happen, and why. Essentially a plan for the execution. That’s a great spot for a breakpoint if the code or a test are failing, but it also yields you a set with all of the duplicates removed, instead of a graph. And in this case the number of data operations to combine all of the data is n+1 instead of > nlog(n) based on the number of duplicates. It also pointed out other optimizations that were possible. In the second case it also surfaces a potential ordering problem, and the added wrinkle was that some warning messages were being repeated, quite confusing to other developers. Those could be reduced from eight to three. In both cases memory usage was reduced (and in the one case the code was a bottleneck for starting short lived processes) because you don’t cache anything that is used once. There is no clever trick you need to work out. It just works, and the mechanism is perfectly readable and reason-able.
- nequo 3y ago
  Your HN karma is nearly 33 thousand. Why get so aggressive about a few down votes? I was among those who down voted your earlier comment, and I did so because of the talk about knocking heads with a baseball bat.
  - hinkley 3y ago
    This account is over 3000 days old so that’s less than eleven imaginary internet points per day. Which is really how it mostly goes. Three points here, six points there. Nothing much for a couple of days, then something up or down. It’s not the points it’s the conversation. One of the few times this year I scored highly, I said virtually the same thing in two parts of the same post. Nothing sarcastic, no dark humor, something like +40 points and responses for one, no responses and oblivion for the other. I only know they former because the latter made me curious. Popularity is weird, not that I’m probably telling you anything new. There are some ideas that are only popular here for a certain crowd, and if they see it first you’re good, if they don’t it’s either gone, or you come back a few hours later to see you’ve swung from -2 to +5. It’s a nice vindication but your flow is gone and so I never feel like those conversations get as far. Maybe that person is a kook, or maybe you’ve had a narrow experience. Or they have. Maybe if you talk about it you’ll learn which. One of those topics, based on previous experience (here, elsewhere, and I’m person”, seems to be, “DP is much more than caching”. Anyway, thanks for replying.
lostmsu 3y ago
I've been taught DP via tabulation and struggled to get it. Then I learned the memoization trick and I am never coming back simply because memoization is much easier to reason about, and the resulting code is often much cleaner. As the result, I would only resort to tabulation if I need to match some performance goal and memoization does not cut it.