Tag Info

Hot answers tagged

56

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


49

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


26

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


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


15

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


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

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


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


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


11

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


10

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


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


9

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


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

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

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


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 *)


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


5

When I see this right, you have one single function call (NDSolve) depending on two parameters which results in a vector (the interp. functions). Here is an equivalent minimal example function for this call f[a_, b_] := {b, a} The underlying issue is now, that you always get both answers from f (x and y) even if you need only x for a specific choice of a ...



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