喜迎
春节

加权随机算法：按权重控制的概率选择机制

PHP 算法 加权随机算法
算法
发布日期:   2025-11-20
文章字数:   1.8k
阅读时长:   8 分

如何让稀有物品掉落率低、普通物品掉落率高？加权随机算法提供了完美的概率控制方案。

问题背景

在很多应用场景中，我们需要按照预设的概率分布来进行随机选择，而不是简单的均匀随机：

  • 游戏开发：稀有装备1%概率，普通装备50%概率
  • 推荐系统：热门商品推荐概率高，冷门商品概率低
  • 负载均衡：高性能服务器分配更多请求
  • 广告投放：高价值广告展示频率更高
  • 抽奖活动：一等奖概率0.1%，参与奖概率90%

简单随机选择无法满足这些需求，而加权随机(Weighted Random) 算法提供了完美的解决方案。

算法原理

加权随机核心思想是：根据权重构建概率区间，随机数落在哪个区间就选择对应的元素。

基本概念

假设我们有三个物品和对应的权重：

1
2
3
物品A: 权重 5
物品B: 权重 3  
物品C: 权重 2

总权重 = 5 + 3 + 2 = 10

每个物品的概率分布：

1
2
3
物品A: 5/10 = 50%
物品B: 3/10 = 30%
物品C: 2/10 = 20%

实现方法

方法一：线性扫描（简单直观）

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
<?php

class WeightedRandom {
    
    /**
     * 线性扫描实现加权随机
     * 
     * @param array $items 格式：['物品A' => 权重, '物品B' => 权重, ...]
     * @return mixed 随机选中的物品
     */
    public static function linearSelect($items) {
        // 计算总权重
        $totalWeight = array_sum($items);
        
        // 生成随机数
        $random = mt_rand(1, $totalWeight);
        
        // 线性扫描找到对应的物品
        $current = 0;
        foreach ($items as $item => $weight) {
            $current += $weight;
            if ($random <= $current) {
                return $item;
            }
        }
        
        return null; // 理论上不会执行到这里
    }
}

// 使用示例：游戏物品掉落
$lootTable = [
    '普通药水' => 50,   // 50% 概率
    '稀有装备' => 30,   // 30% 概率  
    '传奇武器' => 15,   // 15% 概率
    '神器'     => 5     // 5% 概率
];

echo "=== 游戏物品掉落模拟 ===\n";
for ($i = 0; $i < 10; $i++) {
    $loot = WeightedRandom::linearSelect($lootTable);
    echo "第 " . ($i + 1) . " 次掉落: " . $loot . "\n";
}

?>

方法二：别名方法（高效算法）

对于需要频繁抽样的大规模场景，可以使用更高效的别名方法：

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
<?php

class AliasMethod {
    private $prob;
    private $alias;
    private $n;
    
    /**
     * 初始化别名表
     * 
     * @param array $weights 权重数组
     */
    public function __construct($weights) {
        $this->n = count($weights);
        $this->prob = array_fill(0, $this->n, 0);
        $this->alias = array_fill(0, $this->n, 0);
        
        $this->buildAliasTable($weights);
    }
    
    /**
     * 构建别名表
     */
    private function buildAliasTable($weights) {
        $total = array_sum($weights);
        $prob = array_map(function($w) use ($total) {
            return $w * $this->n / $total;
        }, $weights);
        
        $small = [];
        $large = [];
        
        // 分类
        for ($i = 0; $i < $this->n; $i++) {
            if ($prob[$i] < 1) {
                $small[] = $i;
            } else {
                $large[] = $i;
            }
        }
        
        // 构建别名表
        while (!empty($small) && !empty($large)) {
            $s = array_pop($small);
            $l = array_pop($large);
            
            $this->prob[$s] = $prob[$s];
            $this->alias[$s] = $l;
            
            $prob[$l] = ($prob[$l] + $prob[$s]) - 1;
            
            if ($prob[$l] < 1) {
                $small[] = $l;
            } else {
                $large[] = $l;
            }
        }
        
        // 处理剩余项
        while (!empty($large)) {
            $l = array_pop($large);
            $this->prob[$l] = 1;
        }
        
        while (!empty($small)) {
            $s = array_pop($small);
            $this->prob[$s] = 1;
        }
    }
    
    /**
     * 生成随机选择
     */
    public function next() {
        $i = mt_rand(0, $this->n - 1);
        if (mt_rand() / mt_getrandmax() < $this->prob[$i]) {
            return $i;
        } else {
            return $this->alias[$i];
        }
    }
}

// 使用别名方法的加权随机类
class EfficientWeightedRandom {
    
    /**
     * 使用别名方法实现高效加权随机
     */
    public static function aliasSelect($items) {
        static $aliasMethods = [];
        
        $key = md5(serialize($items));
        if (!isset($aliasMethods[$key])) {
            $aliasMethods[$key] = new AliasMethod(array_values($items));
        }
        
        $index = $aliasMethods[$key]->next();
        $itemNames = array_keys($items);
        return $itemNames[$index];
    }
}

