PHP Memoization via userland code
PHP
Switch branches/tags
Nothing to show
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
README.md
memoize.php

README.md

PHP Memoize

Userland implementation written in PHP 5.4, but easily downgraded to 5.3 (by removing both callable type hints).

Wikipedia: Memoization


function memoize ( callable $fnOrig, callable $fnHash )


fnOrig

The first argument is your function to optimize.

fnHash

The second argument is your hashing function, which will receive a single argument: an array representing 
the parameters. Your hash function should return a value that can safely be used an array key.

* Note: both arguments will be invoked as the first argument to call_user_func().

Return Values

The return value is an anonymous function that you can substitute in place of your original function call.

Demo

We will use this simple factorial function to demonstrate the reduction in required invocations:

function factorial($n) {
    if ($n == 0) return 1;
    return factorial($n - 1);
}

First, the long way

$i = pow(10, 4);
while (--$i) {
    factorial(10);
}

This requires 109989 invocations of factorial().

Now, memoized

$fact = memoize('factorial', function($args) {
    return $args[0];
});
$i = pow(10, 4);
while (--$i) {
    $fact(10);
}

Here, 11 invocations of factorial().


Variations

This function is extremely flexible:

$fact = memoize('factorial', 'your_hasher');
$fact = memoize('math::factorial', 'lib::hash');
$apiGetUserData = memoize(
    [new Api, 'getUserData'],
    [new Hasher, 'hashUserData']
);
$Logger = new Logger;
$toJson = memoize(function ($user, $action) use ($Logger) {
    $Logger->warn('cache miss');
    return json_encode(['user' => $user, 'action' => $action]);
}, function ($args) use ($Logger) {
    $Logger->info('cache lookup');
    return vsprintf("%d:%s", $args);
});