Hoa central
Public Member Functions | Static Public Member Functions | Protected Attributes | Private Member Functions | Static Private Attributes | List of all members
Hoa\Cache\Memoize Class Reference

Public Member Functions

 __invoke ()
 

Static Public Member Functions

static getInstance ($callable)
 

Protected Attributes

 $_callable = null
 
 $_arguments = []
 

Private Member Functions

 __construct ()
 

Static Private Attributes

static $_multiton = []
 

Detailed Description

Class .

Memoization is useful when making dynamic programming for example because it avoid to compute a function if it was previously computed with the same arguments. A symptomatic example is the Fibonacci number which one can naively implement as follows:

function fib ( $x ) {

    if($x < 2)
        return 1;

    return fib($x - 1) + fib($x - 2);
}

var_dump(fib(30)); // int(1346269)

A first and trivial optimization could be:

$fib = memoize('fib');
var_dump($fib(30));

But here, we only memoize fib(30) and not fib(29), fib(28) etc. A universal transformation is then proposed with a closure:

function fib ( $x ) {

    $self = null;
    $m    = function ( $x ) use ( &$self ) {

        if($x < 2)
            return 1

        return $self($x - 1) + $self($x - 2);
    }
    $self = memoize($m);

    return $self($x);
}

var_dump(fib(30));

It's far better because we are making real dynamic programming. But we could do better from a strict PHP point of view with indirect recursion:

function fib ( $x ) {

    $_fib = memoize('_fib');

    return $_fib($x);
}

function _fib ( $x ) {

    if($x < 2)
        return 1;

    $fib = memoize('fib');

    return $fib($x - 1) + $fib($x - 2);
}

var_dump(fib(30));

With an old machin, the last implementation is 350,000 times faster than the first implementation. Try to compute fib(1024) with the two last implementations, it's fast and inconceivable with the first one.

Definition at line 112 of file Memoize.php.

Constructor & Destructor Documentation

Hoa\Cache\Memoize::__construct ( )
private

Singleton.

Returns
void

Definition at line 142 of file Memoize.php.

143  {
144  return;
145  }

Member Function Documentation

Hoa\Cache\Memoize::__invoke ( )

Memoization algorithm.

Parameters
...... Arguments.
Returns
mixed

Definition at line 172 of file Memoize.php.

173  {
174  $arguments = func_get_args();
175  $id = md5(serialize($arguments));
176 
177  if (!isset($this->_arguments[$id])) {
178  $this->_arguments[$id] = $this->_callable->distributeArguments(
179  $arguments
180  );
181  }
182 
183  return $this->_arguments[$id];
184  }
static Hoa\Cache\Memoize::getInstance (   $callable)
static

Get a memoization (multiton).

Parameters
mixed$callableCallable.
Returns

Definition at line 153 of file Memoize.php.

154  {
155  $callable = xcallable($callable);
156  $hash = $callable->getHash();
157 
158  if (!isset(self::$_multiton[$hash])) {
159  self::$_multiton[$hash] = new static();
160  self::$_multiton[$hash]->_callable = $callable;
161  }
162 
163  return self::$_multiton[$hash];
164  }

Member Data Documentation

Hoa\Cache\Memoize::$_arguments = []
protected

Definition at line 133 of file Memoize.php.

Hoa\Cache\Memoize::$_callable = null
protected

Definition at line 126 of file Memoize.php.

Hoa\Cache\Memoize::$_multiton = []
staticprivate

Definition at line 119 of file Memoize.php.


The documentation for this class was generated from the following file: