Logo

Programming-Idioms

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

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.

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

CPAN module Memoize can be used to replace a subroutine with a memoized version. See doc for details.
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 );
}

Custom memoization of a Fibonacci function, using a hash to cache result values. Should work for any pure function; i.e. stateless and with no side-effects.
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.
New implementation...
< > ⌨
programming-idioms.org 
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 );
}

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

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;

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


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