抽獎系統核心需求:依設定機率抽取獎項。本文實作「權重陣列洗牌法」,支援動態機率配置、數學期望精確、效能優於輪盤法,附帶大規模優化方案。
<?php
/**
* 依機率抽取獎項
* @param array $prizes ['prize_key' => probability_percent, ...] 機率總和應為 100
* @param int $poolSize 權重池大小(越大越精確,建議 10000)
* @return string 中獎獎項鍵值
*/
function drawPrize(array $prizes, int $poolSize = 10000): string {
// 1. 驗證機率總和
$totalProb = array_sum($prizes);
if (abs($totalProb - 100) > 0.001) {
throw new InvalidArgumentException("機率總和必須為 100,目前為 $totalProb");
}
// 2. 建立權重池
$pool = [];
foreach ($prizes as $key => $prob) {
$count = (int)round($poolSize * $prob / 100);
$pool = array_merge($pool, array_fill(0, $count, $key));
}
// 3. 修正池大小(四捨五入誤差)
$diff = $poolSize - count($pool);
if ($diff > 0) {
$pool = array_merge($pool, array_fill(0, $diff, array_key_first($prizes)));
} elseif ($diff < 0) {
$pool = array_slice($pool, 0, $poolSize);
}
// 4. 洗牌並取第一個
shuffle($pool);
return $pool[array_rand($pool)];
}
// 使用範例
$prizes = [
'first' => 0.12, // 一等獎 0.12%
'second' => 3.00, // 二等獎 3%
'third' => 12.00, // 三等獎 12%
'none' => 84.88, // 謝謝惠顧
];
echo '中獎結果: ' . drawPrize($prizes);
| 指標 | 權重池洗牌法 | 輪盤法 (累積機率) | 二分搜尋輪盤法 |
|---|---|---|---|
| 時間複雜度 | O(N) 建池 + O(N) 洗牌 | O(N) 累積 + O(N) 線性搜尋 | O(N) 累積 + O(log N) 搜尋 |
| 空間複雜度 | O(PoolSize) | O(N) | O(N) |
| 精確度 | 取決於 PoolSize | 浮點數精度 | 浮點數精度 |
| 適合獎項數 | 少量(<20) | 任意 | 大量(>100) |
<?php
$luaScript = <<<'LUA'
local prizes = cjson.decode(ARGV[1])
local poolSize = tonumber(ARGV[2])
local pool = {}
for k, v in pairs(prizes) do
local cnt = math.floor(poolSize * v / 100)
for i = 1, cnt do table.insert(pool, k) end
end
math.randomseed(tonumber(ARGV[3]))
local idx = math.random(#pool)
return pool[idx]
LUA;
$redis->eval($luaScript, 0, json_encode($prizes), 10000, microtime(true) * 1000000);
<?php
// 初始化:生成 100 萬筆獎池存入 Redis List
function initPrizePool(array $prizes, int $total = 1000000) {
$pool = [];
foreach ($prizes as $key => $prob) {
$count = (int)round($total * $prob / 100);
$pool = array_merge($pool, array_fill(0, $count, $key));
}
shuffle($pool);
// 批次寫入 Redis
$redis->del('prize:pool');
foreach (array_chunk($pool, 10000) as $chunk) {
$redis->rPush('prize:pool', ...$chunk);
}
}
// 抽獎:原子 RPOP
$prize = $redis->rPop('prize:pool');
if ($prize === false) {
// 獎池耗盡,重新初始化或降級
}
<?php
function verifyDistribution(array $prizes, int $trials = 1000000): array {
$counts = array_fill_keys(array_keys($prizes), 0);
for ($i = 0; $i < $trials; $i++) {
$counts[drawPrize($prizes)]++;
}
$result = [];
foreach ($prizes as $k => $expected) {
$actual = $counts[$k] / $trials * 100;
$result[$k] = ['expected' => $expected, 'actual' => round($actual, 4), 'diff' => round($actual - $expected, 4)];
}
return $result;
}
// 執行驗證
print_r(verifyDistribution($prizes, 100000));