萬盛學電腦網

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

PHP 概率算法實戰:抽獎、隨機廣告、加權隨機的高效實現

核心需求

活動運營中常需按權重隨機抽取:抽獎(大獎概率低)、廣告位輪播(高收益廣告展示多)、負載均衡(高配機器分流多)。本文對比兩種經典算法,給出生產級實現與配置範例。

算法一:擴展數組法 (空間換時間)

/**
 * 擴展數組法:按權重展開數組,隨機取下標
 * 優點: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 單次微秒級遍歷完全可接受。

完整抽獎系統實現

1. 獎品配置結構

$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%

2. 庫存感知抽獎服務

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

3. API 接口示例

<?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 原子扣減庫存、異步日誌、前端動畫解耦,可構建高併發、可審計、體驗良好的抽獎系統。核心原理同樣適用於廣告輪播、流量分流、推薦採樣等場景。

copyright © 萬盛學電腦網 all rights reserved