Main Content

memoize

Add memoization semantics to function handle

Description

Memoization is an optimization technique used to speed up programs by caching the results of expensive function calls and returning the cached result when the program is called with the same inputs.

Consider memoizing a function call if all of the following are true:

  • Performance is important.

  • The function is time consuming.

  • The function has return values that are determined entirely by the input values, and has no side effects.

  • System memory is adequate to store unique input and output combinations.

example

memoizedFcn = memoize(fh) adds memoization semantics to the input function handle, and returns a MemoizedFunction object. Invoke memoizedFcn as you would invoke fh. However, memoizedFcn is not a function handle.

The MemoizedFunction object maintains the cache of inputs and the corresponding outputs. When it is invoked, MATLAB® returns the associated cached output values if the following conditions are true.

  1. The input arguments are numerically equal to cached inputs. When comparing input values, MATLAB treats NaNs as equal.

  2. The number of requested output arguments matches the number of cached outputs associated with the inputs.

The memoization of a function is associated with the input function and not with the MemoizedFunction object. Therefore, keep the following in mind.

  • Constructing a new MemoizedFunction object to the same function creates another reference to the same data. Two variables that memoize the same function share a cache and object property values, such as cache size. In the following example, the variables a and b share a cache and have the same value for cache size.

    a = memoize(@svd);
    b = memoize(@svd);
    Similarly, clearing the cache for b (b.clearCache) also clears the cache for a, and any other variables that memoize the svd function. clearCache is a MemoizedFunction object function.

  • Assigning a MemoizedFunction object to a new variable creates another reference to the same data. In the following example, the variables c and d share data.

    c = memoize(@svd);
    d = c;

  • Clearing a variable does not clear the cache associated with the input function. To clear the cache for a MemoizedFunction object that no longer exists in the workspace, create a new MemoizedFunction object to the same function, and use the clearCache function on the new object. Alternatively, you can clear caches for all MemoizedFunction objects using the clearAllMemoizedCaches function.

Caution

A MemoizedFunction object is not aware of updates to the underlying function. If you modify the function associated with the memoized function, clear the cache with the clearCache object function.

Examples

collapse all

To speed up performing a singular value decomposition when you could be operating on the same inputs multiple times, memoize the svd function.

fh = @svd;
memoizedFcn = memoize(fh);

Create a matrix and cache the results of the singular value decomposition. Time the function call.

X = magic(1234);
tic
[U,S,V]= memoizedFcn(X);
preCachedTime = toc
preCachedTime = 0.4655

Call the memoized function again using the same inputs. To observe the speed improvement using cached results, time the function call again.

tic
[U,S,V]= memoizedFcn(X);
postCachedTime = toc
postCachedTime = 0.0038

In your current working folder, create a file computeNumberCombinations.m that contains the following function to compute the number of combinations of n items taken k at a time.

type computeNumberCombinations.m
function c = computeNumberCombinations(n,k)
% Calculate number of combinations of n items taken k at a time
c = fact(n)/(fact(n-k)*fact(k));
end

function f = fact(n)
f = 1;
for m = 2:n
    f = f*m;   
end
end

Clear the cache for any MemoizedFunction objects in your workspace.

clearAllMemoizedCaches

Memoize the computeNumberCombinations function to speed up computation for repeated input values.

fh = @computeNumberCombinations;
memoizedFcn = memoize(fh);

Call the memoized function and time the function call. This function call caches the results for the specified inputs.

tic
c = memoizedFcn(42e5,137);
preCachedTime = toc
preCachedTime = 0.0212

Call the memoized function and time the function call again. This function call uses the cached results and does not execute the function.

tic
c = memoizedFcn(42e5,137);
postCachedTime = toc
postCachedTime = 0.0035

Input Arguments

collapse all

Function to memoize, specified as a function handle.

Example: memoizedEigs = memoize(@eigs)

Data Types: function_handle

Tips

  • Multiple calls to memoize with the same function handle return the same MemoizedFunction object. For example:

    x = memoize(@plus);
    y = memoize(@plus);
    x == y
    ans =
    
      logical
    
       1
  • You should not memoize a function with side effects such as setting some global state or performing I/O operations. Side effects are not repeated on subsequent calls to the memoized function with the same inputs. For example, if you memoize the randi function, the memoized function always returns the same value when called with the same input argument.

    fh = @randi;
    memoized_fh = memoize(fh);
    
    fh_result = [fh(100) fh(100) fh(100)]
    memoized_result = [memoized_fh(100) memoized_fh(100) memoized_fh(100)]
    fh_result =
    
        18    71     4
    
    
    memoized_result =
    
        28    28    28

Version History

Introduced in R2017a