AliasMethod算法PHP源码

<?php
    class AliasMethod
    {
        private $length;
        private $prob_arr;
        private $alias;
        private $pdf;
    
        public function __construct ($pdf) {
            $this->length = 0;
            $this->prob_arr = $this->alias = array();
            $this->pdf = $pdf;
            $this->_init($pdf);
        }
        private function _init($pdf) {
            $this->length = count($pdf);
            if($this->length == 0) {
                throw new \Exception("pdf is empty");
            }
            if(array_sum($pdf) != 1.0) {
                throw new \Exception("pdf sum not equal 1, sum:".array_sum($pdf));
            }
    
            $small = $large = array();
            for ($i=0; $i < $this->length; $i++) {
                $pdf[$i] *= $this->length;
                if($pdf[$i] < 1.0) {
                    $small[] = $i;
                } else {
                    $large[] = $i;
                }
            }
    
            while (count($small) != 0 && count($large) != 0)  {
                $s_index = array_shift($small);
                $l_index = array_shift($large);
                $this->prob_arr[$s_index] = $pdf[$s_index];
                $this->alias[$s_index] = $l_index;
                $pdf[$l_index] -= 1.0 - $pdf[$s_index];
                if($pdf[$l_index] < 1.0) {
                    $small[] = $l_index;
                } else {
                    $large[] = $l_index;
                }
            }
            while(!empty($small)) $this->prob_arr[array_shift($small)] = 1.0;
            while (!empty($large)) $this->prob_arr[array_shift($large)] = 1.0;
        }
        public function next_rand() {
            $column = mt_rand(0, $this->length - 1);
            return mt_rand() / mt_getrandmax() < $this->prob_arr[$column] ? $column : $this->alias[$column];
        }
        public static function Rand($pdf) {
        $am = new self($pdf);
        return $am->next_rand();
        }
    }

使用方法：

AliasMethod::Rand($pdf)

参数：$pdf 密度分布 即不同事件的概率值（一位数组，每个元素为一个概率，数组元素之和必须为1，否则会抛出异常）

返回：本次随机到概率事件（$pdf数组的某个下标）

例子：

假设 一个抽奖逻辑：

# 1%  获得一个皮肤
# 10% 获得一个10个皮肤碎片
# 89% 获得谢谢参与

echo AliasMethod::Rand(array(0.01,0.1,0.89));

返回 0 则为获得皮肤
返回 1 则为获得10个皮肤碎片
返回 2 则为获得谢谢参与

测试：

对上述例子 进行3组测试每次10000次获取 分别得到以下结果，事件出现次数接近于设置概率

2--->0.892
1--->0.0978
0--->0.0105

1--->0.1051
2--->0.8847
0--->0.0105

2--->0.8857
1--->0.1055
0--->0.0091

最后更新于 2022-01-18 18:02:57 并被添加「」标签，已有 10507 位童鞋阅读过。

本站使用「署名 4.0 国际」创作共享协议，可自由转载、引用，但需署名作者且注明文章出处