Questions tagged [memoization]

For questions related to user defined caching mechanisms, memoization, in particular.

Filter by
Sorted by
Tagged with
85
votes
5answers
10k views

What does the construct f[x_] := f[x] = … mean?

This question mentions "x := x = trickery". What does defining a function as f[x_] := f[x] = ... do and what is it good for?
52
votes
4answers
4k views

How can I implement dynamic programming for a function with more than one argument?

Dynamic programming is a technique for avoiding the repeated computation of the same values in a recursive program. Each value computed is immediately stored. If the value is needed again, it is not ...
45
votes
2answers
3k views

Memoization with pure functions?

Is this possible? If I have a simple function, say: f=If[#>0,1,2]& then for each value of # this will re-evaluate f right? Is it possible to define a ...
43
votes
4answers
1k views

Parallelize evaluation of function with memoization

I have a complicated function that I need multiple times, so I want to memoize it and have the first evaluation done in parallel. Unlike in my example below it's not a continuous function, so ...
34
votes
3answers
2k views

How to clear parts of a memoized function?

I have a function of two variables, e.g.: f[a_, b_] := f[a, b] = something f[a - 1, b - 1] etc With the above code I used the concept of memoization to speed up ...
25
votes
4answers
1k views

Throwaway memoization makes built-ins faster?

Yesterday I got into an argument with @UnchartedWorks over in the comment thread here. At first glance, he posted a duplicate of Marius' answer, but with some unnecessary memoization: ...
19
votes
3answers
738 views

How to memoize a function with Options?

Consider the following modified fibonacci function: ...
16
votes
1answer
271 views

When to use Once for memoization?

While watching Stephen Wolfram's twitch stream I saw him use Once for memoization, which surprised me since I thought of Once as ...
15
votes
1answer
1k views

Relative performance of the Julia language

I was just reviewing the Mathematica benchmark code linked from the Julia language home page http://julialang.org/. The stated goal of the benchmarks is to test the performance of specific algorithms, ...
14
votes
3answers
600 views

Using Memoization with a Mutable Object

In looking for a solution to this question, I ran across some old binary tree code by Daniel Lichtblau, reproduced below: ...
13
votes
1answer
223 views

How to write crash-robust code?

When a notebook crashes all the work I was doing is lost - I'd like to ameliorate this situation! Is there a way to decorate a symbol so that it is saved to disk whenever it changes, or after a ...
12
votes
3answers
407 views

Memoization of Rounded inputs

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 ...
11
votes
3answers
8k views

Get polynomial interpolation formula

I'm attempting to get a polynomial interpolation formula out of Mathematica but I am absolutely lost. I stared out using ...
11
votes
2answers
1k views

Dynamic Programming with delayed evaluation

By using dynamical programming, we can save intermediate steps for recursive relations, as in f[n_]:= f[n] = f[n-1] + f[n-2] However, this only stores ...
10
votes
1answer
176 views

How to speed up the evaluation of a function with a large LeafCount but many repeated sub-functions for use in NIntegrate

General Context Apparently, the memory leak in NIntegrate is unavoidable pre-MMA-10.2. I have some (two-dimensional) numerical integration to do on a complicated ...
9
votes
3answers
2k views

Improve speed for calculating a recursive sequence

I want to calculate following recursive sequence: $\alpha_{0}=0,\\ \cos(\alpha_{i})=\cos(\alpha_{i-1})\cdot\cos(\beta_{i})+\sin(\alpha_{i-1})\cdot\sin(\beta_{i})\cdot\cos(\gamma_{i}).$ In ...
9
votes
1answer
671 views

Can I memoize retroactively?

I have a function defined something like this: f[x_] := Module[...]; I can easily write a memoized version of it like this: ...
9
votes
1answer
224 views

Saving memoization to disk

I like using memoization (i.e. the construct myFunction[x_]:=myFunction[x]=...) when I have a heavy function that I need to re-evaluate on the same arguments. ...
9
votes
2answers
259 views

using memoization with conditional statement

I would like some advice about the use of memoization in conjunction with conditional statements. Let me try to explain my problem: I am constructing a function depending on a number of parameters. ...
8
votes
1answer
102 views

Memoization and packages

I am working in a package on symmetric functions, that sometimes are quite expensive to compute. I use memoization extensively, but what is the correct approach for a package intended for the public ...
7
votes
2answers
313 views

Correct way to use memoization for recurrence relation having an Integral

I am trying to construct a way to make a function for the following recurrence relation. $$ Q(N,L) = \int_{0}^{L-(N-1)a} Q(N-1, L-a-z) dz $$, with the initial condition $Q(2,L) = \frac{1}{2} (a-L)...
7
votes
1answer
247 views

Garbage collection for memoized functions on subkernels

I have a top-level function which operates on some data: findBestIntegers[data_]:=ParallelMap[optimize,data] which makes parallelized calls to an optimization ...
7
votes
0answers
94 views

Time complexity to choose the right overload from the memoized function

If we want to save some outputs of the function, we often use the memoization pattern as follows, f[x_]:=f[x]=x f/@Range[10^5] If I call this function many times ...
6
votes
2answers
1k views

How does one clear the memory of a recursive function

I want to implement the recursive function v[n_] := v[n] = v[n-1] + f[n-1] + Random[NormalDistribution[0,s]] to get ...
6
votes
2answers
143 views

Combining memoization and SlotSequence

I found myself writing memoizing code like this: ...
6
votes
1answer
115 views

Clever caching of a recursively defined function

I've got a function of the form f[n,s] where n is a natural number and s is a finite ...
6
votes
0answers
526 views

Increasing recursion speed in Hull-White trinomial tree calculation

First timer here and have been finding these boards very useful in learning Mathematica. I'm trying to implement a numerical procedure for the Hull-White trinomial tree in Mathematica. Despite using ...
5
votes
2answers
239 views

Only perform a symbolic differentiation once

I want to define a function that involves a differentiation step that Mathematica can do easily, which might be of the form ...
5
votes
0answers
302 views

Change of basis of polynomials

Suppose I have a favourite basis for polynomials in $x_1,\dotsc,x_n$, say non-symmetric Macdonald polynomials to be specific. I can easily compute these, and thus the change-of-basis matrix that takes ...
5
votes
0answers
211 views

Dropbox datastore

Dropbox seems to have a feature where it can be used as a database. This would be really cool to use for memoized functions, that can be restored on several computers and sessions. I have a function ...
4
votes
4answers
460 views

Memoization of a function defined by a recurrence relation [duplicate]

I have a function which is defined by the following recurrence relation $$h_{n}(x)=h_{n-1}(x)+\frac{\mathrm{e}^{-x^2}}{2^n n!}H_{n}(x)H_{n-1}(x)$$ with the initial condition $h_{0}(x)=0$ and where the ...
4
votes
3answers
342 views

have a function redefine itself as it maps through a list

I have a list which contains sublists, e.g. list = {{a,b}, {a,b,c}, {a,b,a,a}, {b,c}, ...} I then map a function through each sublist. This function should ...
4
votes
2answers
254 views

Is it possible to `Protect` a dynamic programming process?

I wrote a function using dynamic programming to speed up the evaluation. For safety, I also want to protect this function. Take factorial for example: ...
4
votes
4answers
444 views

How to do memoization together with evaluation of a complicated function

UPDATE 2: much shorter version Given a list of paired indices {i, j}={{1,2}, {3,4}, …}, I need to first evaluate a rather complicated function test[i,j,x] (because ...
4
votes
2answers
138 views

Assigning function values in a memoized recursive module

I have a complicated recursive module which I have memoized. I realised that certain isomorphs of inputs to this function will give the same output. Therefore I decided to memoize all such input-...
4
votes
1answer
138 views

How can I access memoized values from parallel evaluation? [duplicate]

I want to evaluate a table of functions with ParallelTable. Here is the serial code: ...
3
votes
1answer
173 views

Kernel crashed after $RecursionLimit = Infinity

$RecursionLimit = Infinity; T[n_, k_]:= T[n, k] = If[n == 0 || k == 1, 1, T[n, k-1] + If[n<k, 0, T[n-k, k]]]; Table[T[n!, n], {n, 1, 9}] Without ...
3
votes
2answers
419 views

Problems with DumpSave and memoization

I defined a function that takes some time to compute using memoization: y[a_, b_, c_] := y[a, b, c] = First[$y /. NDSolve[.........] so that if I call y[a,b,c] ...
3
votes
0answers
120 views

Memoization of built in function

What is the best way to let mathematica memoize built-in function like e.g. SphericalHarmonicY[l,m,th,ph] One possibility would be for sure: ...
3
votes
0answers
63 views

Memoized function with function parameter [duplicate]

I have some code that takes a function and uses the function to do some complicated computation. Thus, I wish to store this so I don't have to repeat this. Below, it is more simple than my real ...
3
votes
0answers
72 views

Parallelization and memoization? [duplicate]

I have an expensive function on discrete values, f[n_] := f[n] = n^2 (* Expensive calculation *) Since f[n] is an expensive ...
2
votes
3answers
155 views

Extract memoized results in the form of a rule

Lets say I define a function f with memoization. Is there some way to extract the memoized values? For example, ...
2
votes
1answer
275 views

tricky memoization

Let's say I have the NDSolve example for documentation involving splitting 2nd order into set of 1st order ODEs: ...
2
votes
1answer
62 views

Timing of three different strategies for fibonacci numbers

A standard way to speed up the creation of Fibonacci numbers is by memoization Instead of: fib1[0] = 0; fib1[1] = 1; fib1[n_] := fib1[n - 1] + fib1[n - 2]; One ...
2
votes
2answers
103 views

Memoization and finding already calculated DownValue

The problem of plotting an expensive function discussed in this question caught my attention. As an exercies I tried to solve it using memoization as follows ...
2
votes
1answer
132 views

Memoization only under certain conditions

I have a function that takes in sequences of values (as a list), and recursively removes the largest element from that sequence as part of its computation. Some of these sequences can be quite large, ...
2
votes
1answer
76 views

a recursive function using memoization

I have looked at a lot of these cases, e.g. Can one identify the design patterns of Mathematica? and the included ones. My trimmed example, here establishing the 'initial conditions' (where the ...
2
votes
1answer
100 views

Debugging and decision support tools for Dynamic Programming (cached definitions) in Mathematica

I'm using the Quantum Computing library with this example: ...
2
votes
0answers
1k views

SystemException[MemoryAllocationFailure] with Memoized function [closed]

Version 10.1 Win7x64 Enterprise. This is more of a report than a question but others may have seen the same / have insights. I have some code (that I can't really post as it's too big) with a large ...
2
votes
0answers
87 views

SetDelayed and avoiding function calls through memoization [duplicate]

I am fairly new to Mathematica. I am working my way through a number of books. I have been looking at the use of SetDelayed and want to confirm that my ...