13
$\begingroup$

Memoization is a technique for improving performance by having a function remember its previous arguments. For example,

f[x_]:=f[x]=mySlowFunction[x]

will be slow on its first evaluation for a given x, but will be vastly faster on subsequent calls for that x, whereas repeated calls to mySlowFunction[x] will always be slow.

My case is that I would like to discretize the parameter space to increase performance at the expense of accuracy. Any Real value of x should be evaluated only at the rounded value, which itself should be memoized. Compare these toy examples:

Clear[f];
f[x_] := f[x] = Total[Table[x, {100000}]]

Clear[g];
g[x_Real] := g[Round[x]];
g[x_Integer] := g[x] = Total[Table[x, {100000}]]

Timing[f[0]][[1]]
  (* 0.002007 *)

Timing[f[0.1]][[1]]
  (* 0.001523 *)

Timing[g[0]][[1]]
  (* 0.002059 *)

Timing[g[0.1]][[1]]
  (* 0.000013 *)

The 2nd call to g[x] is much faster than the first call, even though the actual input (0.1) has not been memoized itself. The second call is less accurate, and I can live with that.

But I would like to Round[] to arbitrary precision. For example, I could try

g[x_Real] := g[Round[x,0.01]];

The g[x_Integer] pattern of the 2nd definition would fail in this case. I tried the naive

h[x_Real] := h[Round[x,0.01]] = Total[Table[x, {100000}]]

which does not produce the desired effect.

How could one memoize a function's inputs, such that subsequent calls to the function at values near the (rounded) memoized inputs are replaced by calls at those memoized inputs?

For the curious, I am tracing particles under the influence of a force. That force can be calculated to high precision at arbitrary locations, but this is slow. I'd like to cache the force at discrete locations, so that particles within some distance of a previously-calculated value use the cached value.

Improve this question
$\endgroup$
7
  • $\begingroup$ So this is multidimensional, i.e. you have f[x,y,z] and not just f[x], right? For the 1D case I had some easy ideas for good precision (interpolation), but the multidimensional one is more complex. $\endgroup$
    – Szabolcs
    Jan 31, 2012 at 23:27
  • $\begingroup$ It's a 2D case, but I'm interested in the 1D as well. Might be able to extend it. $\endgroup$
    – JxB
    Jan 31, 2012 at 23:29
  • 1
    $\begingroup$ BTW you can always use a pattern like f[x_ /; Round[x, prec] == x] := f[x] = slowf[x]; f[x_] := f[Round[x, prec]]. The variable prec gives you the precision. $\endgroup$
    – Szabolcs
    Jan 31, 2012 at 23:30
  • 1
    $\begingroup$ I'd go for the Interpolation[] approach $\endgroup$
    – acl
    Jan 31, 2012 at 23:58
  • 1
    $\begingroup$ Memoization is a type of caching, so I removed the tag in favor of the more general one. $\endgroup$
    – rcollyer
    Feb 1, 2012 at 2:06

3 Answers 3

Reset to default
15
$\begingroup$

Since Dan's already taken my initial solution, here's another approach that additionally allows you to specify the precision:

f[x_, tol_] := f[Round[x, tol]]
f[x_] := f[x] = Total[Table[x, {100000}]]
Improve this answer
$\endgroup$
1
  • $\begingroup$ Interesting variation of what I just posted (before seeing this). +1 $\endgroup$
    – Mr.Wizard
    Feb 1, 2012 at 0:05
16
$\begingroup$

This variant should do what you want.

g[x_Real] := h[Round[x,0.01]];
h[x_] := h[x] = Total[Table[x, {100000}]]

Your Interpolation idea might give better accuracy though, if the function inquestion is sufficiently well behaved on your grid.

Improve this answer
$\endgroup$
10
$\begingroup$

You can introduce a second symbol as Daniel shows, but I am stingy with symbols and prefer this:

g[x_?NumericQ] := g[{Round[x, 0.01]}];
m : g[{x_}] := m = Total[Table[x, {100000}]]

You could use any head for this, even a string:

g[x_?NumericQ] := g[ "rounded"[ Round[x, 0.01] ] ];
m : g["rounded"[x_]] := m = Total[Table[x, {100000}]]

Delving into the realm of overkill, you could even use Option syntax:

Options[g] = {Rounded -> False};
g[x_?NumericQ] := g[Round[x, 0.01], Rounded -> True];
m : g[x_, OptionsPattern[]] :=
  (m = Total[Table[x, {100000}]]) /; OptionValue[Rounded]
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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