PHP权重算法
我想知道这是否是一个足够的算法来寻找加权系统的最佳值。 我可以添加什么东西来让它变得更好吗？
在此示例中，我希望 $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 );
I'm wondering if this is a sufficient algorithm for finding the best value with a weighted system. Is there anything I could add to make it better?
in this example I would like the probability of $object->get() returning test4 to be 4 times greater than the probability of it returning 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 );
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
详细说明streetpc的答案； 在数据数组旁边，使用 add() 来维护一个相同大小的键数组，在其中存储范围的上限； 对于您的示例，该数组将类似于 {10, 30, 60, 100}。 （或者，使用一个包含对象或结构的数组，其中包含数据和键。）然后，您的 get() 方法只是在排序列表中搜索大于
$ 的第一个元素x； 与您的方法的 O(N) 相比，二分搜索可以在 O(ln N) 中完成此操作。 您会消耗一些额外的内存——但对于大多数应用程序来说，这看起来是一个很好的权衡。To elaborate on streetpc's answer; alongside your data array, use
add()to maintain a same-sized keys array where you store the upper bound on your range; for your example, that array would look like {10, 30, 60, 100}. (Or, use one array containing objects or structs that contain both the data and the key.) Then, yourget()method is simply searching a sorted list for the first element greater than$x; a binary search could do that in O(ln N), compared to O(N) for your method. You'll chew up a little extra memory -- but for most applications, it looks like a good tradeoff.看起来很公平，取决于用途。 如果您需要
get()方法获得更好的性能，您可以在add()方法中构建范围值并使用二分法。Seems fair enough, depends on the use. If you need better performance for the
get()method, you could build your range values in theadd()method and use dichotomy.