php 权重随机3种算法
权重随机算法在产品开发中或多或少都遇到，如抽奖，集群服务器中的负载均衡。下面我以抽奖为例：
$arr = array(
array('name' => 'A', 'weight' => 1), //一等奖
array('name' => 'B', 'weight' => 2), //二等奖
array('name' => 'C', 'weight' => 3), //三等奖
);
/*
* 计算总权重* */
function sum($arr)
{
$total = 0;
foreach ($arr as $value) {
$total += $value['weight'];
}
return $total;
}
/*
* 方法1，放大法。时间复杂度O(1)，占用空间大* */
function random1($arr)
{
$weightSum = sum($arr);
if ($weightSum <= 0) {
return ;
}
//初始化对象池， 相等于抽奖箱
$pool = array();
foreach ($arr as $v) {
for ($i = 0; $i <= $v['weight']; $i++) {
$pool[] = $v;
}
}
//打乱数组，这步可有可无。因为我这里是模拟抽奖，打乱顺序
shuffle($pool);
//抽奖
$randNum = rand(1, $weightSum);
return $pool[$randNum - 1]['name']; //返回 A或B或C;
}
/*
*方法2, 区间法*
* **/
function random2($arr)
{
//计算总权重
$weightSum = sum($arr);
if ($weightSum <= 0) {
return ;
}
/*计算区间*/
$total = 0;
foreach ($arr as $key => $val) {
$total += $val['weight'];
//计算区间范围
$arr[$key]['range'] = $total;
}
/* 一等奖区间 (0,1];二等奖 (1,3];三等奖(3,6] */
/*计算区间*/
/*抽奖*/
$randNum = rand(1, $weightSum);
foreach ($arr as $k => $v) {
if ($v['range'] >= $randNum) {
return $v['name']; //返回 A或B或C;
}
}
/*抽奖*/
}
/**方法3**/
function random3($arr)
{
$weightSum = sum($arr);
if ($weightSum <= 0) {
return ;
}
$randNum = rand(1, $weightSum);
foreach ($arr as $k => $v) {
if ($randNum <= $v['weight']) {
return $v['name']; //返回 A或B或C;
}
$randNum -=$v['weight'];
}
}
$choosed = random1($arr);
echo $choosed . PHP_EOL;
