从集合中选择n个随机数

您需要计算集合中所有权重的总和(如果考虑性能的话,可能还需要缓存)。然后,生成n个范围达到该值的随机数。最后,迭代您的集合,计算到目前为止遇到的权重之和。检查所有(剩余)随机数。如果数字介于和的前一个值和下一个值之间,请插入集合中的值并删除随机数。当随机数列表为空或已到达集合末尾时停止。

我不知道有什么图书馆,但听起来你有一个加权的轮盘赌。以下是一些伪代码的参考,尽管上下文与遗传算法有关: http://www.cse.unr.edu/~banerjee/selection.htm

至于“尽可能高效”,这将取决于数据的某些特性。在加权轮盘赌的应用中,搜索索引时可以考虑采用二进制搜索。然而,轮盘赌轮的每一个槽的可能性不是一样的,因此按照它们的重量顺序检查它们可能是有意义的。

很大程度上取决于您愿意花费的额外存储量,以便更快地进行选择。

如果你不愿意使用任何额外的存储空间,@alex emelianov的答案和我想发布的差不多。如果您愿意使用一些额外的存储(并且可能是与 std::set )您可以创建一个树(如集合使用),但是在树的每个节点上,您还可以将(加权的)项目数存储到该节点的左侧。这将允许您从生成的数字映射到具有对数(而不是线性)复杂性的正确关联值。