Stone's Note
0%

PHP 抽奖算法

发表于 更新于

在Google搜索“php 抽奖”, 通篇最为常见的算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
<?php
// “经典抽奖算法”
function rand2($arr)
{
    $sum = array_sum($arr);

    foreach($arr as $key => $value)
    {
        $ret = rand(0, $sum * MAX - 1);

        if ($ret < $value * MAX)
            return $key;
        else
            $sum -= $value;
    }
}
?>

算法思路：

  1. 将每个元素对应的 “概率” * “一个大整数” 得到一个“概率整数”，将所有元素的“概率整数”求和得到随机数的范围 sum
  2. 在[0, sum]范围随机一个数 ret， 若ret小于第一个元素的“概率整数”，则第一个元素被选中，返回
  3. 否则，将第一个元素从集合中删除，重新计算 sum，重复进行步骤 2，直到返回一个元素为止

这样样本总体越来越小，最终一定有一个元素被选中

是否可以优化？
需要每次循环都执行一次随机算法吗？

优化版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
<?php
function rand1($arr)
{
    $sum = array_sum($arr);

    $ret = rand(0, $sum * MAX - 1);

    foreach($arr as $key => $value)
    {
        if ($ret < $value * MAX)
            return $key;
        else
            $ret -= $value * MAX;
    }
}
?>

算法思路：

  1. 将每个元素对应的 “概率” * “一个大整数” 得到一个“概率整数”，将所有元素的“概率整数”求和得到随机数的范围 sum
  2. 将元素看作以“概率整数”为长度的区间，依次排列在数轴[0, sum]上
  3. 在[0, sum]范围随机一个数 ret，ret 落在哪个区间，则哪个区间对应的元素被选中

比较：

  • 两个算法看起来差别不大，其实思路不太一样
  • 第二个算法可以少进行n次随机数调用

下面让我们测试一下，写两个版本，分别在10万次的随机后，看下概率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
<?php

const MAX = 1000000;

$arr = array(
    'a' => 0.6,
    'b' => 0.3,
    'c' => 0.1,
);

function rand1($arr)
{
    $sum = array_sum($arr);

    $ret = rand(0, $sum * MAX - 1);

    foreach($arr as $key => $value)
    {
        if ($ret < $value * MAX)
            return $key;
        else
            $ret -= $value * MAX;
    }
}


// “经典抽奖算法”
function rand2($arr)
{
    $sum = array_sum($arr);

    foreach($arr as $key => $value)
    {
        $ret = rand(0, $sum * MAX - 1);

        if ($ret < $value * MAX)
            return $key;
        else
            $sum -= $value;
    }
}

$ret = array();

for ($i = 0 ;$i <= MAX;++$i)
{
    $char = rand1($arr);
    if (! isset($ret[$char]))
        $ret[$char] = 1;
    else
        $ret[$char] += 1;
}

foreach($ret as $key => $num)
{
    printf("%s: %f\n", $key, $num / MAX);
}

print("\n");
$ret = array();

for ($i = 0 ;$i <= MAX;++$i)
{
    $char = rand2($arr);
    if (! isset($ret[$char]))
        $ret[$char] = 1;
    else
        $ret[$char] += 1;
}

foreach($ret as $key => $num)
{
    printf("%s: %f\n", $key, $num / MAX);
}

?>

每个随机算法运行10万次，查看运行结果

1
2
3
4
5
6
7
a: 0.600406
b: 0.299639
c: 0.099956

a: 0.600070
b: 0.300149
c: 0.099782

结果基本符合每个元素的初始化比例