C++如何从数组中按照指定非归一化概率随机抽取元素

方案1：使用C++标准库自带的离散分布（推荐） #

直接用<random>头文件中的std::discrete_distribution，它天生支持按给定的非负权重序列生成对应下标的随机数，不需要手动处理权重归一化，内部已经实现了加权逻辑。
示例代码：

#include <vector>
#include <random>
#include "Point.h" // 替换为你自己的Point类型定义头文件

// 假设p和chances已经是等长的有效向量，chances元素均为非负，且不全为0
int main() {
    std::vector<Point> p = ...; // 你的Point数组
    std::vector<double> chances = ...; // 对应的权重数组

    std::random_device rd;
    std::mt19937 gen(rd());
    // 直接用chances构造离散分布，自动处理权重不归一的情况
    std::discrete_distribution<> dist(chances.begin(), chances.end());
    // 生成加权随机下标，采样对应元素
    Point sampled_point = p[dist(gen)];
    return 0;
}

优势：

• 不需要手动计算权重总和、前缀和，标准库实现经过优化，正确性和性能都有保障
• 替换了旧的rand()实现，避免了rand()本身的分布不均匀、模运算偏差问题
• 自动适配权重总和不为1的场景，不需要额外做归一化计算

方案2：手动实现前缀和二分查找（适合需要自定义逻辑的场景） #

实现原理：

1. 先计算chances的前缀和数组，得到所有权重的总和total
2. 生成一个[0, total)区间内的均匀随机数r
3. 找到第一个前缀和大于r的下标，即为要采样的元素下标
   示例代码：

#include <vector>
#include <random>
#include <algorithm> // 用于二分查找接口upper_bound
#include "Point.h"

int main() {
    std::vector<Point> p = ...;
    std::vector<double> chances = ...;

    // 计算前缀和数组
    std::vector<double> prefix_sum(chances.size());
    prefix_sum[0] = chances[0];
    for (int i = 1; i < chances.size(); ++i) {
        prefix_sum[i] = prefix_sum[i-1] + chances[i];
    }
    double total = prefix_sum.back();

    // 生成[0, total)区间的均匀随机数
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_real_distribution<double> dist(0.0, total);
    double r = dist(gen);

    // 二分查找得到对应下标
    int idx = std::upper_bound(prefix_sum.begin(), prefix_sum.end(), r) - prefix_sum.begin();
    Point sampled_point = p[idx];
    return 0;
}

注意事项：

• 需确保chances所有元素都是非负的，且总和不能为0，否则会出现未定义行为
• 如果需要多次采样同一份权重序列，可以把前缀和缓存起来，避免重复计算，性能更高

内容的提问来源于stack exchange，提问作者Michael