Logo

Programming-Idioms

# 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.
New implementation

Be concise.

Be useful.

All contributions dictatorially edited by webmasters to match personal tastes.

Please do not paste any copyright violating material.

Please try to avoid dependencies to third-party libraries and frameworks.

Other implementations 
#include <map>
using namespace std;
template <typename F, typename T>
auto m(F f) {
    return [f] (T x) {
        map<T, T> static m;
        auto static n {m.end()};
        auto i {m.find(x)};
        if (i not_eq n) return i->second;
        return m[x] = f(x);
    };
}
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
	}
}
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;

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 );
}

use Memoize;
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 );
}

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


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

Preview