?>

方法三：二分查找（性能均衡）

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
<?php

class BinarySearchWeightedRandom {
    private $prefixSums;
    private $items;
    private $totalWeight;
    
    /**
     * 预处理前缀和数组
     */
    public function __construct($items) {
        $this->items = array_keys($items);
        $this->totalWeight = array_sum($items);
        
        // 构建前缀和数组
        $this->prefixSums = [];
        $sum = 0;
        foreach ($items as $weight) {
            $sum += $weight;
            $this->prefixSums[] = $sum;
        }
    }
    
    /**
     * 二分查找实现快速选择
     */
    public function select() {
        $target = mt_rand(1, $this->totalWeight);
        
        // 二分查找
        $left = 0;
        $right = count($this->prefixSums) - 1;
        
        while ($left < $right) {
            $mid = $left + intval(($right - $left) / 2);
            
            if ($this->prefixSums[$mid] < $target) {
                $left = $mid + 1;
            } else {
                $right = $mid;
            }
        }
        
        return $this->items[$left];
    }
}

?>

完整应用示例

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
<?php

// 完整的加权随机应用示例
class WeightedRandomApplication {
    
    /**
     * 游戏掉落系统
     */
    public static function gameLootSystem() {
        echo "=== 游戏掉落系统 ===\n";
        
        $monsterLootTable = [
            '金币' => 400,
            '普通装备' => 300,
            '稀有装备' => 200,
            '史诗装备' => 80,
            '传奇装备' => 18,
            '神器' => 2
        ];
        
        // 模拟击杀怪物掉落
        $drops = [];
        for ($i = 0; $i < 1000; $i++) {
            $loot = WeightedRandom::linearSelect($monsterLootTable);
            if (!isset($drops[$loot])) {
                $drops[$loot] = 0;
            }
            $drops[$loot]++;
        }
        
        // 统计结果
        echo "1000次击杀掉落统计:\n";
        foreach ($drops as $item => $count) {
            $rate = ($count / 1000) * 100;
            $expected = ($monsterLootTable[$item] / array_sum($monsterLootTable)) * 100;
            echo sprintf("%-10s: 实际%.2f%% (预期%.2f%%)\n", 
                $item, $rate, $expected);
        }
    }
    
    /**
     * 推荐系统
     */
    public static function recommendationSystem() {
        echo "\n=== 商品推荐系统 ===\n";
        
        $products = [
            '热门商品A' => 100,
            '热门商品B' => 80,
            '普通商品C' => 30,
            '普通商品D' => 25,
            '冷门商品E' => 10,
            '新品F' => 5
        ];
        
        echo "今日推荐商品:\n";
        for ($i = 0; $i < 5; $i++) {
            $recommended = WeightedRandom::linearSelect($products);
            echo "推荐位 " . ($i + 1) . ": " . $recommended . "\n";
        }
    }
    
    /**
     * 抽奖活动
     */
    public static function lotterySystem() {
        echo "\n=== 抽奖活动系统 ===\n";
        
        $prizes = [
            '一等奖：iPhone' => 1,
            '二等奖：AirPods' => 5, 
            '三等奖：优惠券' => 50,
            '参与奖：谢谢参与' => 944
        ];
        
        echo "抽奖结果:\n";
        $results = [];
        for ($i = 0; $i < 100; $i++) {
            $prize = WeightedRandom::linearSelect($prizes);
            if (!isset($results[$prize])) {
                $results[$prize] = 0;
            }
            $results[$prize]++;
        }
        
        foreach ($results as $prize => $count) {
            echo $prize . ": " . $count . "次\n";
        }
    }
    
    /**
     * 性能测试
     */
    public static function performanceTest() {
        echo "\n=== 性能测试 ===\n";
        
        // 大规模权重表
        $largeWeightTable = [];
        for ($i = 0; $i < 1000; $i++) {
            $largeWeightTable["item_$i"] = mt_rand(1, 100);
        }
        
        // 线性扫描性能
        $start = microtime(true);
        for ($i = 0; $i < 10000; $i++) {
            WeightedRandom::linearSelect($largeWeightTable);
        }
        $linearTime = microtime(true) - $start;
        
        // 二分查找性能
        $bsRandom = new BinarySearchWeightedRandom($largeWeightTable);
        $start = microtime(true);
        for ($i = 0; $i < 10000; $i++) {
            $bsRandom->select();
        }
        $binaryTime = microtime(true) - $start;
        
        echo "线性扫描: " . number_format($linearTime, 4) . " 秒\n";
        echo "二分查找: " . number_format($binaryTime, 4) . " 秒\n";
        echo "性能提升: " . number_format(($linearTime - $binaryTime) / $linearTime * 100, 2) . "%\n";
    }
}

// 运行所有示例
WeightedRandomApplication::gameLootSystem();
WeightedRandomApplication::recommendationSystem();
WeightedRandomApplication::lotterySystem();
WeightedRandomApplication::performanceTest();

?>

算法对比

