{"id":19,"date":"2006-02-08T12:19:49","date_gmt":"2006-02-08T17:19:49","guid":{"rendered":"https:\/\/blogs.mathworks.com\/loren\/?p=19"},"modified":"2016-07-28T14:09:56","modified_gmt":"2016-07-28T19:09:56","slug":"use-nested-functions-to-memoize-costly-functions","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/loren\/2006\/02\/08\/use-nested-functions-to-memoize-costly-functions\/","title":{"rendered":"Use nested functions to memoize costly functions"},"content":{"rendered":"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\r\nnested functions. Consider this function:\r\n
function f = memoize1(F)\r\n%one-arg F, inputs testable with ==\r\n\r\nx = [];\r\ny = [];\r\nf = @inner;\r\n    function out = inner(in)\r\n        ind = find(in == x);\r\n        if isempty(ind)\r\n            out = F(in);\r\n            x(end+1) = in;\r\n            y(end+1) = out;\r\n        else\r\n            out = y(ind);\r\n        end\r\n    end\r\nend<\/pre>\r\nLet'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.\r\n
\r\n>> f = memoize1(@sin)\r\nf =\r\n@memoize1\/inner\r\n>> x = f(3)\r\nx =\r\n0.1411\r\n>> y = f(7)\r\ny =\r\n0.6570\r\n>> z = f(3)\r\nz =\r\n0.1411\r\n>> f(.2)\r\nans =\r\n0.1987\r\n>> f(pi\/8)\r\nans =\r\n0.3827\r\n<\/pre>\r\nNow let's look into what's happening with our function f<\/kbd> using the functions<\/kbd><\/a> function.  This should be used primarily for debugging and gaining insight, not as a programmatic tool.\r\n\r\n
Get information about the function handle:<\/p>\r\n
\r\n>> s = functions(f)\r\ns =\r\nfunction: 'memoize1\/inner'\r\ntype: 'nested'\r\nfile: 'H:DocumentsLORENv7memoize1.m'\r\nworkspace: {[1x1 struct]}\r\n<\/pre>\r\n
Get info about the nested function including its workspace:<\/p>\r\n
\r\n>> s.workspace{1}\r\nans =\r\n\r\nf: @memoize1\/inner\r\nF: @sin\r\nx: [3 7 0.2000 0.3927]\r\ny: [0.1411 0.6570  0.1987 0.3827]\r\n<\/pre>\r\nSo, if we were to put a breakpoint at inner<\/kbd> and issued the command f(3)<\/kbd> from the prompt, we'd be able to follow the logic about indexing into the saved values rather than doing the calculation again.\r\n\r\nIn 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<\/em> need to save anything in addition to the handle, since the associated workspace would be also be saved.\r\n\r\nmemoize1<\/kbd> can clearly be improved by vectorizing it (probably using ismember<\/kbd><\/a>).   Here is the latest version of this variant of the code:\r\n<\/p> \r\n
\r\nfunction f = memoize2(F)\r\n%one-arg F, inputs testable with ==\r\n%allow nonscalar input.\r\n\r\nx = [];\r\ny = [];\r\nf = @inner;\r\n    function out = inner(in)\r\n        out = zeros(size(in));  % preallocate output\r\n        [tf,loc] = ismember(in,x);  % find which in's already computed in x\r\n        ft = ~tf;  % ones to be computed\r\n        out(ft) = F(in(ft));  % get output values for ones not already in\r\n        % place new values in storage\r\n        x = [x in(ft(:).')];\r\n        y = [y reshape(out(ft),1,[])];\r\n        out(tf) = y(loc(tf));  % fill in the rest of the output values\r\n    end\r\nend\r\n<\/pre>\r\n
\r\nVariants 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.\r\n<\/p>","protected":false},"excerpt":{"rendered":"
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... read more >><\/a><\/p>","protected":false},"author":39,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[10,3,7,6],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/19"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/users\/39"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/comments?post=19"}],"version-history":[{"count":1,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/19\/revisions"}],"predecessor-version":[{"id":1789,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/19\/revisions\/1789"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/media?parent=19"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/categories?post=19"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/tags?post=19"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}