5 ms·

That tends to blow up your memory. And even if you have huge amounts of memory available, using a big cache will slow down your program enormously.

by 317070 3y ago

CyberDildonics 3y ago
You: Dynamic programming means saving the results of computations Me: That's just normal programming, there is no reason to use a term that someone made up in the 60s to as intentionally nonsensical. You: That will blow up your memory and slow down your program! What are you talking about here? All I said was that what you described was normal programming. I didn't come up with anything different, we're still talking about whatever you wrote. Somehow now storing data, something that happens in every program ever made, 'blows up memory'.
- 317070 3y ago
  But there is a difference between memoization and dynamic programming. Memoization or otherwise indiscriminately storing the results of computations will blow up your memory use on many problems, where a dynamic programming approach would not. Dynamic programming does not mean saving the results of computations, it is about saving the _minimal_ number of results, without having to recompute already solved subproblems later on. I agree that the name chosen is nonsensical, but the concept is very much a real thing. And a quite important one at that.
  - Shorel 3y ago
    Yep, it has a nonsensical name, that's the point I wanted to convey. Actual "dynamic programming" would be self-modifying code, or something just as sophisticated, IMO. Or Prolog =) What about "memoization optimized backtracking"?
    - 317070 3y ago
      I'd propose "Minimal memory optimal subproblem iteration"? Or "minimem iteration" for the friends? I don't like mentioning memoization in DP's name, as I have had a lot of problems explaining students how you go beyond the memoization approach.
  - CyberDildonics 3y ago
    Your previous comment: dynamic programming will keep around previous subproblem solutions Your comment here: Dynamic programming does not mean saving the results of computations indiscriminately storing the results of computations This is not something that happens. No is out there storing a bunch of stuff they don't need on purpose, running out of memory, then calling it a day. That's like saying "some people walk straight into walls, but in dynamic walking we go around walls!". it is about saving the _minimal_ number of results, without having to recompute already solved subproblems later on. Again, this is just what programming is some times. You save results instead of recomputing stuff.
    - 317070 3y ago
      > No is out there storing a bunch of stuff they don't need on purpose, running out of memory, then calling it a day. There are a lot of people (such as my students) that would take a DP problem, solve with recursion, throw some caching [0] in and call it a day. They are often surprised by the 1000x speedups using a DP algorithm instead, no caching needed. [0] https://docs.python.org/3/library/functools.html#functools.cache https://docs.python.org/3/library/functools.html#functools.c... > Again, this is just what programming is some times. You save results instead of recomputing stuff. I'm sorry, but I still don't get the argument you are making. That DP is part of programming? Well, yes?
      - CyberDildonics 3y ago
        That DP is part of programming? Dynamic programming was a made up nonsense term from the 50s to be opaque and vague so they wouldn't be bothered. It doesn't mean anything, but people try to make up some backwards rationalization. Computing a factorial by recursively computing all the other previous factorials if you have any of them already done is an insane way to work. Doing something straightforward and sane like saving some results is like walking on broken glass then calling putting something over your feet "shoe walking". There is no special fancy label for doing the simple sane version of something.

That tends to blow up your memory. And even if you have huge amounts of memory available, using a big cache will slow down your program enormously.

by 317070 3y ago

That tends to blow up your memory. And even if you have huge amounts of memory available, using a big cache will slow down your program enormously.

CyberDildonics 3y ago

You: Dynamic programming means saving the results of computations Me: That's just normal programming, there is no reason to use a term that someone made up in the 60s to as intentionally nonsensical. You: That will blow up your memory and slow down your program! What are you talking about here? All I said was that what you described was normal programming. I didn't come up with anything different, we're still talking about whatever you wrote. Somehow now storing data, something that happens in every program ever made, 'blows up memory'.

317070 3y ago
But there is a difference between memoization and dynamic programming. Memoization or otherwise indiscriminately storing the results of computations will blow up your memory use on many problems, where a dynamic programming approach would not. Dynamic programming does not mean saving the results of computations, it is about saving the _minimal_ number of results, without having to recompute already solved subproblems later on. I agree that the name chosen is nonsensical, but the concept is very much a real thing. And a quite important one at that.
- Shorel 3y ago
  Yep, it has a nonsensical name, that's the point I wanted to convey. Actual "dynamic programming" would be self-modifying code, or something just as sophisticated, IMO. Or Prolog =) What about "memoization optimized backtracking"?
  - 317070 3y ago
    I'd propose "Minimal memory optimal subproblem iteration"? Or "minimem iteration" for the friends? I don't like mentioning memoization in DP's name, as I have had a lot of problems explaining students how you go beyond the memoization approach.
- CyberDildonics 3y ago
  Your previous comment: dynamic programming will keep around previous subproblem solutions Your comment here: Dynamic programming does not mean saving the results of computations indiscriminately storing the results of computations This is not something that happens. No is out there storing a bunch of stuff they don't need on purpose, running out of memory, then calling it a day. That's like saying "some people walk straight into walls, but in dynamic walking we go around walls!". it is about saving the _minimal_ number of results, without having to recompute already solved subproblems later on. Again, this is just what programming is some times. You save results instead of recomputing stuff.
  - 317070 3y ago
    > No is out there storing a bunch of stuff they don't need on purpose, running out of memory, then calling it a day. There are a lot of people (such as my students) that would take a DP problem, solve with recursion, throw some caching [0] in and call it a day. They are often surprised by the 1000x speedups using a DP algorithm instead, no caching needed. [0] https://docs.python.org/3/library/functools.html#functools.cache https://docs.python.org/3/library/functools.html#functools.c... > Again, this is just what programming is some times. You save results instead of recomputing stuff. I'm sorry, but I still don't get the argument you are making. That DP is part of programming? Well, yes?
    - CyberDildonics 3y ago
      That DP is part of programming? Dynamic programming was a made up nonsense term from the 50s to be opaque and vague so they wouldn't be bothered. It doesn't mean anything, but people try to make up some backwards rationalization. Computing a factorial by recursively computing all the other previous factorials if you have any of them already done is an insane way to work. Doing something straightforward and sane like saving some results is like walking on broken glass then calling putting something over your feet "shoe walking". There is no special fancy label for doing the simple sane version of something.