Loren on the Art of MATLAB

Turn ideas into MATLAB

Use nested functions to memoize costly functions

Some languages provide ways to store results of costly calculations so if the calculation had been performed before, it need not be repeated when requested later. There is a way to accomplish this in MATLAB as well, using nested functions. Consider this function:
function f = memoize1(F)
%one-arg F, inputs testable with ==

x = [];
y = [];
f = @inner;
    function out = inner(in)
        ind = find(in == x);
        if isempty(ind)
            out = F(in);
            x(end+1) = in;
            y(end+1) = out;
        else
            out = y(ind);
        end
    end
end
Let's see what happens when we use this function, admittedly with not such an expensive function to calculate. Also, you could substitute any other function handle here, including one referring to an anonymous function, provided it has one input and one output.
>> f = memoize1(@sin)
f =
@memoize1/inner
>> x = f(3)
x =
0.1411
>> y = f(7)
y =
0.6570
>> z = f(3)
z =
0.1411
>> f(.2)
ans =
0.1987
>> f(pi/8)
ans =
0.3827
Now let's look into what's happening with our function f using the functions function. This should be used primarily for debugging and gaining insight, not as a programmatic tool.

Get information about the function handle:

>> s = functions(f)
s =
function: 'memoize1/inner'
type: 'nested'
file: 'H:DocumentsLORENv7memoize1.m'
workspace: {[1x1 struct]}

Get info about the nested function including its workspace:

>> s.workspace{1}
ans =

f: @memoize1/inner
F: @sin
x: [3 7 0.2000 0.3927]
y: [0.1411 0.6570  0.1987 0.3827]
So, if we were to put a breakpoint at inner and issued the command f(3) from the prompt, we'd be able to follow the logic about indexing into the saved values rather than doing the calculation again. In addition, if we wanted to quit MATLAB and come back at a later time, we could save our function handle in a MAT-file and reload it later. We would not need to save anything in addition to the handle, since the associated workspace would be also be saved. memoize1 can clearly be improved by vectorizing it (probably using ismember). Here is the latest version of this variant of the code:

function f = memoize2(F)
%one-arg F, inputs testable with ==
%allow nonscalar input.

x = [];
y = [];
f = @inner;
    function out = inner(in)
        out = zeros(size(in));  % preallocate output
        [tf,loc] = ismember(in,x);  % find which in's already computed in x
        ft = ~tf;  % ones to be computed
        out(ft) = F(in(ft));  % get output values for ones not already in
        % place new values in storage
        x = [x in(ft(:).')];
        y = [y reshape(out(ft),1,[])];
        out(tf) = y(loc(tf));  % fill in the rest of the output values
    end
end

Variants of this memoize code pattern might be useful for functions that have recurrence relationships, recursive functions, or refining underlying meshes. It's possible that you would want to have a buffer limit so the size of the stored data in the nested function didn't grow beyond some bound. But you get the idea.

|

Comments

To leave a comment, please click here to sign in to your MathWorks Account or create a new one.