方法 时间复杂度 空间复杂度 适用场景
线性扫描 O(n) O(1) 权重项少，简单应用
二分查找 O(log n) O(n) 权重项多，性能要求高
别名方法 O(1) O(n) 超大规模，频繁抽样

最佳实践建议

1. 权重设计原则

1
2
3
4
5
6
7
8
9
10
11
12
13
// 好的权重设计
$goodWeights = [
    '常见物品' => 70,   // 70%
    '稀有物品' => 25,   // 25%  
    '史诗物品' => 4,    // 4%
    '传说物品' => 1     // 1%
];

// 避免的权重设计
$badWeights = [
    '物品A' => 0.0001,  // 概率过小，可能永远选不到
    '物品B' => 999999,  // 权重差异过大
];

2. 动态权重调整

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
class DynamicWeightedRandom {
    private $baseWeights;
    private $dynamicFactors;
    
    public function __construct($baseWeights) {
        $this->baseWeights = $baseWeights;
        $this->dynamicFactors = array_fill_keys(array_keys($baseWeights), 1);
    }
    
    /**
     * 根据用户行为动态调整权重
     */
    public function adjustWeight($item, $factor) {
        if (isset($this->dynamicFactors[$item])) {
            $this->dynamicFactors[$item] *= $factor;
        }
    }
    
    /**
     * 获取当前动态权重
     */
    public function getCurrentWeights() {
        $current = [];
        foreach ($this->baseWeights as $item => $weight) {
            $current[$item] = $weight * $this->dynamicFactors[$item];
        }
        return $current;
    }
    
    /**
     * 基于动态权重的选择
     */
    public function select() {
        $currentWeights = $this->getCurrentWeights();
        return WeightedRandom::linearSelect($currentWeights);
    }
}

总结

加权随机算法是概率控制的重要工具，具有以下特点：

核心优势

  1. 精确控制概率：严格按照权重分配选择概率
  2. 灵活配置：支持动态调整权重
  3. 性能可控：多种实现满足不同性能需求
  4. 应用广泛：适用于游戏、推荐、抽奖等场景

选择建议

  • 小规模数据：使用线性扫描，简单直观
  • 大规模数据：使用二分查找，性能均衡
  • 超频繁抽样：使用别名方法，极致性能

加权随机算法让概率控制变得简单而精确，是每个开发者都应该掌握的重要算法工具。

文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/weighted-random.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 算法 加权随机算法
赏
评 论
 上一篇
Fisher-Yates 洗牌算法
Fisher-Yates 洗牌算法
Fisher-Yates 洗牌算法（也称为 Knuth 洗牌）是一种高效且公正的随机洗牌算法，用于将数组或列表中的元素随机重新排列。 🎯 算法原理核心思想：从后往前遍历数组，将当前元素与随机位置的一个元素交换。 📝 算法步骤原始版本：1
2025-11-20 算法
PHP 算法 Fisher-Yates
下一篇 
蓄水池抽样算法：从大数据流中随机取样的优雅解决方案
蓄水池抽样算法：从大数据流中随机取样的优雅解决方案
如何在未知总量的数据流中公平地随机抽取样本？蓄水池抽样算法给出了完美的答案。 问题背景在大数据时代，我们经常面临这样的挑战：需要从一个规模未知或极大的数据集中随机抽取少量样本。比如： 从数十GB的日志文件中随机选取1万条记录进行分析
2025-11-20 算法
PHP 算法 蓄水池抽样算法
PHP 算法 加权随机算法
算法
发布日期:   2025-11-20
文章字数:   1.8k
阅读时长:   8 分

如何让稀有物品掉落率低、普通物品掉落率高？加权随机算法提供了完美的概率控制方案。

问题背景

在很多应用场景中，我们需要按照预设的概率分布来进行随机选择，而不是简单的均匀随机：

  • 游戏开发：稀有装备1%概率，普通装备50%概率
  • 推荐系统：热门商品推荐概率高，冷门商品概率低
  • 负载均衡：高性能服务器分配更多请求
  • 广告投放：高价值广告展示频率更高
  • 抽奖活动：一等奖概率0.1%，参与奖概率90%

简单随机选择无法满足这些需求，而加权随机(Weighted Random) 算法提供了完美的解决方案。

算法原理

加权随机核心思想是：根据权重构建概率区间，随机数落在哪个区间就选择对应的元素。

基本概念

假设我们有三个物品和对应的权重：

1
2
3
物品A: 权重 5
物品B: 权重 3  
物品C: 权重 2

总权重 = 5 + 3 + 2 = 10

每个物品的概率分布：

1
2
3
物品A: 5/10 = 50%
物品B: 3/10 = 30%
物品C: 2/10 = 20%

实现方法

方法一：线性扫描（简单直观）

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
<?php

class WeightedRandom {
    
