Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What does the term "memoize" imply?

Tags:

memoization

Comparing the terms "memoize" and "cache" and in reading Wikipedia's memoization entry, do people agree that using the term "memoize" implies

  • The memoized result is kept in the process' memory; in other words, it isn't stored in memcached .
  • One only "memoizes" functions, as in mathematical functions, e.g. Fibonacci, not values that may change over time, e.g. the number of registered users on the web site?

If you're doing anything else than the above, then one is just caching a result?

like image 300
Blair Zajac Avatar asked Dec 12 '22 19:12

Blair Zajac


2 Answers

I'm not sure, but my understanding is that memoization requires that given a function y = f(u), that f be deterministic (that is, for a given u, the y must always be the same), in order that the results of f may be stored.

Caching to me seems to be more of a problem of determining what pieces of data are accessed frequently, and keeping those data in fast storage.

The former is deterministic while the latter is stochastic.

like image 99
Gilead Avatar answered Mar 11 '23 20:03

Gilead


I believe that memoizing a function allows you to locally cache the result of a function for a given set of arguments. It's almost like:

function f(a, b, c) {
  if (a==1 && b==2 && !c) {
    return 5;
  } else if (a==1 && b==3 && !c) {
    return 17.2;
  } /* ... etc ... */

  // some horribly long/complex/expensive calculation
  return result;
}

but with the initial huge "if" block being handled automatically and far more efficiently, and being added to as the function is called with different arguments.

Note that you can only memoize a function that is deterministic and has no side effects. This means that the function's result can only depend on its inputs, and it cannot change anything when it is run.

So in short, memoization is function-local caching in very specific circumstances, and so it's a specialisation of regular caching.

like image 22
DMI Avatar answered Mar 11 '23 19:03

DMI