How to clear parts of a memoized function?

Question

I have a function of two variables, e.g.:

f[a_, b_] := f[a, b] = something f[a - 1, b - 1] etc

With the above code I used the concept of memoization to speed up the computation.

However, I have the problem that I run out of memory for large values of a and b.

Since my recursion is not very deep, I would like to clear the memory from time to time; for example, I calculate f[1000, 1000] and then remove all values of f[a, b] for a, b between 1 and something close to 1000.

However, I only found the Clear/ClearAll functions, which (unless I am missing something) clear everything indiscriminately. This is not what I want.

Is there a built-in function that does not clear all values of f[a, b], but just a specific range?

Answer 1

This is quite easy to achieve by direct manipulation of downvalues. Here's a simple example:

ClearAll[removeDownValues];
SetAttributes[removeDownValues, HoldAllComplete];
removeDownValues[p : f_[___]] :=
  DownValues[f] = DeleteCases[
    DownValues[f, Sort -> False],
    HoldPattern[Verbatim[HoldPattern][p] :> _]
   ];

Now let's memoize some values:

Do[f[1, i] = i, {i, 1, 10}];
DownValues[f]
(* -> {HoldPattern[f[1, 1]] :> 1, HoldPattern[f[1, 2]] :> 2, 
       HoldPattern[f[1, 3]] :> 3, HoldPattern[f[1, 4]] :> 4, 
       HoldPattern[f[1, 5]] :> 5, HoldPattern[f[1, 6]] :> 6, 
       HoldPattern[f[1, 7]] :> 7, HoldPattern[f[1, 8]] :> 8, 
       HoldPattern[f[1, 9]] :> 9, HoldPattern[f[1, 10]] :> 10} *)

If we no longer need some of these, we can remove them as follows:

removeDownValues[f[_, x_ /; 4 <= x <= 7]]
(* -> {HoldPattern[f[1, 2]] :> 2, HoldPattern[f[1, 1]] :> 1, 
       HoldPattern[f[1, 3]] :> 3, HoldPattern[f[1, 8]] :> 8, 
       HoldPattern[f[1, 9]] :> 9, HoldPattern[f[1, 10]] :> 10} *)

Performance will probably be fairly good if you need to remove a large number of memoized values at the same time, but you should bear in mind that resetting downvalues in this way requires rebuilding the hash table from scratch. As such, if you want to remove a few specific downvalues but do so many times, using Unset is probably a better choice. A timing comparison demonstrates that if you don't need to pattern match downvalues and can simply iterate over them instead, Unset is indeed preferable:

Do[f[1, i] = i, {i, 1, 1*^6}]; (* evaulated before each timing run below *)

removeDownValues[f[1, x_ /; 1000 <= x <= 999000]]; (* 3.67 seconds *)
removeDownValues[f[1, _]]; (* 3.39 seconds *)
Do[f[1, x] =., {x, 1000, 999000}]; (* 2.03 seconds *)

Answer 2

Preamble

I will present a sort of a packaged and automated solution, which uses deques and metaprogramming to automate caching. This should work for most normal pattern-based functions.

Deques

I will use Daniel Lichtblau's implementation for a deque, taken from his great account on Data Structures and Efficient Algorithms in Mathematica. Here it is:

newQueue[sym_Symbol] := {Unique[sym], 0, Null, 0, 0}
Clear[queueLength, emptyQueue, enQueue, deQueue];
qptr = 1; qlen = 2; qelem = 3; qfront = 4; qback = 5;
queueLength[Q_] := Q[[qlen]]
emptyQueue[Q_] := Q[[qlen]] == 0
SetAttributes[enQueue, HoldFirst]
enQueue[Q_, elem_] := 
  (Q[[qlen]]++; Q[[qfront]]++;Q[[qptr]][Q[[qfront]]] = elem;)
SetAttributes[deQueue, HoldFirst]
deQueue[Q_] := (
  Q[[qlen]]--; Q[[qback]]++;
  Q[[qelem]] = Q[[qptr]][Q[[qback]]];Q[[qptr]][Q[[qback]]] =.; 
  Q[[qelem]]
)

