Весовой алгоритм PHP

Question

Мне интересно, достаточно ли этого алгоритма для нахождения наилучшего значения с помощью взвешенной системы. Что-нибудь, что я мог бы добавить, чтобы сделать это лучше?

в этом примере я бы хотел, чтобы вероятность того, что $object->get() вернет test4, будет в 4 раза больше, чем вероятность того, что он вернет 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

Чтобы уточнить ответ Streetpc; наряду с вашим массивом данных, используйте add(), чтобы поддерживать массив ключей того же размера, где вы храните верхнюю границу вашего диапазона; для вашего примера этот массив будет выглядеть как {10, 30, 60, 100}. (Или используйте один массив, содержащий объекты или структуры, которые содержат как данные, так и ключ.) Затем ваш метод get() просто ищет отсортированный список для первого элемента, большего чем $x; бинарный поиск может сделать это в O (ln N), по сравнению с O (N) для вашего метода. Вы потратите немного дополнительной памяти, но для большинства приложений это выглядит как хороший компромисс.

Answer 2

Кажется достаточно справедливым, зависит от использования. Если вам нужна лучшая производительность для метода get(), вы можете построить значения диапазона в методе add() и использовать дихотомию.