Reservoir Sampling

Reservoir sampling 是一种在不知道抽样集合大小的情况下，选择一个公平的随机样本的技术。读完本文，你将了解：

• 何时需要 Reservoir sampling。
• 其工作原理背后的数学原理，仅使用基本的运算：减法、乘法和除法。我保证不使用数学符号。
• 如果想使用 Reservoir sampling，一种简单的实现方法。

在你滚动之前！这篇文章是由 ittybit 的朋友们赞助的，他们提供用于处理视频、图像和音频的 API。如果你需要存储、编码或从应用中的媒体文件中获取信息，请查看它们！

# 在已知大小的情况下抽样

现在你面前有 10 张扑克牌，我让你随机选择 3 张。你会怎么做？

你小时候可能想到的第一个方法是把它们全部洗牌。然后你可以把它们排好，选出前 3 张。你可以通过点击“洗牌”来看到下面的过程。

A A 4 4 K K 2 2 J J Q Q 5 5 8 8 10 10 9 9 洗牌

每次你点击“洗牌”，下面的图表都会记录前 3 张牌是什么。

0 A 0 4 0 K 0 2 0 J 0 Q 0 5 0 8 0 10 0 9

起初你会注意到有些牌被选中的次数比其他牌多，但如果你一直洗牌，它们会变得均匀。所有牌都有同等的机会被选中。这使得它“公平”。

点击“洗牌 100 次”，直到图表变得均匀。如果你想重新开始，可以重置图表。

洗牌 100 次 重置

这种方法适用于 10 张牌，但如果你有 100 万张牌呢？把它们混在一起就不容易了。相反，我们可以使用随机数生成器来选择 3 个索引。这些将是我们选择的 3 张牌。

A A 4 4 K K 2 2 J J Q Q 5 5 8 8 10 10 9 9 选择

我们不再需要移动所有的牌，如果我们多次点击“选择”按钮，我们会发现这种方法和洗牌一样公平。

0 A 0 4 0 K 0 2 0 J 0 Q 0 5 0 8 0 10 0 9 选择 100 次 重置

我在这里稍微夸大了类比。数完牌堆找到第 436,234 张牌需要很长时间。但是当它在内存中是一个数组时，计算机可以毫不费力地通过索引找到一个元素。

现在让我给你抛出一个难题：如果我一次给你看一张牌，你必须随机选择一张呢？

你要给我看多少张牌？

这就是难题：你不知道。

我可以一直拿着你给我的所有牌，等你停下来后再选一张吗？

不，你一次只能拿一张牌。你可以自由地用最新的牌替换你的牌，但你只能拿一张，而且你不能回到你已经看过的牌。

那是不可能的！我为什么要这样做呢？

信不信由你，这是一个实际存在的问题，而且有一个真实而优雅的解决方案。

例如，假设你正在构建一个日志收集服务。文本日志，而不是木头日志。此服务接收来自其他服务的日志消息并存储它们，以便在一个地方轻松搜索它们。

在构建此类服务时，你需要考虑的一件事是，当另一个服务开始向你发送过多的日志时，你会怎么做。也许这是一个糟糕的版本，也许你的一个视频走红了。无论是什么原因，它都威胁要淹没你的日志收集服务。

让我们模拟一下。在下面你可以看到一个经历周期性峰值的日志流。水平线表示日志收集服务可以处理的每秒日志阈值，在本例中为每秒 5 个日志。

8:18:11 PM W

• a 10 dollar bill exceeded quota by downloading entire internet 8:18:11 PM W
• git history rewritten by smart toaster 8:18:11 PM E
• holographic display went on vacation despite all odds 8:18:11 PM E
• Black Widow implemented security through interpretive dance 8:18:11 PM W
• robot vacuum estimated task as "somewhere between now and heat death of universe"

你可以看到，每隔一段时间，每秒日志数都会超过阈值。一种处理方法是“抽样”。决定只将一小部分日志发送到日志收集服务。让我们发送 10% 的日志。

下面我们将再次看到相同的模拟，但这次未发送到我们的日志收集服务的日志将变为灰色。该图有 2 条线：黑线跟踪已发送的日志，即发送到我们的日志收集服务的日志，灰线跟踪总日志。

8:18:11 PM E

• webhook delivered a turtle instead of payload 8:18:11 PM W
• a goldfish spent entire budget on NFTs of your favorite text editor 8:18:11 PM I
• AI assistant monkey patched themselves to avoid debugging meetings 8:18:11 PM W
• Product backlog items gain sentience, create their own MacOS 8:18:11 PM I
• wearable tech requested unlimited PTO for their cloud instance

发送的日志速率永远不会超过阈值，因此我们永远不会淹没我们的日志收集服务。但是，在较安静的时期，我们却丢弃了 90% 的日志，而我们并不需要这样做！

