萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 可配置中獎機率抽獎演算法:權重陣列洗牌法與效能分析

抽獎系統核心需求:依設定機率抽取獎項。本文實作「權重陣列洗牌法」,支援動態機率配置、數學期望精確、效能優於輪盤法,附帶大規模優化方案。

核心演算法:建立權重池 → 洗牌 → 隨機取一

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

大規模/高併發優化方案

方案一:Redis Lua 腳本(原子性、高效能)

<?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);

方案二:預生成獎池 + 原子 POP(極高併發)

<?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));

安全性補充

  • 防重放:每次抽獎消耗 Token/Session,防止重複提交
  • 防偽造:前端不直接呼叫抽獎 API,改為「請求抽獎資格 → 後端驗證 → 返回結果」
  • 日誌審計:記錄 user_id、prize、timestamp、ip、user_agent,定期核對分佈
  • 大獎二次確認:一二等獎需人工複核或簡訊驗證
copyright © 萬盛學電腦網 all rights reserved