活動運營中常需按權重隨機抽取:抽獎(大獎概率低)、廣告位輪播(高收益廣告展示多)、負載均衡(高配機器分流多)。本文對比兩種經典算法,給出生產級實現與配置範例。
/**
* 擴展數組法:按權重展開數組,隨機取下標
* 優點:O(1) 取值,極快
* 缺點:權重精度高/項目多時內存佔用大
* @param array $probs ['獎項Key' => 權重值]
* @return string 中獎 Key
*/
function random_v1(array $probs): string
{
static $cache = [];
$key = md5(serialize($probs));
if (!isset($cache[$key])) {
$max = array_sum($probs);
$pool = [];
foreach ($probs as $k => $v) {
// 權重歸一化到 10000 精度
$count = (int)($v / $max * 10000);
$pool = array_merge($pool, array_fill(0, $count, $k));
}
$cache[$key] = $pool;
}
return $cache[$key][mt_rand(0, count($cache[$key]) - 1)];
}
/**
* 累積概率法:單次遍歷,無額外內存
* 優點:內存 O(1),支援任意精度權重
* 缺點:每次 O(n) 遍歷,n 較大時稍慢
* @param array $probs ['獎項Key' => 權重值]
* @return string 中獎 Key
*/
function random_v2(array $probs): string
{
$sum = array_sum($probs);
$rand = mt_rand(1, $sum); // 1 到總權重
foreach ($probs as $k => $v) {
if ($rand <= $v) {
return $k;
}
$rand -= $v;
}
// 理論不可達,兜底返回最後一項
return array_key_last($probs);
}
| 維度 | 擴展數組法 | 累積概率法 |
|---|---|---|
| 時間複雜度 | 初始化 O(N×W),查詢 O(1) | 查詢 O(N) |
| 空間複雜度 | O(N×W) (W=精度基數) | O(1) |
| 權重精度 | 受限於基數 (示例 10000) | 無限制 (整數/浮點均可) |
| 適合場景 | 高頻調用、項目少、權重固定 | 項目多、權重動態、內存敏感 |
推薦:累積概率法 (v2),通用性更強,現代 CPU 單次微秒級遍歷完全可接受。
$prizes = [
1 => ['id' => 1, 'name' => 'iPhone 15 Pro', 'weight' => 1, 'stock' => 5, 'level' => 1],
2 => ['id' => 2, 'name' => 'Dyson 吹風機', 'weight' => 5, 'stock' => 20, 'level' => 2],
3 => ['id' => 3, 'name' => '索尼耳機', 'weight' => 10, 'stock' => 50, 'level' => 3],
4 => ['id' => 4, 'name' => '64G U盤', 'weight' => 20, 'stock' => 200,'level' => 4],
5 => ['id' => 5, 'name' => '10 元話費券', 'weight' => 100, 'stock' => 1000,'level' => 5],
6 => ['id' => 6, 'name' => '謝謝參與', 'weight' => 864, 'stock' => 999999,'level' => 6],
];
// 總權重 = 1000,一等獎中獎率 0.1%
class LotteryService
{
private array $prizes;
private Redis $redis; // 庫存扣減用 Redis 原子操作
private string $stockPrefix = 'lottery:stock:';
public function __construct(array $prizes, Redis $redis)
{
$this->prizes = $prizes;
$this->redis = $redis;
// 初始化庫存
foreach ($prizes as $p) {
$this->redis->set($this->stockPrefix . $p['id'], $p['stock']);
}
}
public function draw(int $userId): array
{
// 1. 構建當前可用獎池 (庫存>0)
$pool = [];
foreach ($this->prizes as $p) {
$stock = (int)$this->redis->get($this->stockPrefix . $p['id']);
if ($stock > 0) {
$pool[$p['id']] = $p['weight'];
}
}
if (empty($pool)) return ['code' => 0, 'msg' => '獎品已抽完'];
// 2. 概率抽取
$winId = $this->weightedRandom($pool);
$prize = $this->prizes[$winId];
// 3. 原子扣減庫存 (Lua 腳本保證原子性)
$lua = "
local key = KEYS[1]
local stock = tonumber(redis.call('GET', key))
if stock > 0 then
redis.call('DECR', key)
return 1
else
return 0
end
";
$script = $this->redis->eval($lua, 1, $this->stockPrefix . $winId);
if (!$script) {
// 併發衝突導致扣減失敗,重試或降級
return $this->draw($userId); // 簡單遞歸重試,生產環境加限流
}
// 4. 記錄中獎日誌 (異步寫入 MySQL/ES)
$this->logWin($userId, $prize);
return ['code' => 1, 'prize' => $prize];
}
private function weightedRandom(array $pool): int
{
$sum = array_sum($pool);
$rand = mt_rand(1, $sum);
foreach ($pool as $k => $v) {
if ($rand <= $v) return $k;
$rand -= $v;
}
return array_key_last($pool);
}
private function logWin(int $userId, array $prize): void
{
// 推送到 Kafka/Redis Stream,消費者異步落庫
$log = ['uid' => $userId, 'pid' => $prize['id'], 'time' => time()];
$this->redis->rpush('lottery:win_log', json_encode($log));
}
}
<?php
// api/draw.php
header('Content-Type: application/json');
require 'LotteryService.php';
$redis = new Redis();
$redis->connect('127.0.0.1', 6379);
$service = new LotteryService($prizes, $redis);
// 簡單防刷:用戶每天限抽 3 次
$userId = (int)($_POST['uid'] ?? 0);
$todayKey = "lottery:user_limit:$userId:" . date('Ymd');
$count = $redis->incr($todayKey);
if ($count === 1) $redis->expire($todayKey, 86400);
if ($count > 3) exit(json_encode(['code' => -1, 'msg' => '今日次數已用完']));
$result = $service->draw($userId);
echo json_encode($result);
文中提到的「概率設為 0」是極端作弊。正規運營中,大獎概率極低 (如 0.01%) 且庫存極少 (如 1 個),數學期望下絕大多數用戶確實抽不到。**這是概率分佈的必然特性,而非程序作弊**。
透明化建議:公開獎品列表、總庫存、中獎概率、歷史中獎記錄 (脫敏),接受社會監督。
累積概率法 (v2) 是通用加權隨機的最佳選擇:代碼簡潔、內存常數、精度無損。結合 Redis 原子扣減庫存、異步日誌、前端動畫解耦,可構建高併發、可審計、體驗良好的抽獎系統。核心原理同樣適用於廣告輪播、流量分流、推薦採樣等場景。