    /**
     * 线性扫描实现加权随机
     * 
     * @param array $items 格式：['物品A' => 权重, '物品B' => 权重, ...]
     * @return mixed 随机选中的物品
     */
    public static function linearSelect($items) {
        // 计算总权重
        $totalWeight = array_sum($items);
        
        // 生成随机数
        $random = mt_rand(1, $totalWeight);
        
        // 线性扫描找到对应的物品
        $current = 0;
        foreach ($items as $item => $weight) {
            $current += $weight;
            if ($random <= $current) {
                return $item;
            }
        }
        
        return null; // 理论上不会执行到这里
    }
}

// 使用示例：游戏物品掉落
$lootTable = [
    '普通药水' => 50,   // 50% 概率
    '稀有装备' => 30,   // 30% 概率  
    '传奇武器' => 15,   // 15% 概率
    '神器'     => 5     // 5% 概率
];

echo "=== 游戏物品掉落模拟 ===\n";
for ($i = 0; $i < 10; $i++) {
    $loot = WeightedRandom::linearSelect($lootTable);
    echo "第 " . ($i + 1) . " 次掉落: " . $loot . "\n";
}

?>

方法二：别名方法（高效算法）

对于需要频繁抽样的大规模场景，可以使用更高效的别名方法：

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
<?php

class AliasMethod {
    private $prob;
    private $alias;
    private $n;
    
    /**
     * 初始化别名表
     * 
     * @param array $weights 权重数组
     */
    public function __construct($weights) {
        $this->n = count($weights);
        $this->prob = array_fill(0, $this->n, 0);
        $this->alias = array_fill(0, $this->n, 0);
        
        $this->buildAliasTable($weights);
    }
    
    /**
     * 构建别名表
     */
    private function buildAliasTable($weights) {
        $total = array_sum($weights);
        $prob = array_map(function($w) use ($total) {
            return $w * $this->n / $total;
        }, $weights);
        
        $small = [];
        $large = [];
        
        // 分类
        for ($i = 0; $i < $this->n; $i++) {
            if ($prob[$i] < 1) {
                $small[] = $i;
            } else {
                $large[] = $i;
            }
        }
        
        // 构建别名表
        while (!empty($small) && !empty($large)) {
            $s = array_pop($small);
            $l = array_pop($large);
            
            $this->prob[$s] = $prob[$s];
            $this->alias[$s] = $l;
            
            $prob[$l] = ($prob[$l] + $prob[$s]) - 1;
            
            if ($prob[$l] < 1) {
                $small[] = $l;
            } else {
                $large[] = $l;
            }
        }
        
        // 处理剩余项
        while (!empty($large)) {
            $l = array_pop($large);
            $this->prob[$l] = 1;
        }
        
        while (!empty($small)) {
            $s = array_pop($small);
            $this->prob[$s] = 1;
        }
    }
    
    /**
     * 生成随机选择
     */
    public function next() {
        $i = mt_rand(0, $this->n - 1);
        if (mt_rand() / mt_getrandmax() < $this->prob[$i]) {
            return $i;
        } else {
            return $this->alias[$i];
        }
    }
}

// 使用别名方法的加权随机类
class EfficientWeightedRandom {
    
    /**
     * 使用别名方法实现高效加权随机
     */
    public static function aliasSelect($items) {
        static $aliasMethods = [];
        
        $key = md5(serialize($items));
        if (!isset($aliasMethods[$key])) {
            $aliasMethods[$key] = new AliasMethod(array_values($items));
        }
        
        $index = $aliasMethods[$key]->next();
        $itemNames = array_keys($items);
        return $itemNames[$index];
    }
}

?>

方法三：二分查找（性能均衡）

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
<?php

class BinarySearchWeightedRandom {
    private $prefixSums;
    private $items;
    private $totalWeight;
    
    /**
     * 预处理前缀和数组
     */
    public function __construct($items) {
        $this->items = array_keys($items);
        $this->totalWeight = array_sum($items);
        
        // 构建前缀和数组
        $this->prefixSums = [];
        $sum = 0;
        foreach ($items as $weight) {
            $sum += $weight;
            $this->prefixSums[] = $sum;
        }
    }
    
    /**
     * 二分查找实现快速选择
     */
    public function select() {
        $target = mt_rand(1, $this->totalWeight);
        
        // 二分查找
        $left = 0;
        $right = count($this->prefixSums) - 1;
        
        while ($left < $right) {
            $mid = $left + intval(($right - $left) / 2);
            
            if ($this->prefixSums[$mid] < $target) {
                $left = $mid + 1;
            } else {
                $right = $mid;
            }
        }
        
        return $this->items[$left];
    }
}

?>

完整应用示例

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
<?php

// 完整的加权随机应用示例
class WeightedRandomApplication {
    
    /**
     * 游戏掉落系统
     */
    public static function gameLootSystem() {
        echo "=== 游戏掉落系统 ===\n";
        
        $monsterLootTable = [
            '金币' => 400,
            '普通装备' => 300,
            '稀有装备' => 200,
            '史诗装备' => 80,
            '传奇装备' => 18,
            '神器' => 2
        ];
        
        // 模拟击杀怪物掉落
        $drops = [];
        for ($i = 0; $i < 1000; $i++) {
            $loot = WeightedRandom::linearSelect($monsterLootTable);
            if (!isset($drops[$loot])) {
                $drops[$loot] = 0;
            }
            $drops[$loot]++;
        }
        
        // 统计结果
        echo "1000次击杀掉落统计:\n";
        foreach ($drops as $item => $count) {
            $rate = ($count / 1000) * 100;
            $expected = ($monsterLootTable[$item] / array_sum($monsterLootTable)) * 100;
            echo sprintf("%-10s: 实际%.2f%% (预期%.2f%%)\n", 
                $item, $rate, $expected);
        }
    }
    