I refer to his treatment for details on how this works.

Automating caching via metaprogramming

The idea will be to inject certain caching code into a definition of a function. The deque will be used to store the arguments of a last given number of function calls, and remove older cache values when a function is called again, if the cache is full. Here is an implementation:

ClearAll[makeCached];
SetAttributes[ makeCached, HoldAll];
makeCached::incrlim =
  "The cache size is too small. Increase the cache size. Further \
    computation will use an uncached function";

makeCached[SetDelayed[f_[args___], rhs_], limit_Integer] :=
   Module[{qq, faux, queue, cache, myHold, dv},
     dv = DownValues[f];
     SetAttributes[myHold, HoldAll];
     queue = newQueue[qq];
     faux[a : PatternSequence[args]] :=
       With[{result = cache[a]},
          result /; ! MatchQ[result, _cache]
       ];
     faux[a : PatternSequence[args]] /; queueLength[queue] < limit :=
       (
          enQueue[queue, {a}];
          cache[a] = rhs
       );
     faux[a : PatternSequence[args]] :=
       With[{argums = Sequence @@ deQueue[queue]},
          If[Head[cache[argums]] === cache,
            Message[makeCached::incrlim];
            Throw[myHold[f[a]], makeCached],
            (* else *)
            cache[argums] =.;
            faux[a]]
       ];

     f[argums___] :=
       Catch[faux[argums], makeCached] /.
          myHold[code_] :> 
              Block[{f},
                 DownValues[f] = dv;
                 f[args] := rhs;
                 code
              ]
];

What is happening here is that we introduce cache as a storage for cached results, queue and qq to keep the queue of function arguments, and we define f so that it basically uses faux to do the computation. If the cache becomes full in the process of a computation (which may happen for deeply recursive functions), we bail out of the computation via Throw and then use the un-cached definition for f to compute that piece of code (technically, I use Block-trick to accomplish that across the execution stack).

Example

Here will be our function:

ClearAll[ff];
ff[_?Negative, _?Negative] = 0;
makeCached[ff[x_, y_] := 1 + ff[x - 1, y - 1], 1000];

and we also define it's non-cached counter-part:

ClearAll[fff];
fff[_?Negative, _?Negative] = 0;
fff[x_, y_] := 1 + fff[x - 1, y - 1];

Now, the benchmarks:

MapThread[ff,{#,#}&@Range[10000]]//Short//Timing

(* {0.796875,{2,3,4,5,6,<<9990>>,9997,9998,9999,10000,10001}} *)

while for non-cached version:

Block[{$RecursionLimit=Infinity},MapThread[fff,{#,#}&@Range[10000]]]//Short//Timing

(* {107.437500,{2,3,4,5,6,<<9990>>,9997,9998,9999,10000,10001}}  *)

Remarks

The above code should be able to deal with most pattern-based functions. It may have some problems with functions which hold their arguments, or have many definitions that have to be cached. The non-cached definitions (like base definitions for recursion, etc), must be given before makeCached is called.

Another problem which I did not yet deal with here is that the internal variables like faux, cache etc won't be garbage-collected even after we Remove ff. This can be dealt with by introducing an explicit function to release that memory.

Answer 3

For individual cases I believe the most straight forward solution is simply using Unset: For instance:

f[x_] := f[x] = x
f[1];
f[2];
f[5];

DownValues[f]
f[5] =.
f[3];
DownValues[f]

 (* {HoldPattern[f[1]] :> 1, HoldPattern[f[2]] :> 2, HoldPattern[f[5]] :> 5,     
        HoldPattern[f[x_]] :> (f[x] = x)}  *)
 (* {HoldPattern[f[1]] :> 1, HoldPattern[f[2]] :> 2, HoldPattern[f[3]] :> 3, 
        HoldPattern[f[x_]] :> (f[x] = x)} *)

If you want to clear using patterns on the set values, then the other answers dealing with manipulating downvalues will prove more useful. Though you can also clear multiple definitions using code similar to: Table[f[n] =., {n, 1, 2}].