Created
February 7, 2013 19:12
-
-
Save dav-m85/4733329 to your computer and use it in GitHub Desktop.
Vector class along with a cool algorithm that... let me describe it.
Say we want 100 items from 3 different sources, and we want with it different ratios from each. The sources arent perfect and sometimes we dont get enough item to match a ratio. This algorithm makes the other sources spit more items.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
/** | |
* I rewrote quickly a Vector class, reinventing the wheel sorry :) | |
*/ | |
class Vector implements arrayaccess{ | |
private $_x = array(); | |
public function offsetExists ( $offset ){ | |
return isset($this->_x[$offset]); | |
} | |
public function offsetGet ( $offset ){ | |
return $this->_x[$offset]; | |
} | |
public function offsetSet ( $offset , $value ){ | |
$this->_x[$offset] = $value; | |
} | |
public function offsetUnset ( $offset ){ | |
unset($this->_x[$offset]); | |
} | |
public static function unity($i){ | |
$v = new self; | |
$v->_x = array_fill(0, $i, 1.0); | |
return $v; | |
} | |
public function __construct(){ | |
$this->_x = func_get_args(); | |
} | |
public function add(Vector $a){ | |
$b = clone $this; | |
for($i = 0; $i < count($b->_x);$i++){ | |
$b->_x[$i] += $a[$i]; | |
} | |
return $b; | |
} | |
public function sub(Vector $a){ | |
return $this->add($a->multiply(-1.0)); | |
} | |
public function multiply($j){ | |
$b = clone $this; | |
for($i = 0; $i < count($b->_x);$i++){ | |
$b->_x[$i] *= $j; | |
} | |
return $b; | |
} | |
public function sum(){ | |
$r = 0; | |
for($i = 0; $i < count($this->_x);$i++){ | |
$r += $this->_x[$i]; | |
} | |
return $r; | |
} | |
public function truncate(){ | |
$b = clone $this; | |
for($i = 0; $i < count($b->_x);$i++){ | |
if($b->_x[$i] < 0){ | |
$b->_x[$i] = 0; | |
} | |
} | |
return $b; | |
} | |
public function product(Vector $a){ | |
$b = clone $this; | |
for($i = 0; $i < count($b->_x);$i++){ | |
$b->_x[$i] *= $a[$i]; | |
} | |
return $b; | |
} | |
public function square(){ | |
$r = $this->sum(); | |
return $this->multiply(1.0 / $r); | |
} | |
public function round(){ | |
$b = clone $this; | |
for($i = 0; $i < count($b->_x);$i++){ | |
$b->_x[$i] = round($b->_x[$i]); | |
} | |
return $b; | |
} | |
public function __toString(){ | |
return '['.join(', ', $this->_x).']'; | |
} | |
public function weight(Vector $mass){ // fat algorithm comes here | |
$b = clone $this; | |
$w = clone $mass; | |
$p = 0; | |
$n = 0; | |
for($i = 0; $i < count($b->_x);$i++){ | |
if($w[$i] != 0){ | |
$n += $w[$i]; | |
$b[$i] += $w[$i]; | |
} | |
else{ | |
$p += $b[$i]; | |
} | |
} | |
if($p == 0){ | |
return $b; | |
} | |
for($i = 0; $i < count($b->_x);$i++){ | |
if($w[$i] == 0){ | |
$b[$i] *= 1.0 - $n / $p; | |
} | |
} | |
return $b; | |
} | |
} | |
// Lets say we want 100 items from 3 different sources... | |
$n = 100.0; | |
// ... with the following ratios (10% from first source, 20% from second, 70% from third), ... | |
$a = new Vector(0.1, 0.2, 0.7); | |
// ... but can only fetch that much. | |
$r = new Vector(200, 10, 200); | |
echo 'fetchd: ' . $r . PHP_EOL; | |
// Follows here a simple algorithm wich converge (I shall demonstrate this) to the most handsome | |
// solution. Per say, if one source gives not enough, we allow others to push more items accordingly. | |
do{ | |
$retry++; // we do not want an infinite loop, do we ? | |
$a = $a->square(); // make sum of components equal 1 | |
$ni = Vector::unity(3)->multiply($n)->product($a); // wanted volumes per source | |
echo 'wanted: ' . $ni->round() . PHP_EOL; | |
$d = $r->sub($ni)->multiply(1.0/$n); // delta from wanted to really fetched | |
$w = $d->multiply(-1)->truncate()->multiply(-1); // get where it's missing | |
$ws = $w->sum(); // we stop when this reach 0, aka no more unsatisfied ratio conditions. | |
echo 'w : ' . $w . PHP_EOL; | |
echo 'a : ' . $a . PHP_EOL; | |
$a = $a->weight($w); // thats the algo | |
echo 'a\' : ' . $a . PHP_EOL; | |
echo '----------------------' . PHP_EOL; | |
} while( $ws < 0 && $retry <= 5); | |
$a = $a->square(); | |
echo 'a end : ' . $a . PHP_EOL; | |
$ni = Vector::unity(3)->multiply($n)->product($a); | |
echo 'r end : ' . $ni->round() . PHP_EOL; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment