如何在用户事件流中随机抽取 p% 的用户

Question

我正在寻找一种算法，该算法可以从无限的用户列表中公平地抽取 p% 的用户。

一个朴素的算法看起来像这样：

//This is naive.. what is a better way??
def userIdToRandomNumber(userId: Int): Float = userId.toString.hashCode % 1000)/1000.0

//An event listener will call this every time a new event is received
def sampleEventByUserId(event: Event) = {
    //Process all events for 3% percent of users
    if (userIdToRandomNumber(event.user.userId) <= 0.03) {
        processEvent(event)
    }
}

虽然此代码存在问题（hashCode 可能有利于较短的字符串，模运算是离散化值，因此它不完全是 p，等等）。

"more correct" 是为上面的函数 userIdToRandomNumber 找到 userId 到随机数的确定性映射的方法吗？

Answer 1

这是一个非常简单的映射，假设您的数据集足够大：

对于每个用户，generate a random number x，说 [0, 1]。
如果x <= p，选择那个用户

这是一种在大型数据集上实际使用的方法，并为您提供完全随机的结果！

我希望您可以轻松地用 Scala 编写代码。

编辑：在评论中，您提到了确定性。我将其解释为如果你再次采样，它会给你相同的结果。为此，只需为每个用户存储 x。

此外，这适用于任意数量的用户（甚至无限）。您只需要为每个用户生成一次 x。映射只是 userId -> x.

EDIT2: 你问题中的算法有偏差。假设 p = 10%，并且有 1100 个用户（userIds 1-1100）。前 1000 个用户 ID 有 10% 的机会被选中，接下来的 100 有 100% 的机会。此外，散列会将用户 ID 映射到新值，但仍然不能保证模 1000 会给你一个统一的样本！

Answer 2

尝试下面的方法而不是 hashCode。即使对于短字符串，字符的值作为整数也能确保总和超过 100。另外，避免除法，这样就避免了舍入错误

  def inScope(s: String, p: Double) = modN(s, 100) < p * 100

  def modN(s: String, n: Int): Int = {
    var sum = 0
    for (c <- s) { sum += c }
    sum % n
  }

Answer 3

我想出了一个确定性的解决方案，可以从完全随机的流中随机抽取用户（假设随机数生成器是完全随机的）：

def sample(x: AnyRef, percent: Double): Boolean = {
    new Random(seed=x.hashCode).nextFloat() <= percent
}

//sample 3 percent of users
if (sample(event.user.userId, 0.03)) {
    processEvent(event)
}

如何在用户事件流中随机抽取 p% 的用户

How to randomly sample p percent of users in user event stream

random

scala

sampling