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