Re: Limiting mma caching (??)
- Subject: [mg2641] Re: Limiting mma caching (??)
- From: wagner at bullwinkle.cs.Colorado.EDU (Dave Wagner)
- Date: Thu, 30 Nov 1995 21:02:29 -0500
- Approved: usenet@wri.com
- Distribution: local
- Newsgroups: wri.mathgroup
- Organization: Wolfram Research, Inc.
In article <49dplb$8a6 at dragonfly.wri.com>,
Mark Van de Vyver <mvyver at ecel.uwa.edu.au> wrote:
>Hi,
>
>I've the following query / suggestion.
>
>Is it possible to limit the amount of caching that mma does?
>
>For example:
>
>factorial[0] = 1;
>factorial[n] = n * factorial[n-1];
>
>With factorial[5], there are five numbers held in memory.
>
>In larger recursions this chews up memory quite fast.
>A useful feature would be to be able to limit mma to holding the last 'x'
>numbers in memory.
>Is it possible to implement such a feature, or would it have to be built in
>by Wolfram?
Well, I feel a duty to answer this question, seeing as how I wrote an
article about using this technique. Funny thing is, I was thinking about
this exact problem last night!
What you'd want to do is set up a definition like the following:
(Local) In[55]:=
Clear[factorial]
factorial[0] = 1;
factorial[n_] :=
(
factorial[n] = n * factorial[n-1];
If[n>1, Unset[factorial[#]]&[n-1]];
factorial[n]
)
The basic idea here is that after you compute factorial[n], you don't
need factorial[n-1] any longer, so you get rid of it. The mechanics
of doing this are somewhat subtle. Since Unset holds its argument, you
can't simply call "Unset[factorial[n-1]]". You have to get an actual
numeric value inside the factorial inside the Unset. I've done this
using a pure function trick; there are other tricks involving Hold and
rule substitution that would do the same thing, although not as elegantly.
The If is necessary so that the base case doesn't get removed! If you
wanted to save, say, the last 10 values, you could do something like
"If[n > 11, Unset[factorial[#]]&[n-10]]". Of course, all of this extra
calculation slows things down.
Observe what happens:
(Local) In[58]:=
factorial[10]
(Local) Out[58]=
3628800
(Local) In[59]:=
?factorial
Global`factorial
factorial[0] = 1
factorial[10] = 3628800
factorial[n_] :=
(factorial[n] = n*factorial[n - 1];
If[n > 1, ((factorial[#1] =. ) & )[n - 1]];
factorial[n])
If you call factorial with a larger argument, the recursion will
"bottom out" at the cached value of factorial[10], which will then
be removed:
(Local) In[60]:=
factorial[20]
(Local) Out[60]=
2432902008176640000
(Local) In[61]:=
?factorial
Global`factorial
factorial[0] = 1
factorial[20] = 2432902008176640000
factorial[n_] :=
(factorial[n] = n*factorial[n - 1];
If[n > 1, ((factorial[#1] =. ) & )[n - 1]];
factorial[n])
On the other hand, if you evaluate factorial of a smaller number, then
the previous cached value isn't removed. Hopefully this isn't a problem.
(Local) In[62]:=
factorial[5]
(Local) Out[62]=
120
(Local) In[63]:=
?factorial
Global`factorial
factorial[0] = 1
factorial[5] = 120
factorial[20] = 2432902008176640000
factorial[n_] :=
(factorial[n] = n*factorial[n - 1];
If[n > 1, ((factorial[#1] =. ) & )[n - 1]];
factorial[n])
Things get slightly trickier with a more complicated example, such
as the fibonacci function.
(Local) In[64]:=
Clear[fib]
fib[0] = fib[1] = 1;
fib[n_] :=
(
fib[n] = fib[n-1] + fib[n-2];
If[n > 3, Unset[fib[#]]&[n-2]];
fib[n]
)
Here, I've saved the last two cached values by Unset'ing fib[n-2].
This is fairly subtle: the recursive call to fib[n-1] computes fib[n-2]
and Unsets fib[n-3]; then the recursive call to fib[n-2] doesn't require
any recursion because fib[n-2] is still cached. (I had to think about
this about 5 times before I could convince myself it was right!)
Here's proof:
(Local) In[92]:=
Trace[fib[8], fib[__]]
(Local) Out[92]=
{fib[8], {{{fib[7], {{{fib[6],
{{{fib[5], {{{fib[4], {{{fib[3],
{{{fib[2], {{{fib[1]}, {fib[0]}}},
{fib[2]}}, {fib[1]}}}, {fib[3]}},
{fib[2]}}}, {fib[4]}}, {fib[3]}}},
{fib[5]}}, {fib[4]}}}, {fib[6]}}, {fib[5]}}
}, {fib[7]}}, {fib[6]}}}, {fib[8]}}
(Local) In[93]:=
?fib
Global`fib
fib[0] = 1
fib[1] = 1
fib[7] = 21
fib[8] = 34
fib[n_] :=
(fib[n] = fib[n - 1] + fib[n - 2];
If[n > 3, ((fib[#1] =. ) & )[n - 2]]; fib[n])
Dave Wagner
Principia Consulting
(303) 786-8371
dbwagner at princon.com
http://www.princon.com/princon