3 ms·

The bottom-up tabularization isn't always necessary, but it's a key technique that is not just "avoiding overhead" or whatever. Doing the top-down memoization,

by OskarS 3y ago

The bottom-up tabularization isn't always necessary, but it's a key technique that is not just "avoiding overhead" or whatever. Doing the top-down memoization, you don't know which subproblems you need to store at any given, but going bottom-up, you do, and you can usually be much more clever about memory usage and overhead. The obvious example is Fibonacci numbers: the "top down" memoized version needs to store every Fibonacci number in memory, because you don't know what number the recursion is asking for. But if you do it "bottom up", you know that to calculate f(N), you only need f(N-2) and f(N-1). Therefore, you only need to store the last two numbers, reducing your memory usage from O(n) to O(1). This principle almost always applies in DP problems: for the "edit distance" problem, the number possible values for the function is N^2 (where N is the size of the two words you need to compare, assuming they're similar sizes), so the memoized version takes O(N^2) memory. But if you do it the "bottom up" version, you realize that to calculate all values in a row, you just need the previous row of values. So it takes memory from O(N^2) to O(N). Point being: turning the recursion "upside down" is not just a thing you do to be clever (or to avoid "function calling overhead", something like that), it has very real algorithmic benefits, usually because it takes MUCH less memory to do it like that.

hansvm 3y ago
I think their point is that naive caching attempts still result in duplicate work, and if you start by viewing the problem recursively then DP is a clever insight allowing you to avoid that duplicate work. You're right; it's not _just_ function calling overhead or anything minor; it often represents major Big-O improvements. I think that's in alignment with what they're saying. I like your insight about Fibonacci needing less state than a naive DP would suggest. Diving into that a bit, DP implementations represent a DAG. More importantly, for all the problems that easily fit into DP that DAG has small numbers of "local" connections -- you can partition it into at least O(some_meaningful_dimension) many topologically sorted levels where each level only depends on a small, known, finite number of previous levels (often 1-2), not deeper DAG nodes. A clever choice of order of operations then looks for a min-cut on that graph, proceeding through those levels. Fib has at most O(n) levels and at least O(n) state for naive DP, so a clever implementation has O(n/n)=O(1) state. Edit distance has at most O(n) levels and at least O(n^2) state, so a clever implementation has O(n^2/n)=O(n) state. I did something similar for some DP probability calculation [0], and it reduces state from quadratic to linear. Fibonacci is, slightly pedantically, one of the worst algorithms to analyze this way. Only the smallest inputs actually fit in machine integers, and the exponential increase in the size of any bigints involved really puts a damper on a naive Big-O analysis. Fib mod 2^64 (or some biggish prime) fits into the spirit of things better. [0] https://github.com/hmusgrave/zdps https://github.com/hmusgrave/zdps
- qsantos 3y ago
  Regarding Fibonacci, the recursive formula is much more efficient anyway! Oh, not _that_ recursive formula. That one: [1], from [2]. Basically, it allows you to implement in O(log n) arithmetic operations. [1] https://wikimedia.org/api/rest_v1/media/math/render/svg/64b95fd1ea97b7a4315e8ee4ddb7f6b44c7681f0 https://wikimedia.org/api/rest_v1/media/math/render/svg/64b9... [2] https://en.wikipedia.org/wiki/Fibonacci_sequence#Matrix_form https://en.wikipedia.org/wiki/Fibonacci_sequence#Matrix_form
  - hansvm 3y ago
    Only under the word-RAM model of computation though. The phrase "arithmetic operation" is doing a lot of heavy lifting. On a real computer, the output size of Fib is O(2^n), requiring O(n) bits of space, and O(n) assembly instructions (at a minimum, and for other reasons that minimum can be attained). The exponential nature of the problem additionally means you hit that Big-O curve for extraordinarily small inputs (as opposed to, e.g., a hash table where technically access isn't O(1) but nobody cares). Separately though, that's a fun trick :)
    - qsantos 3y ago
      That's why I phrased it that way. But since you mentioned working modulo 2^64, I thought that would count :-). It's useful to make it explicit anyway for people who might miss that, so thanks!
      - hansvm 3y ago
        oic. I missed that nuance. Thanks for the clarification. Again, neat formula, happy to see your comments :)

by OskarS 3y ago

hansvm 3y ago

I think their point is that naive caching attempts still result in duplicate work, and if you start by viewing the problem recursively then DP is a clever insight allowing you to avoid that duplicate work. You're right; it's not _just_ function calling overhead or anything minor; it often represents major Big-O improvements. I think that's in alignment with what they're saying. I like your insight about Fibonacci needing less state than a naive DP would suggest. Diving into that a bit, DP implementations represent a DAG. More importantly, for all the problems that easily fit into DP that DAG has small numbers of "local" connections -- you can partition it into at least O(some_meaningful_dimension) many topologically sorted levels where each level only depends on a small, known, finite number of previous levels (often 1-2), not deeper DAG nodes. A clever choice of order of operations then looks for a min-cut on that graph, proceeding through those levels. Fib has at most O(n) levels and at least O(n) state for naive DP, so a clever implementation has O(n/n)=O(1) state. Edit distance has at most O(n) levels and at least O(n^2) state, so a clever implementation has O(n^2/n)=O(n) state. I did something similar for some DP probability calculation [0], and it reduces state from quadratic to linear. Fibonacci is, slightly pedantically, one of the worst algorithms to analyze this way. Only the smallest inputs actually fit in machine integers, and the exponential increase in the size of any bigints involved really puts a damper on a naive Big-O analysis. Fib mod 2^64 (or some biggish prime) fits into the spirit of things better. [0] https://github.com/hmusgrave/zdps https://github.com/hmusgrave/zdps

qsantos 3y ago
Regarding Fibonacci, the recursive formula is much more efficient anyway! Oh, not _that_ recursive formula. That one: [1], from [2]. Basically, it allows you to implement in O(log n) arithmetic operations. [1] https://wikimedia.org/api/rest_v1/media/math/render/svg/64b95fd1ea97b7a4315e8ee4ddb7f6b44c7681f0 https://wikimedia.org/api/rest_v1/media/math/render/svg/64b9... [2] https://en.wikipedia.org/wiki/Fibonacci_sequence#Matrix_form https://en.wikipedia.org/wiki/Fibonacci_sequence#Matrix_form
- hansvm 3y ago
  Only under the word-RAM model of computation though. The phrase "arithmetic operation" is doing a lot of heavy lifting. On a real computer, the output size of Fib is O(2^n), requiring O(n) bits of space, and O(n) assembly instructions (at a minimum, and for other reasons that minimum can be attained). The exponential nature of the problem additionally means you hit that Big-O curve for extraordinarily small inputs (as opposed to, e.g., a hash table where technically access isn't O(1) but nobody cares). Separately though, that's a fun trick :)
  - qsantos 3y ago
    That's why I phrased it that way. But since you mentioned working modulo 2^64, I thought that would count :-). It's useful to make it explicit anyway for people who might miss that, so thanks!
    - hansvm 3y ago
      oic. I missed that nuance. Thanks for the clarification. Again, neat formula, happy to see your comments :)