Path: csiph.com!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.programming Subject: Re: on distinguishing memoization and dynamic programming Date: Fri, 12 Jan 2024 16:41:52 -0800 Organization: A noiseless patient Spider Lines: 55 Message-ID: <86a5pam5db.fsf@linuxsc.com> References: <87frzembwb.fsf@yaxenu.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: dont-email.me; posting-host="3f630b650db0c173ee1e204d093e8dad"; logging-data="3840806"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18UYHXIx9T/6JKgMFzeIgcsJ+llDQOfzpQ=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:lxIQz9RmmJo6iQzf9UZc03YoLlo= sha1:rtesozV4mjJn9ScxrvXRC3sRq24= Xref: csiph.com comp.programming:16723 Julieta Shem writes: > I was trying to distinguish memoization from dynamic programming --- in > a technical way --- and I failed. Can you write something like a > mathematical definition of each one? Memoization is a stand-alone technique for improving the performance of pure functions, which is to say functions whose result depends only on their inputs. The idea is when a result is calculated for a particular set of inputs, the result is saved so that it needn't be calculated again for the same set of inputs. If lookup is cheaper than recomputing, it's a win to save the result (up to some amount of saved results, obviously) so it doesn't have to be calculated again. By analogy, memoization is more or less a software cache at the level of individual functions. Note that there needn't be any particular relationship between the inputs and the results. A function might be recursive, like the fibonacci function, or the different results might be completely independent, with no recursion at play. Memoization doesn't care - the only things that matter is that the output is a pure function of the inputs, and that lookup is cheaper than recalculation. When those two conditions hold, memoization can improve performance (as before, depending on how much storage is needed to accomplish that). Dynamic programming is used when there is a single large-scale problem for which it is necessary to solve a significant number of smaller-scale problems, and there are relationships between the smaller problems such that there are dependencies on those smaller problems that force some to be solved before others. The key idea of dynamic progamming is to determine, based on an analysis of the overall problem, an ordering for the smaller problems that allows each smaller problem to be solved exactly once. It is common for dynamic programming problems that the smaller problems make up a regular array (of whatever dimensionality) so that results can be stored in a regular structure, and looking up previously solved subproblems can be done just by doing a normal indexing operation. An abstract example of a dynamic programming problem is calculating a function F of three arguments I, J, K, where computing F depends on several values of F( {i values}, {j values}, {k values} ), where each {i value} is <= I, each {j value} is <= J, and each {k value} is <= K. By tabulating F in increasing order of I+J+K, we arrange for the earlier values to be available when computing F(I,J,K). Incidentally, it can happen that F(I,J,K) is a function of lesser values of i, j, or k, and also on F(I,J,K) itself. When that happens we get an /equation/ that must be solved for F(I,J,K), and the equation can be solved because values for all the dependent (smaller) sub-problems are already known. I wanted to answer your question because memoization and dynamic programming are really nothing like each other, I thought it would be good to clarify the two concepts. Hopefully you got some value out of my explanations here.