Logo

Programming-Idioms

This language bar is your friend. Select your favorite languages!

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.

m = Hash.new{|hash, key| hash[key] = f(key)} 
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)


New implementation...
< >
programming-idioms.org