    /**
     * 推荐系统
     */
    public static function recommendationSystem() {
        echo "\n=== 商品推荐系统 ===\n";
        
        $products = [
            '热门商品A' => 100,
            '热门商品B' => 80,
            '普通商品C' => 30,
            '普通商品D' => 25,
            '冷门商品E' => 10,
            '新品F' => 5
        ];
        
        echo "今日推荐商品:\n";
        for ($i = 0; $i < 5; $i++) {
            $recommended = WeightedRandom::linearSelect($products);
            echo "推荐位 " . ($i + 1) . ": " . $recommended . "\n";
        }
    }
    
    /**
     * 抽奖活动
     */
    public static function lotterySystem() {
        echo "\n=== 抽奖活动系统 ===\n";
        
        $prizes = [
            '一等奖：iPhone' => 1,
            '二等奖：AirPods' => 5, 
            '三等奖：优惠券' => 50,
            '参与奖：谢谢参与' => 944
        ];
        
        echo "抽奖结果:\n";
        $results = [];
        for ($i = 0; $i < 100; $i++) {
            $prize = WeightedRandom::linearSelect($prizes);
            if (!isset($results[$prize])) {
                $results[$prize] = 0;
            }
            $results[$prize]++;
        }
        
        foreach ($results as $prize => $count) {
            echo $prize . ": " . $count . "次\n";
        }
    }
    
    /**
     * 性能测试
     */
    public static function performanceTest() {
        echo "\n=== 性能测试 ===\n";
        
        // 大规模权重表
        $largeWeightTable = [];
        for ($i = 0; $i < 1000; $i++) {
            $largeWeightTable["item_$i"] = mt_rand(1, 100);
        }
        
        // 线性扫描性能
        $start = microtime(true);
        for ($i = 0; $i < 10000; $i++) {
            WeightedRandom::linearSelect($largeWeightTable);
        }
        $linearTime = microtime(true) - $start;
        
        // 二分查找性能
        $bsRandom = new BinarySearchWeightedRandom($largeWeightTable);
        $start = microtime(true);
        for ($i = 0; $i < 10000; $i++) {
            $bsRandom->select();
        }
        $binaryTime = microtime(true) - $start;
        
        echo "线性扫描: " . number_format($linearTime, 4) . " 秒\n";
        echo "二分查找: " . number_format($binaryTime, 4) . " 秒\n";
        echo "性能提升: " . number_format(($linearTime - $binaryTime) / $linearTime * 100, 2) . "%\n";
    }
}

// 运行所有示例
WeightedRandomApplication::gameLootSystem();
WeightedRandomApplication::recommendationSystem();
WeightedRandomApplication::lotterySystem();
WeightedRandomApplication::performanceTest();

?>

算法对比

方法 时间复杂度 空间复杂度 适用场景
线性扫描 O(n) O(1) 权重项少，简单应用
二分查找 O(log n) O(n) 权重项多，性能要求高
别名方法 O(1) O(n) 超大规模，频繁抽样

最佳实践建议

1. 权重设计原则

1
2
3
4
5
6
7
8
9
10
11
12
13
// 好的权重设计
$goodWeights = [
    '常见物品' => 70,   // 70%
    '稀有物品' => 25,   // 25%  
    '史诗物品' => 4,    // 4%
    '传说物品' => 1     // 1%
];

// 避免的权重设计
$badWeights = [
    '物品A' => 0.0001,  // 概率过小，可能永远选不到
    '物品B' => 999999,  // 权重差异过大
];

2. 动态权重调整

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
class DynamicWeightedRandom {
    private $baseWeights;
    private $dynamicFactors;
    
    public function __construct($baseWeights) {
        $this->baseWeights = $baseWeights;
        $this->dynamicFactors = array_fill_keys(array_keys($baseWeights), 1);
    }
    
    /**
     * 根据用户行为动态调整权重
     */
    public function adjustWeight($item, $factor) {
        if (isset($this->dynamicFactors[$item])) {
            $this->dynamicFactors[$item] *= $factor;
        }
    }
    
    /**
     * 获取当前动态权重
     */
    public function getCurrentWeights() {
        $current = [];
        foreach ($this->baseWeights as $item => $weight) {
            $current[$item] = $weight * $this->dynamicFactors[$item];
        }
        return $current;
    }
    
    /**
     * 基于动态权重的选择
     */
    public function select() {
        $currentWeights = $this->getCurrentWeights();
        return WeightedRandom::linearSelect($currentWeights);
    }
}

总结

