# Tag Info

59

It is a simple way to implement Memoization. The trick is that if you define a function as f[x_]:=f[x]=ExpensiveFunctionOf[x] then when you for the first time call e.g. f[3], it will evaluate as f[3]=ExpensiveFunctionOf[3] which will evalulate the expensive function, and assign the result to f[3] (in addition to giving it back, of course). So if e.g. ...

50

Memoization is perhaps the most common application, but it is not the meaning of that construct. More generally it is a construct for a function that redefines itself. This has many uses beyond memoization. Consider this function: f[y_] := (f[y] = Sequence[]; y) It is used to remove duplicates in a list. When the function is first called with a ...

28

It's ... oh, why not let the docs speak: tutorial/FunctionsThatRememberValuesTheyHaveFound (in Doc center) Edit You may also find additional information by searching for "memoization" on this site. This has always been a great trick to avoid having to re-evaluate the result of a computationally intensive function call. In the above link, it is also used ...

28

Yes, there is, although the speed-up is not as dramatic as for 1D memoization: ClearAll[CharlierC]; CharlierC[0, a_, x_] := 1; CharlierC[1, a_, x_] := x - a; CharlierC[n_Integer, a_, x_] := Module[{al, xl}, Set @@ Hold[CharlierC[n, al_, xl_], Expand[(xl - al - n + 1) CharlierC[n - 1, al, xl] - al (n - 1) CharlierC[n - ...

26

This is my first reply in this group. So please bear with me if I make any mistake, it would not be intentional, just lack of familiarity with the rules. Although the replies above mention important aspects, I generally like to view things from alternative perspectives. I'd like to offer a few of those on this question. Understanding is enhanced by viewing ...

17

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 ...

17

Nice question. This is my suggested implementation. Evaluate all code at once. Clear[CharlierC, "CharlierC*"] CharlierC (* create symbol in current context *) Begin["CharlierC"]; implementation[0] := 1; implementation[1] := x - a; implementation[n_Integer] := implementation[n] = Expand[(x - a - n + 1) implementation[n - 1] - ...

16

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.

15

It also has another practical side. If you have a random function, which you only want to evaluate once, but you don't know where exactly it will be evaluated or you want to declare it before the parameters it depends on are defined, and you want it to be the same after the first evaluation, for any subsequent call, you can use the memoization trick: ...

14

I would also suggest to use pure functions here: CharlierC[0] = 1 &; CharlierC[1] = #2 - #1 &; CharlierC[n_Integer] := (CharlierC[n] = Evaluate[ Expand[(#2 - #1 - n + 1) CharlierC[n - 1][#1, #2] - #1 (n - 1) CharlierC[n - 2][#1, #2]]] &); CharlierC[20][a, x] // AbsoluteTiming (* ==> {0.0312414, a^20 - ...

14

The problem with SetSharedFunction is that it forces f to be evaluated on the main kernel: this means that if you simply do SetSharedFunction[f] then you will lose parallelization (a timing of ParallelTable[f[x], {x, 3}] will give about 9 seconds). This property of SetSharedFunction is not clear from the documentation in my opinion. I learned about it ...

13

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}]]

12

The case at hand Here is one possibility: ClearAll[fibon] Options[fibon] = {k -> 1} fibon[0, OptionsPattern[]] = 0; fibon[1, OptionsPattern[]] = 1; fibon[n_, opts : OptionsPattern[]] /; ! OrderedQ[{opts}] := fibon[n, Sequence @@ Sort[{opts}]]; fibon[n_, opts : OptionsPattern[]] := fibon[n, opts] = fibon[n - 1, opts] + ...

12

You can utilize Dynamic Programming in the following way: CharlierC[0, a_, x_] := 1 CharlierC[1, a_, x_] := x - a CharlierC[n_Integer, a_, x_] := CharlierC[n, a, x] = Expand[Expand[(x - a - n + 1) CharlierC[n - 1, a, x]] - Expand[a (n - 1) CharlieC[n - 2, a, x]]] It basically creates an in-memory store of previous evaluated function values instead of ...

11

Although you can always implement recursion by hand the way you are trying to do, there are also some specialized functions that are designed to make your life a little easier. In particular, there is FoldList. This approach is also slightly faster than the manual recursion approach (assuming you start from a clean slate): endRecursion = 20; beta = ...

11

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: ...

10

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 ...

10

I will offer a rather cryptic solution using nested version of the injector pattern, but it should be possible to also rewrite it using more readable methods, if really needed. Solution Here is the code: ClearAll[t]; t[a_]:= c[a] t[a_,b_]:= d[a,b] t[a__]:= With[{vars=Table[Unique[],{Length[{a}]}]}, With[{pts=(Pattern[#1,_]&)/@vars}, ...

9

You can speed it up by "memoization", i.e., remembering previous values of alpha[i]: endRecursion = 20; beta = Import["beta.txt", "List"]; beta = beta[[1 ;; endRecursion]]; gamma = RandomReal[{0, 2*Pi}, endRecursion]; alpha[0] := 0; alpha[i_] := alpha[i] = ArcCos[Cos[alpha[i - 1]]*Cos[beta[[i]]] + Sin[alpha[i - ...

8

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, ...

8

For such small trees I would memoize those that already have the element... ClearAll[leftsubtree, rightsubtree, nodevalue, emptyTree, treeInsert] leftsubtree[{left_, _, _}] := left rightsubtree[{_, _, right_}] := right nodevalue[{_, val_, _}] := val emptyTree = {}; treeInsert[emptyTree, elem_] := {emptyTree, elem, emptyTree} (*This is the changed line*) t ...

7

Well, the simplest approach I came up with is to just memoize the result after you generate it. ClearAll[leftSubTree, rightSubTree, nodeValue, emptyTree, treeInsert]; leftSubTree[{left_, _, _}] := left; rightSubTree[{_, _, right_}] := right; nodeValue[{_, val_, _}] := val; emptyTree = {}; treeInsert[emptyTree, elem_] := {emptyTree, elem, emptyTree}; ...

7

In many cases, memoization helps for a given particular computation, and one can (or even has to) then remove the memoized values. For such cases, protection can nicely coexist with the technique which I call "self-blocking". I will illustrate this using the infamous Fibonacci numbers example: Unprotect[fib]; ClearAll[fib]; fib[n_] := Block[{fib}, ...

7

Without memoization but works too :) Block[{i}, (i = 1; # /. a :> i++)] & /@ {{a, b}, {a, b, c}, {a, b, a, a}, {b, c}} And with: ClearAll[f]; f[a, _Integer] = 0; f[a, {p_, _}] := f[a, p] += 1; f[x_, _] := x; MapIndexed[f, {{a, b}, {a, b, c}, {a, b, a, a}, {b, c}}, {2} ] {{1, b}, {1, b, c}, {1, b, 2, 3}, {b, c}}

6

You could just unprotect and protect on the first call of the recursion. To avoid checking in every inner call if it's the first or not, you could implement it in a an extra private symbol, and use the public interface as a non-recursive wrapper. Unprotect[fac]; ClearAll[fac]; Module[{facPvt}, facPvt[1] = 1; facPvt[n_Integer] := facPvt[n] = n facPvt[n - ...

6

Here is a crude way using FoldList. foo[lis_, var_] := Module[{i, f}, f[var] := ++i; f[x_List] := f /@ x; f[x_] := x; Rest @ FoldList[(i = 0; f[#2]) &, var, lis] ] Use: foo[list, a] {{1, b}, {1, b, c}, {1, b, 2, 3}, {b, c}}

6

Q[n_, L_] := Q[n, L] = Integrate[Q[n - 1, L] /. L :> L - a - z, {z, 0, L - (n - 1) a}] Q[2, L_] = 1/2 (a - L)^2 Q[4, L] (* 1/24 (-3 a + L)^4 *)

6

Not much different from your approach and maybe not the best/safest approach, but DumpSave helps a bit because at least you don't have to works with strings: cacheFile = FileNameJoin[{$TemporaryDirectory, "fibonacciCache" <> ".mx"}]; If[FileExistsQ[cacheFile], Get[cacheFile], fibonacci[1] = 1; fibonacci[2] = 1; fibonacci[n_Integer] := Module[{}, ... 5 The function runs slowly because each iteration calls alpha twice the number of times of the previous iteration. Thus,$n$iterations invoke alpha$2^n\$ times -- exponential run time! Fortunately, the two nested calls to alpha are identical. If we change alpha to call itself only once instead of twice, the algorithm runs in linear time while still ...

Only top voted, non community-wiki answers of a minimum length are eligible