C++ 中采样加权随机指数的最快方法？

Question

我正在实现一种算法，需要从 100 个整数的数组中抽取数千个随机样本。

std::vector<int> weight_vector(100);

我想了解如何提高当前方法的运行时间，因为它是我的整体算法的主要瓶颈。考虑下面的代码，它乘以加权随机采样。

// let's just populate weight_vector somehow: 1, 2, ..., 99
iota(weight_vector.begin(), weight_vector.end(), 0);

std::discrete_distribution<int> weighted_dist = std::discrete_distribution<>(
    weight_vector.begin(),
    weight_vector.end()
);

auto start = std::chrono::high_resolution_clock::now();

for (int n = 1; n <= 10000; n++)
{
    int random_index = weighted_dist(generator);

    // do something with randomly sampled index...
}

auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double, std::milli> ms_double = end-start;

std::cout << ms_double.count() << "ms" << std::endl;

该循环的运行时间约为2.9ms。目前这个值高得令人无法接受，将其降低到 0.1 毫秒的数量级将是一个巨大的成功。有什么明显的方法可以做到这一点吗？或者也许是生成随机索引的更有效方法？

我怀疑这可能是可能的，因为设置

int random_index = rand()%100;

会使循环的运行时间小于 0.1 毫秒。当然，这是错误的分布，但是它让我怀疑采样随机位不需要像第一种方法那样耗时（例如，我可以通过一次或多次调用

rand()

来获得加权随机位吗？）。我不关心随机性的“质量”，如果我采样统一的索引，

rand()

就完全足够了。

我想在转向并行化之前考虑这一点（我的所有循环迭代都是独立的，最终结果基本上是循环值的平均值，所以理论上这是可能的）。如果我最终走这条路，并行化可行吗？或者，运行时间是否以毫秒为单位低于线程管理开销开始占主导地位的阈值？

非常感谢您的帮助，对于我的问题的模糊性，我深表歉意。我对 C++ 和“低级”编程非常缺乏经验，所以请原谅。

Answer 1

您应该查看别名采样。此方法需要一些准备步骤，并且使用更多的内存。但采样本身非常快，O(1)。

C++ 和其他语言有多种实现，例如https://github.com/scilari/sas_cpp