加权随机算法是概率控制的重要工具，具有以下特点：

核心优势

  1. 精确控制概率：严格按照权重分配选择概率
  2. 灵活配置：支持动态调整权重
  3. 性能可控：多种实现满足不同性能需求
  4. 应用广泛：适用于游戏、推荐、抽奖等场景

选择建议

  • 小规模数据：使用线性扫描，简单直观
  • 大规模数据：使用二分查找，性能均衡
  • 超频繁抽样：使用别名方法，极致性能

加权随机算法让概率控制变得简单而精确，是每个开发者都应该掌握的重要算法工具。

文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/weighted-random.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 算法 加权随机算法
赏
评 论
 上一篇
Fisher-Yates 洗牌算法
Fisher-Yates 洗牌算法
Fisher-Yates 洗牌算法（也称为 Knuth 洗牌）是一种高效且公正的随机洗牌算法，用于将数组或列表中的元素随机重新排列。 🎯 算法原理核心思想：从后往前遍历数组，将当前元素与随机位置的一个元素交换。 📝 算法步骤原始版本：1
2025-11-20 算法
PHP 算法 Fisher-Yates
下一篇 
蓄水池抽样算法：从大数据流中随机取样的优雅解决方案
蓄水池抽样算法：从大数据流中随机取样的优雅解决方案
如何在未知总量的数据流中公平地随机抽取样本？蓄水池抽样算法给出了完美的答案。 问题背景在大数据时代，我们经常面临这样的挑战：需要从一个规模未知或极大的数据集中随机抽取少量样本。比如： 从数十GB的日志文件中随机选取1万条记录进行分析
2025-11-20 算法
PHP 算法 蓄水池抽样算法
PHP 算法 加权随机算法
算法
发布日期:   2025-11-20
文章字数:   1.8k
阅读时长:   8 分

如何让稀有物品掉落率低、普通物品掉落率高？加权随机算法提供了完美的概率控制方案。

问题背景

在很多应用场景中，我们需要按照预设的概率分布来进行随机选择，而不是简单的均匀随机：

  • 游戏开发：稀有装备1%概率，普通装备50%概率
  • 推荐系统：热门商品推荐概率高，冷门商品概率低
  • 负载均衡：高性能服务器分配更多请求
  • 广告投放：高价值广告展示频率更高
  • 抽奖活动：一等奖概率0.1%，参与奖概率90%

简单随机选择无法满足这些需求，而加权随机(Weighted Random) 算法提供了完美的解决方案。

算法原理

加权随机核心思想是：根据权重构建概率区间，随机数落在哪个区间就选择对应的元素。

基本概念

假设我们有三个物品和对应的权重：

1
2
3
物品A: 权重 5
物品B: 权重 3  
物品C: 权重 2

总权重 = 5 + 3 + 2 = 10

每个物品的概率分布：

1
2
3
物品A: 5/10 = 50%
物品B: 3/10 = 30%
物品C: 2/10 = 20%

实现方法

方法一：线性扫描（简单直观）

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
<?php

class WeightedRandom {
    
    /**
     * 线性扫描实现加权随机
     * 
     * @param array $items 格式：['物品A' => 权重, '物品B' => 权重, ...]
     * @return mixed 随机选中的物品
     */
    public static function linearSelect($items) {
        // 计算总权重
        $totalWeight = array_sum($items);
        
        // 生成随机数
        $random = mt_rand(1, $totalWeight);
        
        // 线性扫描找到对应的物品
        $current = 0;
        foreach ($items as $item => $weight) {
            $current += $weight;
            if ($random <= $current) {
                return $item;
            }
        }
        
        return null; // 理论上不会执行到这里
    }
}

// 使用示例：游戏物品掉落
$lootTable = [
    '普通药水' => 50,   // 50% 概率
    '稀有装备' => 30,   // 30% 概率  
    '传奇武器' => 15,   // 15% 概率
    '神器'     => 5     // 5% 概率
];

echo "=== 游戏物品掉落模拟 ===\n";
for ($i = 0; $i < 10; $i++) {
    $loot = WeightedRandom::linearSelect($lootTable);
    echo "第 " . ($i + 1) . " 次掉落: " . $loot . "\n";
}

?>

方法二：别名方法（高效算法）

对于需要频繁抽样的大规模场景，可以使用更高效的别名方法：

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
<?php

class AliasMethod {
    private $prob;
    private $alias;
    private $n;
    
    /**
     * 初始化别名表
     * 
     * @param array $weights 权重数组
     */
    public function __construct($weights) {
        $this->n = count($weights);
        $this->prob = array_fill(0, $this->n, 0);
        $this->alias = array_fill(0, $this->n, 0);
        
        $this->buildAliasTable($weights);
    }
    
