PHP Weight Algorithm

Question

Je me demande si c'est un algorithme suffisant pour trouver la meilleure valeur avec un système pondéré. Y a-t-il quelque chose que je pourrais ajouter pour le rendre meilleur?

Dans cet exemple, je souhaiterais que la probabilité de retour de test44 soit 4 fois supérieure à la probabilité de retour de test1 à $object->get().

class weightCalculator { 
    var $data = array(); 
    var $universe = 0; 

    function add($data, $probability){ 
     $this->data[ $x = sizeof($this->data) ] = new stdClass; 
     $this->data[ $x ]->value = $data; 
     $this->universe += $this->data[ $x ]->probability = abs($probability); 
    } 

    function get(){ 
     if(!$this->universe){ 
      return null; 
     } 
     $x = round(mt_rand(0, $this->universe)); 
     $max = 0; 
     $i = 0; 

     while($x > $max){ 
      $max += $this->data[ $i++ ]->probability; 
     } 
     $val=-1; 
     if($this->universe==1){ 
      $val = $this->data[$i]->value;  
      } else { 
      $val = $this->data[$i-1]->value;     
     } 
     return $val; 
    } 
} 

$object = new weightCalculator; 
$object->add('test1', 10); 
$object->add('test2', 20); 
$object->add('test3', 30); 
$object->add('test4', 40); 

Answer 1

Pour élaborer sur la réponse de streetpc; à côté de votre tableau de données, utilisez add() pour conserver un tableau de clés de même taille dans lequel vous stockez la limite supérieure de votre plage; pour votre exemple, ce tableau ressemblerait à {10, 30, 60, 100}. (Ou utilisez un tableau contenant des objets ou des structures contenant à la fois les données et la clé.) Ensuite, votre méthode get() recherche simplement une liste triée pour le premier élément supérieur à $x; une recherche binaire pourrait faire cela dans O (ln N), comparé à O (N) pour votre méthode. Vous allez mâcher un peu de mémoire supplémentaire - mais pour la plupart des applications, cela ressemble à un bon compromis.

Answer 2

Cela semble assez juste, cela dépend de l'utilisation. Si vous avez besoin de meilleures performances pour la méthode get(), vous pouvez créer vos valeurs de plage dans la méthode add() et utiliser la dichotomie.