PHP Poids algorithme

Question

Je me demande si cela est un algorithme suffisant pour trouver la meilleure valeur avec un système pondéré. Est-ce que je pourrais ajouter pour le rendre meilleur?

dans cet exemple, je voudrais que la probabilité de retour $object->get() test4 être 4 fois plus grande que la probabilité de le retourner test1.

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 des précisions sur la réponse de streetpc; à côté de votre tableau de données, utilisez add() pour maintenir un tableau de clés de même taille où 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 struct contenant à la fois les données et la clé.) Ensuite, votre méthode de recherche get() est simplement une liste triée pour le premier élément supérieur à $x; une recherche binaire pourrait faire en O (ln N), par rapport à O (N) pour la méthode. Vous mâchez un peu de mémoire supplémentaire -. Mais pour la plupart des applications, il ressemble à un bon compromis entre

Answer 2

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