C++如何实现带权重的随机抽取算法？累加概率与二分查找两种方式详解

抽奖系统里抽到SSR的概率只有1%，抽到普通道具的概率是79%，这种“不同物品不同概率”的随机抽取，本质上就是带权重的随机选择问题。最朴素的办法是造一个大数组，把SSR放1个、普通道具放79个，然后随机取一个下标。但如果权重是100万比1呢？这种做法的内存开销就无法接受了。本文介绍两种在C++中高效且工程上常用的方案：累加概率法和前缀和加二分查找法，并给出完整源码。

方案一：累加概率法，把权重映射到数轴区间

累加概率法的核心思想非常直观。假设有三个物品A、B、C，权重分别是1、2、7，总权重是10。我们把一段长度为10的数轴按权重切成三段：A占据[0, 1)，B占据[1, 3)，C占据[3, 10)。接下来生成一个[0, 10)范围内的随机数，看它落在哪个区间，就抽中哪个物品。由于随机数在数轴上是均匀分布的，落在某段区间的概率就严格等于该段长度占总长度的比例，也就是权重占比。

实现时只需要一次线性扫描：用一个变量累加权重，当随机数小于当前累加值时，说明落在了当前物品的区间内。下面是完整代码：

#include <iostream>
#include <vector>
#include <random>
#include <string>

// 简单物品结构
struct Item {
    std::string name;
    int weight;
};

// 累加概率法：返回被抽中物品的下标
int weightedRandom(const std::vector<Item>& items, std::mt19937& rng) {
    // 先算总权重
    long long total = 0;
    for (const auto& item : items) {
        total += item.weight;
    }
    // 生成 [0, total) 范围的随机整数
    std::uniform_int_distribution<long long> dist(0, total - 1);
    long long r = dist(rng);

    // 线性扫描找区间
    long long acc = 0;
    for (size_t i = 0; i < items.size(); ++i) {
        acc += items[i].weight;
        if (r < acc) {
            return static_cast<int>(i);
        }
    }
    return static_cast<int>(items.size() - 1); // 兜底，理论上走不到这里
}

int main() {
    std::vector<Item> items = {
        {"SSR卡", 1},
        {"SR卡", 9},
        {"R卡", 30},
        {"普通道具", 60}
    };

    std::random_device rd;
    std::mt19937 rng(rd());

    // 统计一万次抽取的分布，验证概率
    int count[4] = {0};
    for (int i = 0; i < 10000; ++i) {
        count[weightedRandom(items, rng)]++;
    }

    for (size_t i = 0; i < items.size(); ++i) {
        std::cout << items[i].name << " 被抽中 "
                  << count[i] << " 次" << std::endl;
    }
    return 0;
}

这段代码里有一个细节值得注意：随机数用的是std::mt19937引擎配合std::uniform_int_distribution，而不是老的rand()和rand() % total。原因有两点：一是rand()的范围通常只有32767，当总权重超过这个值时取模会产生严重的分布偏差；二是取模运算本身会破坏均匀性，这在加权随机的场景下会被放大成概率失真。

累加概率法的优点是实现简单，不需要额外内存，适合物品数量不多、权重偶尔变化的场合。缺点也明显：每次抽取都是O(n)的线性扫描，如果物品有几十万个，每次抽奖都要扫一遍，性能会成为瓶颈。

方案二：前缀和加二分查找，让抽取变成O(log n)

当抽取次数很多、物品列表固定时，更优的做法是预先构建前缀和数组。前缀和数组的第i个元素等于前i+1个权重之和，它天然就是有序的，因此可以用二分查找替代线性扫描：拿到随机数r后，找到第一个大于等于r的前缀和位置，该位置对应的物品就是抽中结果。

标准库里已经提供了现成的二分查找函数std::lower_bound，它返回第一个不小于目标值的迭代器，正好符合我们的需求。这样一来，构建前缀和是一次O(n)的开销，之后每次抽取只需O(log n)，对于高频抽奖的系统来说提升巨大。

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <string>

