# Tag Info

72

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

63

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

54

General The conceptual problem with memoized pure functions is that pure functions typically (in fact, normally by their mere definition) do not cause side effects, while memoization necessarily requires side effects (changes of state). What was meant was probably to construct a memoized anonymous (lambda) - functions - this is possible, because the latter ...

36

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

31

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

29

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

25

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

23

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

22

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

19

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

16

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

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

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] + OptionValue[k]*fibon[...

14

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

14

Suggested solution If I understood the question right, then the simplest solution here would probably be to define a helper function like the following: vv[n_] := Internal`InheritedBlock[{v}, v /@ Range[n]]; Then, you get vel = vv[m] and every run of vv would result in different set of values, while the values in the set will all come from the same ...

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

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

12

f[x_] := x^2 DownValues[h] = DownValues[f] /. f -> h; f[x_] := f[x] = h[x] h is now equal to the original f, and f is a memoized version of it. Some kinds of definitions would require a more specific replacement rule than /. f -> h, for example recursive functions.

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 = Import["...

11

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

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

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

10

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

10

I wrote the code in question... It is pretty much a line for line port of the Julia version of the benchmark: Julia: fib(n) = n < 2 ? n : fib(n-1) + fib(n-2) Mathematica: fib = Compile[{{n, _Integer}}, If[n < 2, n, fib[n - 1] + fib[n - 2]], CompilationTarget -> "WVM" (* WVM is faster than C in this case because of the recursive ...

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 - 1]]*Sin[beta[[i]]]*Cos[gamma[[i]]]...

9

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[{}, ...

8

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

8

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

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