AliasMethod随机概率算法一种适合用于抽奖的算法

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

已有 7 条评论
  1. Austot

    Zithromax Vs. Amoxicillin generic cialis Kamagra Gelatina Orale 10 Cialis Laboratorio Lilly

    Austot 回复
  2. FranKap

    Catalogo Levitra Generico Viagra Azione Le Viagra Pourquoi levitra generico prezzo Supreme Suppliers

    FranKap 回复
  3. Kelemetry

    Finasteride Costi Propecia Generico Asacol viagra Bentyl Formulex Come Comprare Il Viagra In Farmacia

    Kelemetry 回复
  4. FranKap

    Isotretinoin 10mg No Prior Script generic viagra Viagra Effetti Sulle Donne Fish Amoxicillin Propecia Ejaculation Cialis

    FranKap 回复
  5. Austot

    Cytotec Commander onde comprar dapoxetina no brasil Unisom In Singapore Cytotec 200pg Pharmacie En Ligne

    Austot 回复
  6. FranKap

    Nolvadex Research Products For Sale viagra online prescription Indian Pharm Inderal Ciprofloxacin Et Alcool

    FranKap 回复
  7. Kelemetry

    Amoxicilina Worldwide Medication Amoxicillin Pregnancy Category viagra prix suisse en bourges Propecia Pnt Cialis 10 Mg Opinioni

    Kelemetry 回复
发表新评论