    /**
     * 构建别名表
     */
    private function buildAliasTable($weights) {
        $total = array_sum($weights);
        $prob = array_map(function($w) use ($total) {
            return $w * $this->n / $total;
        }, $weights);
        
        $small = [];
        $large = [];
        
        // 分类
        for ($i = 0; $i < $this->n; $i++) {
            if ($prob[$i] < 1) {
                $small[] = $i;
            } else {
                $large[] = $i;
            }
        }
        
        // 构建别名表
        while (!empty($small) && !empty($large)) {
            $s = array_pop($small);
            $l = array_pop($large);
            
            $this->prob[$s] = $prob[$s];
            $this->alias[$s] = $l;
            
            $prob[$l] = ($prob[$l] + $prob[$s]) - 1;
            
            if ($prob[$l] < 1) {
                $small[] = $l;
            } else {
                $large[] = $l;
            }
        }
        
        // 处理剩余项
        while (!empty($large)) {
            $l = array_pop($large);
            $this->prob[$l] = 1;
        }
        
        while (!empty($small)) {
            $s = array_pop($small);
            $this->prob[$s] = 1;
        }
    }
    
    /**
     * 生成随机选择
     */
    public function next() {
        $i = mt_rand(0, $this->n - 1);
        if (mt_rand() / mt_getrandmax() < $this->prob[$i]) {
            return $i;
        } else {
            return $this->alias[$i];
        }
    }
}

// 使用别名方法的加权随机类
class EfficientWeightedRandom {
    
    /**
     * 使用别名方法实现高效加权随机
     */
    public static function aliasSelect($items) {
        static $aliasMethods = [];
        
        $key = md5(serialize($items));
        if (!isset($aliasMethods[$key])) {
            $aliasMethods[$key] = new AliasMethod(array_values($items));
        }
        
        $index = $aliasMethods[$key]->next();
        $itemNames = array_keys($items);
        return $itemNames[$index];
    }
}

?>

方法三：二分查找（性能均衡）

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
<?php

class BinarySearchWeightedRandom {
    private $prefixSums;
    private $items;
    private $totalWeight;
    
    /**
     * 预处理前缀和数组
     */
    public function __construct($items) {
        $this->items = array_keys($items);
        $this->totalWeight = array_sum($items);
        
        // 构建前缀和数组
        $this->prefixSums = [];
        $sum = 0;
        foreach ($items as $weight) {
            $sum += $weight;
            $this->prefixSums[] = $sum;
        }
    }
    
    /**
     * 二分查找实现快速选择
     */
    public function select() {
        $target = mt_rand(1, $this->totalWeight);
        
        // 二分查找
        $left = 0;
        $right = count($this->prefixSums) - 1;
        
        while ($left < $right) {
            $mid = $left + intval(($right - $left) / 2);
            
            if ($this->prefixSums[$mid] < $target) {
                $left = $mid + 1;
            } else {
                $right = $mid;
            }
        }
        
        return $this->items[$left];
    }
}

?>

完整应用示例

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
<?php

// 完整的加权随机应用示例
class WeightedRandomApplication {
    
    /**
     * 游戏掉落系统
     */
    public static function gameLootSystem() {
        echo "=== 游戏掉落系统 ===\n";
        
        $monsterLootTable = [
            '金币' => 400,
            '普通装备' => 300,
            '稀有装备' => 200,
            '史诗装备' => 80,
            '传奇装备' => 18,
            '神器' => 2
        ];
        
        // 模拟击杀怪物掉落
        $drops = [];
        for ($i = 0; $i < 1000; $i++) {
            $loot = WeightedRandom::linearSelect($monsterLootTable);
            if (!isset($drops[$loot])) {
                $drops[$loot] = 0;
            }
            $drops[$loot]++;
        }
        
        // 统计结果
        echo "1000次击杀掉落统计:\n";
        foreach ($drops as $item => $count) {
            $rate = ($count / 1000) * 100;
            $expected = ($monsterLootTable[$item] / array_sum($monsterLootTable)) * 100;
            echo sprintf("%-10s: 实际%.2f%% (预期%.2f%%)\n", 
                $item, $rate, $expected);
        }
    }
    
    /**
     * 推荐系统
     */
    public static function recommendationSystem() {
        echo "\n=== 商品推荐系统 ===\n";
        
        $products = [
            '热门商品A' => 100,
            '热门商品B' => 80,
            '普通商品C' => 30,
            '普通商品D' => 25,
            '冷门商品E' => 10,
            '新品F' => 5
        ];
        
        echo "今日推荐商品:\n";
        for ($i = 0; $i < 5; $i++) {
            $recommended = WeightedRandom::linearSelect($products);
            echo "推荐位 " . ($i + 1) . ": " . $recommended . "\n";
        }
    }
    
    /**
     * 抽奖活动
     */
    public static function lotterySystem() {
        echo "\n=== 抽奖活动系统 ===\n";
        
        $prizes = [
            '一等奖：iPhone' => 1,
            '二等奖：AirPods' => 5, 
            '三等奖：优惠券' => 50,
            '参与奖：谢谢参与' => 944
        ];
        
        echo "抽奖结果:\n";
        $results = [];
        for ($i = 0; $i < 100; $i++) {
            $prize = WeightedRandom::linearSelect($prizes);
            if (!isset($results[$prize])) {
                $results[$prize] = 0;
            }
            $results[$prize]++;
        }
        
        foreach ($results as $prize => $count) {
            echo $prize . ": " . $count . "次\n";
        }
    }
    