我们真正想要的是_最多_每秒发送 5 个日志。这意味着在安静时期，你可以获得所有日志，但在高峰时期，你会丢弃日志以保护日志收集服务。

实现此目的的简单方法是发送你每秒看到的前 5 个日志，但这并不公平。你没有给所有日志平等的机会被选中。

# 在未知大小的情况下抽样

相反，我们想要选择每秒看到的所有日志的公平样本。问题是我们不知道我们会看到多少个日志。Reservoir sampling 是一种解决这个确切问题的算法。

1 秒不是很长的时间，我们不能只存储我们看到的所有消息，然后使用上面提到的选择方法吗？

你_可以_，但为什么要承担这种不确定性呢？你将在内存中保存未知数量的日志。一个足够大的峰值可能会给你带来问题。Reservoir sampling 解决了这个问题，并且在不使用超过你要求的内存的情况下做到了这一点。

让我们回到我一次给你看一张牌的难题。以下是规则回顾：

1. 我将一次从一副牌中抽出一张牌。
2. 每次我给你看一张牌，你都必须选择保留它或丢弃它。
3. 如果你已经拿着一张牌，你必须在用新牌替换它之前丢弃你拿的牌。
4. 在任何时候，我都可以停止抽牌，你拿着的任何牌就是你选择的牌。

你将如何玩这个游戏，以确保当我决定停止时，所有牌都有平等的机会被选中？

我们每张新牌都抛硬币怎么样？如果是正面，我们保留我们拥有的牌。如果是反面，我们用新牌替换它。

你的方向是对的。让我们看看抛硬币的想法在实践中是如何发挥作用的。在下面你可以看到一副牌。点击“发牌”将抽出一张牌，并且 50% 的时间它会进入右侧的废弃堆，50% 的时间它会成为你中心的牌，任何先前拥有的牌都会移动到废弃堆。

0 0 A A 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 J J Q Q K K A A 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 J J Q Q K K A A 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 J J Q Q K K A A 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 J J Q Q K K 发牌重置

问题是，虽然持有与丢弃的计数大致相等，这感觉很公平，但稍后的牌在我停止时更有可能被持有。第一张抽出的牌必须赢得 10 次抛硬币才能在抽出第 10 张牌后仍然在你手中。最后一张牌只需要赢 1 次。

滑动下面的滑块以查看当我们抽出更多牌时，机会如何变化。每个条代表牌堆中的一张牌，条的高度是我们停止时持有该牌的概率。滑块下方是我们持有第一张抽出的牌与最后一张抽出的牌的概率。

滑动以抽牌。 K K card 1

K K card -

任何比 15 张牌更早的牌，在我们停止时被持有的几率都不到 0.01%。

你说我的方向是对的！当我持有 24 张牌之前看到的牌的几率比中彩票还低时，怎么能说我的方向是对的呢？

因为信不信由你，我们只需要对这个想法做一个小小的改变就能让它变得公平。

我们不是抛硬币来决定是否持有这张牌，而是给每张新牌一个 1/n 的概率被持有，其中 n 是我们目前看到的牌的数量。

等等，就这些？这就能让它变得公平？

是的！为了公平起见，每张牌都必须有平等的机会被选中。所以对于第 2 张牌，我们希望两张牌都有 1/2 的机会。对于第 3 张牌，我们希望所有 3 张牌都有 1/3 的机会。对于第 4 张牌，我们希望所有 4 张牌都有 1/4 的机会，依此类推。所以如果我们对新牌使用 1/n，我们至少可以说新牌已经有了一次公平的机会。

让我们看看使用这种新方法抽出更多牌时的几率。

滑动以抽牌。 K K card 1

K K card -

我明白每张新牌都有正确的选择概率，但这如何使旧牌公平？

到目前为止，我们一直关注新牌被选中的概率，但我们还需要考虑你持有的牌留在你手中的概率。让我们来看看这些数字。

# 第一张牌

第一张牌很容易：我们什么都没拿着，所以我们总是选择拿着第一张牌。我们持有这张牌的概率是 1/1，或者 100%。

持有 100% 替换

# 第二张牌

这次我们有了一个真正的选择。我们可以继续拿着我们拥有的牌，或者用新牌替换它。我们已经说过我们将以 1/n 的概率来做这件事，其中 n 是我们目前看到的牌的数量。所以我们替换第一张牌的概率是 1/2，或者 50%，我们继续持有第一张牌的概率是它上次被选中的概率乘以它被替换的概率，所以 100% * 1/2，这又是 50%。

持有 100% * 1/2 50% 替换 1/2 50%

# 第三张牌

我们持有的牌有 50% 的概率在那里。无论到目前为止发生了什么，都是如此。无论我们拿着第一张牌还是第二张牌，都是 50%。

