Skip to content

Instantly share code, notes, and snippets.

@dav-m85
Created February 7, 2013 19:12
Show Gist options
  • Save dav-m85/4733329 to your computer and use it in GitHub Desktop.
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.
<?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