输入是一个数据集，其中每一行都包含一个事件，比如点击。成员 ID 是唯一 ID。样本数据：M1,100 M2,100 M3,50 M4,50 目标是对 1% 的点击进行采样，其中总点击数是通过对所有成员 ID 的所有点击求和得出的。如果我希望在样本数据集上采样 1%，我希望应用一种随机采样点击计数并产生 1% 或 3 次点击的技术，例如：M1、1 M2、1 M4、1 或其他组合，其中成员之间的点击总和为 1%。
一种基本方法是分解输入中的所有条目并将其作为数据，然后从中抽取 1%。如果有数百万点击数为 100 的成员，这将非常缓慢/低效。正在寻找不需要数据爆炸的更好解决方案？
似乎显而易见的事情是从用户中抽样，每个用户的概率与他们的点击次数成正比，然后为给定的用户随机均匀地选择一次点击。在您给出的示例中，这意味着选择概率为 100/300、100/300、50/300 和 50/300 的用户，然后从给定用户中选择一次点击。
您可以通过生成介于 0 和 1 之间的随机数 p，然后找到最小的 k (k = 1, 2, 3, . .. #weights) 使得从 1 到 k 的权重之和小于或等于 p。
找到 k 的一种有效方法是构造权重的部分和的列表（即 0、w1、w1 + w2、w1 + w2 + w3、...），然后在该列表上执行二进制搜索（非线性） . 二进制搜索将产生每个样本的时间，该时间与权重（在您的情况下为用户）的数量成对数增长，而线性搜索产生线性增长。
编辑：一个例子。给定 n = 10 个用户，N = (100, 160, 200, 20, 500, 550, 400, 300, 120, 80) 事件。总事件数 = 2430，权重 w = (10/243, 16/243, 20/243, 2/243, 50/243, 55/243, 40/243, 10/81, 4/81, 8/243) . 权重 S 的部分总和 = (0, 10/243, 26/243, 46/243, 16/81, 98/243, 17/27, 193/243, 223/243, 235/243, 1)。（注意：我之前弄错了；顺序应该是 (0, w1, w1 + w2, w1 + w2 + w3, ..., w1 + ... + w[n - 1], 1)。）
给定一个介于 0 和 1 之间的随机数 x，找到（通过二进制搜索）部分和的索引，使得 S[i] <= x < S[i + 1]。然后从用户 i 的 N[i] 个事件中均匀地随机选择一个事件。
我假设您可以执行二进制搜索和每个用户事件的采样，所以我不会写出那部分。
EDIT2：修正了部分总和列表的公式。该列表有 n + 1 个元素；搜索 i 使得 S[i] <= x < S[i + 1] 将因此产生 i = 1, 2, 3, ..., n。假设随机数始终小于 1，则永远不会选择最后一个元素 1。