class WeightedPicker {
public:
    WeightedPicker(const std::vector<int>& weights)
        : weights_(weights), total_(0) {
        prefix_.reserve(weights.size());
        long long sum = 0;
        for (int w : weights) {
            sum += w;
            prefix_.push_back(sum);
        }
        total_ = sum;
    }

    // 二分查找抽取，返回物品下标
    int pick(std::mt19937& rng) const {
        std::uniform_int_distribution<long long> dist(1, total_);
        long long r = dist(rng); // 随机数范围取 [1, total]
        // 找第一个前缀和 >= r 的位置
        auto it = std::lower_bound(prefix_.begin(), prefix_.end(), r);
        return static_cast<int>(it - prefix_.begin());
    }

private:
    std::vector<int> weights_;
    std::vector<long long> prefix_; // 前缀和数组，天然有序
    long long total_;
};

int main() {
    std::vector<std::string> names = {"SSR卡", "SR卡", "R卡", "普通道具"};
    std::vector<int> weights = {1, 9, 30, 60};

    WeightedPicker picker(weights);
    std::random_device rd;
    std::mt19937 rng(rd());

    int count[4] = {0};
    for (int i = 0; i < 100000; ++i) {
        count[picker.pick(rng)]++;
    }

    for (size_t i = 0; i < names.size(); ++i) {
        std::cout << names[i] << ": " << count[i] / 1000.0 << "%" << std::endl;
    }
    return 0;
}

注意这里随机数的范围取的是[1, total]而不是[0, total)。因为前缀和数组的最小值至少是第一个权重（权重为正时至少是1），如果随机数取0，lower_bound可能找不到合理落点或造成边界混乱。用[1, total]配合“找第一个大于等于r的前缀和”的语义，边界处理会非常干净。

这种方案适合权重列表构建一次、抽取无数次的场景，比如配置表加载后初始化抽奖池。如果权重频繁变动（比如动态增删物品），每次变动都要重建前缀和，这时可以考虑更高级的数据结构，比如用std::multiset维护或线段树支持动态更新，不过对绝大多数业务来说重建前缀和已经足够快了。

浮点数权重的精度陷阱与工程细节

有些需求方给的权重是小数，比如0.5、0.35这种，直接用浮点数累加会有精度问题。典型表现是所有物品的概率加起来明明是1.0，但浮点累加的最后可能差出一个微小误差，导致随机数落在所有区间之外，返回了兜底值。稳妥的做法有两种：一是把小数权重统一放大成整数，比如0.5、0.35乘以1000变成500和350，用整数运算彻底规避精度问题；二是如果必须用浮点，抽取时把随机数范围的上限设为累加后的实际总和，而不是理论值1.0，同时保留兜底逻辑。

另一个容易被忽视的细节是权重为0的物品。无论用哪种方案，权重为0意味着该物品的区间长度为0，理论上永远不会被抽中，这在数学上是成立的。但代码里最好显式过滤掉权重小于等于0的项，一是让意图更清晰，二是避免总权重为0时uniform_int_distribution收到非法区间导致未定义行为。当所有权重之和为0时，应当直接报错或走默认分支，而不是让随机分布崩掉。

最后说说性能层面的取舍。两种方案的对比可以简单归纳为一张表：

实际项目中如果抽奖池只有几十个物品，两种方案的性能差异几乎测不出来，选哪种看代码风格偏好即可。但如果抽奖池上千、QPS又高，二分方案的优势就非常明显了。此外，如果需要“不放回抽取”（抽中的物品从池子里移除），可以在抽中后把该物品权重置0再重建前缀和，或者用洗牌算法对权重区间做调整，思路是一致的。

总结一下，加权随机抽取的核心就是把权重转换为区间长度，再让均匀分布的随机数去“撞”区间。理解了这个本质，无论是C++、Java还是Python，实现方式都是相通的，只是标准库函数的差异而已。

C++随机抽取权重算法二分查找修改时间：2026-09-14 02:07:00