Logo

Programming-Idioms

  • Go
  • Python

Idiom #315 Memoization

Given any function f, create an object or function m that stores the results of f, and calls f only on inputs for which the result is not stored yet.

import functools
@functools.lru_cache
def m(*args):
    return f(*args)

Function f may have multiple parameters which must be hashable.
func memoize[T comparable, U any](f func(T) U) func(T) U {
	memory := make(map[T]U)

	return func(t T) U {
		if u, seen := memory[t]; seen {
			return u
		}
		u := f(t)
		memory[t] = u
		return u
	}
}

memoize is generic but requires that f accepts a single argument of type T and returns a single result of type U.
fgl
type
  TCache = specialize TFPGMap<TKey, TData>;

var
  Cache: TCache;

...
function m(Key: TKey): TData;
begin
  if not Assigned(Cache) then
    Cache := TCache.Create;
  if not Cache.TryGetData(Key, Result) then
  begin
    Result := f(Key);
    Cache.Add(Key, Result);
  end;
end;

TKey and TData can be of any kind (as long as they are not a class).

The variable Cache should be freed upon exiting the program.
New implementation...
< > ⌨
programming-idioms.org 
@functools.lru_cache
def m(*args):
    return f(*args)


func memoize[T comparable, U any](f func(T) U) func(T) U {
	memory := make(map[T]U)

	return func(t T) U {
		if u, seen := memory[t]; seen {
			return u
		}
		u := f(t)
		memory[t] = u
		return u
	}
}
type
  TCache = specialize TFPGMap<TKey, TData>;

var
  Cache: TCache;

...
function m(Key: TKey): TData;
begin
  if not Assigned(Cache) then
    Cache := TCache.Create;
  if not Cache.TryGetData(Key, Result) then
  begin
    Result := f(Key);
    Cache.Add(Key, Result);
  end;
end;

my %cache;
sub fib {
    my $n = shift;
    return $cache{$n} if exists $cache{$n};
    return $cache{$n} = $n if $n < 2;
    return $cache{$n} = fib($n-1) + fib($n-2);
}

print "\n\nCustom memoized implementation\n";
foreach my $n ( 1..10 ) {
    print ' ' . fib( $n );
}

sub f {
    my $n = shift;
    return $n if $n < 2;
    f($n-1) + f($n-2);
}

memoize('f');

print "\n\nFast implementation using CPAN Memoization\n";
foreach my $n ( 1..10 ) {
    print ' ' . f( $n );
}

m = Hash.new{|hash, key| hash[key] = f(key)}