Joh*_*sky 15 random algorithm statistics list
我有一个100,000个对象的列表.每个列表元素都有一个与之关联的"权重",它是从1到N的正整数.
从列表中选择随机元素的最有效方法是什么？我想要随机选择的元素的分布与列表中的权重分布相同的行为.
例如,如果我有一个列表L = {1,1,2,5},我希望第4个元素平均被选择为5/9的时间.
假设插入和删除在此列表中很常见,因此任何使用"积分区域表"的方法都需要经常更新 - 希望有一个O(1)运行时和O(1)额外内存所需的解决方案.
您可以使用扩充二进制搜索树来存储元素,以及每个子树中权重的总和.这允许您根据需要插入和删除元素和权重.采样和更新都需要每次操作O(lg n)时间,空间使用量为O(n).
通过在[1,S]中生成随机整数来完成采样,其中S是所有权重的总和(S存储在树的根处),并使用为每个子树存储的权重和执行二进制搜索.