    /**
     * 性能测试
     */
    public static function performanceTest() {
        echo "\n=== 性能测试 ===\n";
        
        // 大规模权重表
        $largeWeightTable = [];
        for ($i = 0; $i < 1000; $i++) {
            $largeWeightTable["item_$i"] = mt_rand(1, 100);
        }
        
        // 线性扫描性能
        $start = microtime(true);
        for ($i = 0; $i < 10000; $i++) {
            WeightedRandom::linearSelect($largeWeightTable);
        }
        $linearTime = microtime(true) - $start;
        
        // 二分查找性能
        $bsRandom = new BinarySearchWeightedRandom($largeWeightTable);
        $start = microtime(true);
        for ($i = 0; $i < 10000; $i++) {
            $bsRandom->select();
        }
        $binaryTime = microtime(true) - $start;
        
        echo "线性扫描: " . number_format($linearTime, 4) . " 秒\n";
        echo "二分查找: " . number_format($binaryTime, 4) . " 秒\n";
        echo "性能提升: " . number_format(($linearTime - $binaryTime) / $linearTime * 100, 2) . "%\n";
    }
}

// 运行所有示例
WeightedRandomApplication::gameLootSystem();
WeightedRandomApplication::recommendationSystem();
WeightedRandomApplication::lotterySystem();
WeightedRandomApplication::performanceTest();

?>

算法对比

方法 时间复杂度 空间复杂度 适用场景
线性扫描 O(n) O(1) 权重项少，简单应用
二分查找 O(log n) O(n) 权重项多，性能要求高
别名方法 O(1) O(n) 超大规模，频繁抽样

最佳实践建议

1. 权重设计原则

1
2
3
4
5
6
7
8
9
10
11
12
13
// 好的权重设计
$goodWeights = [
    '常见物品' => 70,   // 70%
    '稀有物品' => 25,   // 25%  
    '史诗物品' => 4,    // 4%
    '传说物品' => 1     // 1%
];

// 避免的权重设计
$badWeights = [
    '物品A' => 0.0001,  // 概率过小，可能永远选不到
    '物品B' => 999999,  // 权重差异过大
];

2. 动态权重调整

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
class DynamicWeightedRandom {
    private $baseWeights;
    private $dynamicFactors;
    
    public function __construct($baseWeights) {
        $this->baseWeights = $baseWeights;
        $this->dynamicFactors = array_fill_keys(array_keys($baseWeights), 1);
    }
    
    /**
     * 根据用户行为动态调整权重
     */
    public function adjustWeight($item, $factor) {
        if (isset($this->dynamicFactors[$item])) {
            $this->dynamicFactors[$item] *= $factor;
        }
    }
    
    /**
     * 获取当前动态权重
     */
    public function getCurrentWeights() {
        $current = [];
        foreach ($this->baseWeights as $item => $weight) {
            $current[$item] = $weight * $this->dynamicFactors[$item];
        }
        return $current;
    }
    
    /**
     * 基于动态权重的选择
     */
    public function select() {
        $currentWeights = $this->getCurrentWeights();
        return WeightedRandom::linearSelect($currentWeights);
    }
}

总结

加权随机算法是概率控制的重要工具，具有以下特点：

核心优势

  1. 精确控制概率：严格按照权重分配选择概率
  2. 灵活配置：支持动态调整权重
  3. 性能可控：多种实现满足不同性能需求
  4. 应用广泛：适用于游戏、推荐、抽奖等场景

选择建议

  • 小规模数据：使用线性扫描，简单直观
  • 大规模数据：使用二分查找，性能均衡
  • 超频繁抽样：使用别名方法，极致性能

加权随机算法让概率控制变得简单而精确，是每个开发者都应该掌握的重要算法工具。

文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/weighted-random.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 算法 加权随机算法
赏
评 论
 上一篇
Fisher-Yates 洗牌算法
Fisher-Yates 洗牌算法
Fisher-Yates 洗牌算法（也称为 Knuth 洗牌）是一种高效且公正的随机洗牌算法，用于将数组或列表中的元素随机重新排列。 🎯 算法原理核心思想：从后往前遍历数组，将当前元素与随机位置的一个元素交换。 📝 算法步骤原始版本：1
2025-11-20 算法
PHP 算法 Fisher-Yates
下一篇 
蓄水池抽样算法：从大数据流中随机取样的优雅解决方案
蓄水池抽样算法：从大数据流中随机取样的优雅解决方案
如何在未知总量的数据流中公平地随机抽取样本？蓄水池抽样算法给出了完美的答案。 问题背景在大数据时代，我们经常面临这样的挑战：需要从一个规模未知或极大的数据集中随机抽取少量样本。比如： 从数十GB的日志文件中随机选取1万条记录进行分析
2025-11-20 算法
PHP 算法 蓄水池抽样算法
  目录
  目录
  目录
hexo