0

我想知道这是否是使用加权系统找到最佳值的足够算法。有什么我可以添加以使其更好的吗？

在这个例子中，我希望$object->get()返回 test4 的概率比返回 test1 的概率大 4 倍。

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 );
4

2 回答 2

0

看起来很公平，取决于用途。如果您需要该get()方法的更好性能，您可以在该方法中构建您的范围值add()并使用二分法。

于 2009-07-09T20:36:59.493 回答
0

详细说明streetpc的答案；在您的数据数组旁边，用于add()维护一个相同大小的键数组，您可以在其中存储范围的上限；对于您的示例，该数组看起来像 {10, 30, 60, 100}。（或者，使用一个包含数据和键的对象或结构的数组。）然后，您的get()方法只是在排序列表中搜索大于$x;的第一个元素。与您的方法的 O(N) 相比，二进制搜索可以在 O(ln N) 中做到这一点。您会消耗一点额外的内存——但对于大多数应用程序来说，这看起来是一个不错的折衷方案。

于 2009-07-10T17:29:48.900 回答