寻求更高效的C++带权随机数生成方案——现有实现性能对比

项目中需频繁生成大量带权随机数，当前测试生成1亿个取值为{0,1,2,3}、对应权重{0.1,0.2,0.3,0.4}的随机数时，Release构建下两种方案耗时如下：

• 方案(i)：使用random()与srand()，耗时约1.3秒
• 方案(ii)：使用C++ random库，耗时约4秒

该模块已成为程序性能瓶颈，且实际场景中每次生成随机数时权重weights均不同，无法将std::discrete_distribution移出循环，寻求更高效的带权随机数生成方法。

现有方案实现代码 #

方案(i)：使用random()与srand() #

vector<int> res;
res.resize(100000000);
vector<double> weights{0.1, 0.2, 0.3, 0.4};

srand((unsigned int)time(NULL));
for (int i = 0; i < 100000000; ++i) {

    double tempSum = 0;
    double randomNnm = (double)(random()/(double)RAND_MAX);

    for(int j = 0;j < weights.size(); j++) {
        tempSum += weights[j];
        if(randomNnm <= tempSum) {
            res[i] = j;
            break;
        }
    }
}

方案(ii)：使用C++ random库 #

vector<int> res;
res.resize(100000000);
vector<double> weights{0.1, 0.2, 0.3, 0.4};

for (int i = 0; i < 100000000; ++i) {
    unsigned seed = chrono::system_clock::now().time_since_epoch().count();
    default_random_engine randGen(seed);
    discrete_distribution<int> thisDistribution(weights.begin(), weights.end());
    res[i] = thisDistribution(randGen); // get the final value
}

优化建议与实现 #

1. 消除随机数引擎重复初始化开销 #

方案(ii)的核心性能瓶颈是每次循环都重新初始化随机数引擎，这一操作的开销远大于生成随机数本身。即使权重每次变化，引擎只需初始化一次，循环内复用即可：

vector<int> res;
res.resize(100000000);
vector<double> weights{0.1, 0.2, 0.3, 0.4};

// 引擎仅初始化一次
std::mt19937 rand_gen(std::chrono::system_clock::now().time_since_epoch().count());

for (int i = 0; i < 100000000; ++i) {
    // 仅根据当前权重重新创建分布
    std::discrete_distribution<int> dist(weights.begin(), weights.end());
    res[i] = dist(rand_gen);
}

修改后方案(ii)的耗时会大幅降低，接近甚至超过方案(i)的性能。

2. 用整数运算替代浮点运算（性能最优方案） #

浮点累加与比较的开销远高于整数操作，可将权重转换为整数比例（根据精度需求放大），通过整数区间判断实现采样，同时配合更快的随机数生成器与二分查找优化：

vector<int> res;
res.resize(100000000);
vector<double> weights{0.1, 0.2, 0.3, 0.4};

// 将浮点权重转换为整数（示例放大10倍，可根据精度调整为100/1000倍）
vector<int> int_weights;
int total_weight = 0;
for (double w : weights) {
    // 用round避免精度丢失
    int w_int = static_cast<int>(std::round(w * 10));
    int_weights.push_back(w_int);
    total_weight += w_int;
}

// 预计算整数前缀和数组
vector<int> prefix_sum(int_weights.size());
prefix_sum[0] = int_weights[0];
for (size_t j = 1; j < int_weights.size(); ++j) {
    prefix_sum[j] = prefix_sum[j-1] + int_weights[j];
}

// 使用高速伪随机数生成器，仅初始化一次
std::mt19937 rand_gen(std::chrono::system_clock::now().time_since_epoch().count());
std::uniform_int_distribution<int> dist(0, total_weight - 1);

for (int i = 0; i < 100000000; ++i) {
    int r = dist(rand_gen);
    // 用lower_bound二分查找前缀和，比线性遍历更高效（权重数量越多优势越明显）
    auto it = std::lower_bound(prefix_sum.begin(), prefix_sum.end(), r + 1);
    res[i] = std::distance(prefix_sum.begin(), it);
}

该方案通过以下几点提升性能：

• 完全避免浮点运算，改用整数操作
• 使用std::mt19937（比random()更快，周期更长）
• 权重数量较多时，用二分查找（O(logn)）替代线性遍历（O(n)）

3. 针对方案(i)的轻量化优化 #

若不想改动核心逻辑，可仅替换随机数生成器并避免重复初始化：

vector<int> res;
res.resize(100000000);
vector<double> weights{0.1, 0.2, 0.3, 0.4};

std::mt19937 rand_gen(std::chrono::system_clock::now().time_since_epoch().count());
std::uniform_real_distribution<double> dist(0.0, 1.0);

for (int i = 0; i < 100000000; ++i) {
    double tempSum = 0;
    double randomNnm = dist(rand_gen);

    for(int j = 0;j < weights.size(); j++) {
        tempSum += weights[j];
        if(randomNnm <= tempSum) {
            res[i] = j;
            break;
        }
    }
}

替换后性能会比原方案(i)略有提升。

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