新牌有 1/3 的概率被选中，所以我们持有的牌有 1/3 的概率被替换。这意味着我们持有的牌有 2/3 的概率保持持有。所以它“幸存”这一轮的概率是 50% * 2/3。

持有 50% * 2/3 33.33% 替换 1/3 33.33%

# 第 N 张牌

这种模式会持续任意多张你想要抽的牌。我们可以用公式来表示这两种选择。拖动滑块用实数替换 n，你会发现这两个公式始终相等。

持有 1/(n-1) * (1-(1/n))

替换 1/n

如果 1/n 是选择新牌的概率，1/(n-1) 是从上一次抽牌中选择新牌的概率。不_选择新牌的概率是 1/n 的_补数，即 1-(1/n)。

下面是这些牌，但这次设置为使用 1/n 而不是抛硬币。点击到牌堆的末尾。你觉得公平吗？

0 0 A A 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 J J Q Q K K A A 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 J J Q Q K K A A 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 J J Q Q K K A A 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 J J Q Q K K 发牌重置

很有可能在牌堆的后半部分，你永远不会替换你选择的牌。这_感觉_不对劲，至少对我来说是这样，但正如我们在上面看到的那样，数字表明它是完全公平的。

# 选择多张牌

现在我们知道如何选择一张牌，我们可以将其扩展到选择多张牌。我们需要做 2 个更改：

1. 新牌被选中的概率不再是 1/n，而是 k/n，其中 k 是我们想要选择的牌的数量。
2. 当我们决定替换一张牌时，我们随机选择我们持有的 k 张牌中的一张。

所以我们新的先前牌选择公式变为 k/(n-1)，因为我们现在持有 k 张牌。然后我们持有的任何牌被替换的概率是 1-(1/n)。

让我们看看这在实数中是如何运作的。

持有 k/(n-1) * (1-(1/n))

替换 k/n

公平性仍然成立，并且对于任何 k 和 n 的配对都将成立。这是因为所有持有的牌都有平等的机会被替换，这使它们在每次抽牌时都有相同的可能性仍然在你手中。

一个很好的实现方法是使用一个大小为 k 的数组。对于每张新牌，生成一个介于 0 和 n 之间的随机数。如果该随机数小于 k，则用新牌替换该索引处的牌。否则，丢弃新牌。

A A 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 J J Q Q K K A A 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 J J Q Q K K A A 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 J J Q Q K K A A 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 J J Q Q K K 发牌重置

这就是 Reservoir sampling 的工作原理！

# 将其应用于日志收集

让我们将我们现在了解的 Reservoir sampling 应用于我们的日志收集服务。我们将设置 k=5，所以我们每次“持有”最多 5 个日志消息，并且每秒我们将发送选定的日志到日志收集服务。在我们完成之后，我们清空我们的大小为 5 的数组，然后重新开始。

这会在下面的图表中创建一个“块状”模式，并突出显示使用 Reservoir sampling 时的权衡。它不再是日志的实时流，而是在一个间隔发送的日志块。但是，发送的日志永远不会超过阈值，并且在安静时期，这两条线几乎完美地相互跟踪。

8:18:11 PM I

• a copy of Introduction to Algorithms submitted PR in a cat format 8:18:11 PM W
• machine learning model became a overly complex life coach 8:18:11 PM W
• retrospective turned into locally-sourced therapy session 8:18:11 PM W
• have you tried turning the Captain America off and on again? 8:18:11 PM E
• standup meeting exceeded sprint length accidentally

在安静时期不会丢失日志，在高峰时期每秒发送的日志不会超过阈值。两全其美。它也不会存储超过 k=5 个日志，所以它将具有可预测的内存使用量。

# 进一步阅读

你在阅读这篇文章时可能会想到，有些日志比其他日志更有价值。例如，你几乎肯定想要保留所有错误日志。

对于该用例，Reservoir sampling _确实_有一个加权变体。我找不到一个更简单的解释，所以这个链接是指 Wikipedia，我个人觉得有点难以理解。但关键是它存在，如果你需要它，你可以使用它。

# 结论

Reservoir sampling 是我最喜欢的算法之一，我一直想写它已经好几年了。它允许你解决一个起初看起来不可能的问题，并且以一种既优雅又高效的方式。

再次感谢 ittybit 赞助这篇文章。我真的无法期望有更支持我的第一个赞助商。感谢你相信并理解我在这里所做的事情。

感谢所有阅读这篇文章并提供反馈意见的人。你让这篇文章比我自己做得更好，并且引导我远离了几条行不通的道路。

如果你想通过向我发送一条直接发送到我手机的匿名消息来告诉我你对这篇文章的看法，请访问 https://samwho.dev/ping。

喜欢这篇文章？考虑订阅以通过电子邮件获取有关新文章的更新！ 或者，你可以通过 RSS 订阅。 由 buttondown 提供支持