Is there a theorem / single formula, that describes the often necessary tradeoff between memoiziation (for example that of a certain variable x) and effective computation as written in any common form such as runtime?

(A good purely theoretical startig point to work with could really be a number sequence...)

  • 2
    $\begingroup$ What do you expect from answer if answer is "no"? What model of computation do you have in mind? $\endgroup$ – Evil Oct 7 at 20:22
  • $\begingroup$ I thought of Turing machines, but really any model with the possibility of calculation could be used $\endgroup$ – SomeGuy Oct 8 at 5:28

I'm not sure I understand your question entirely, but I'm going to assume that you're talking about the space-time tradeoff. The gist of the aforementioned tradeoff is as you put it, in the context of an algorithm, the balance you have to strike between the memory it will use (its space complexity) and the time it will take to run (its time complexity). Obviously, the faster you want it to run, the more memory you will need to use, and vice-versa. The tradeoff is in general present in most fields of computer science besides pure algorithm design, but this provides I believe a nice abstract starting point.

Let's start with the bad news: from a rigid theoretical computer science point of view, tough luck, no such unifying formula exists and it is actually a fairly well-known open problem (for more info you may want to check this question about the space-time tradeoff, but it is fairly technical). Even worse, few general results are known about this.

Now the good news, of which there are two. First of all, I highly encourage you to think about the problem yourself and come up with your own (even incomplete theory), as it isn't very hard to qualitatively come up with some pretty interesting remarks.

For instance, let us try to develop a (very!) basic theory here. At its core, a result to be obtained through computation can be decomposed into a bunch of dependencies and operations. For instance, to compute c=a+b, you need to know a and b (the dependencies, also known as operands), and add them together (the operation). This decomposition can be applied iteratively many times until all of the dependencies are directly known (present in the problem instance/the input you receive). There are many ways of looking at this, one of them is as a DFG (Data Flow Graph), but there are of course many more with varying degrees of complexity, which each offer accuracy for different factors. For convenience, have this nice picture of a DFG:

DFG example

Abstracting the compute cost of one operation to 1 (no matter its complexity or the number of operands), we can see that the lower time bound to obtain the value of a node of the DFG is equal to the length of the longest path from the node to an input operand. Indeed, if we assume entirely parallel computation (possible if no interdependencies exist between nodes at the same depth), this bound can be attained. If we would however assume entirely serial computation, we would need to add the cost of obtaining each result one by one and I choose not complicate myself with this here. If we add memoization, this time becomes the length of the longest path from the node to a memoized operand (but we stop when we reach the first one on a given path backwards from the target node).

This sounds suspiciously simple, right? If we know the DFG beforehand and we assume parallelism, it indeed isn't very complicated, but a few avenues of thought would be if we consider as mentioned serial (or partly serial execution) and then memoization strategy.

I'll just point out that while it's not what you're looking for, for practical purposes it's always a good idea to benchmark on real hardware as well.

Now since I mentioned that there are two good news: there are bounds on this tradeoff which have been found and proven for specific problems and computation models. If you're interested, you can find some of these purely theoretical results in this answer.

  • $\begingroup$ I tried to answer your post below. Cheers ✌ $\endgroup$ – SomeGuy Oct 9 at 13:48

To more generally answer @DavidChian,

Thank you very much, especially for cheering me up a bit. Now, if I understood your post right, you say, that there isn't a general way, but you still gave the following starting point: instead of my proposed number sequence, you choose a Data Flow Graph (DFG). Using your model, where the most effective space-time tradeoff for like n computations defined for specific variables and operands, such as simplicity-wise 0 Interdependencies (guaranteed for by mere sequential computations / iterations like: x2 = x1 + 1 instead of like: Find me the meaning of everything :-) ), would possibly be calculated by something like this:
Cost C(Compute) of completing some defined computation Cost C(Memorize) of saving and reopening some defined memory address (which always is a variable with some states (numerically like f. e. x = 3.14…) Then for C(c) = C(m) the cost of both memorization and that of direct computation are equal, because their functions cross each other. Is it now possible that the biggest problem remaining is that of (a) parallel processing and (b) the cost of the meta-optimization we just did, that will always (due to the halting problem) be > the cost of the computation itself!?

  • $\begingroup$ Wel, let's say we indeed define a cost function for computing $c$ and one for memoizing $m$. Both of these take as input a target $t$ and output the cost of respectively computing and memoizing it $c$ (in arbitrary units if we want to stay in the real world and not just mathematical abstraction). The gains for an isolated target $t$ then would be: $c(t) - m(t)$. This can generalize to multiple interdependent targets, and it then becomes a problem of maximizing the total gain by choosing what to memoize and what to compute. $\endgroup$ – David Cian Oct 9 at 21:41
  • $\begingroup$ Assuming you define target as google does for me: "a target is a file, device or any type of location to which data is moved or copied. Many computer commands involve copying data from one place to another. One says that the computer copies from the source to the target (or destination).", you're saying, that is just an rather arbitrary optimization? $\endgroup$ – SomeGuy Oct 10 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.