油藏取样
水库抽样是一种在您不知道要从中抽样的集合的大小时选择公平随机样本的技术。读完本文你将会知道：
- 当您需要水库采样时。
- 其工作原理背后的数学原理，仅使用基本运算：减法、乘法和除法。没有数学符号，我保证。
- 如果您想使用它，这是实施水库采样的简单方法。
在你滚动之前！这篇文章是由ittybit及其用于处理视频、图像和音频的 API 的优秀人员赞助的。如果您需要在应用程序中存储、编码或获取媒体文件的情报，请查看它们！
#知道尺寸后进行采样
你面前有 10 张扑克牌，我要求你随机选 3 张。你怎么做？
您童年时想到的第一个技巧可能是将它们全部混合在一起。然后您可以将它们理顺并选择前 3 个。您可以通过单击“随机播放”在下面看到这种情况发生。
每次您单击“随机播放”时，下面的图表都会跟踪前 3 张牌的内容。
一开始你会注意到有些牌比其他牌被选择的多，但如果你继续下去，情况就会变得平衡。所有卡牌被选中的机会均等。这使得它“公平”。
单击“随机播放 100 次”，直到图表变得均匀。如果您想重新开始，可以重置图表。
此方法适用于 10 张卡，但如果您有 100 万张卡怎么办？将这些混合起来并不容易。相反，我们可以使用随机数生成器来选择 3 个索引。这将是我们选择的 3 张牌。
我们不再需要移动所有的牌，如果我们点击“选择”按钮足够多次，我们就会发现这种方法与混合方法一样公平。
我在这里稍微延伸一下这个类比。数完这副牌需要很长时间才能到达索引 436,234。但当它是内存中的数组时，计算机可以轻松地通过索引找到元素。
现在让我给你一个曲线球：如果我一次向你展示一张牌，而你必须随机选择一张怎么办？
你要给我看多少张卡片？
这就是曲线球：你不知道。
我可以保留你给我的所有卡片，然后在你停止后选择一张吗？
不可以，您一次只能保留一张卡。每次我向您展示一张卡片时，您都可以自由地将卡片换成最新的卡片，但您只能持有一张卡片，并且无法返回到您已经看过的卡片。
那么就不可能了！为什么我需要这样做？
不管你相信与否，这是一个真实的问题，并且有一个真实而优雅的解决方案。
例如，假设您正在构建日志收集服务。文字原木，不是木制的。该服务从其他服务接收日志消息并将其存储起来，以便可以轻松地在一处搜索它们。
在构建这样的服务时，您需要考虑的事情之一是，当另一个服务开始向您发送太多日志时，您该怎么做。也许这是一个糟糕的发布，也许你的一个视频像病毒一样传播开来。无论出于何种原因，它都有可能使您的日志收集服务不堪重负。
让我们模拟一下这个。下面您可以看到出现周期性峰值的日志流。水平线表示日志收集服务每秒可以处理的日志阈值，在本示例中为每秒 5 个日志。
您可以看到每秒的日志数经常会超过阈值。解决这个问题的一种方法是“抽样”。决定仅将一部分日志发送到日志收集服务。让我们发送 10% 的日志。
下面我们将再次看到相同的模拟，但这次未发送到我们的日志收集服务的日志将显示为灰色。该图有 2 条线：一条黑线跟踪发送的日志，即发送到我们的日志收集服务的日志，一条灰线跟踪总日志。
发送日志的速率永远不会超过阈值，因此我们永远不会压垮我们的日志收集服务。然而，在比较安静的时期，我们会在不需要的时候扔掉 90% 的日志！
我们真正想要的是每秒最多发送 5 个日志。这意味着在安静时期您可以获得所有日志，但在高峰期间您会丢弃日志以保护日志收集服务。
实现此目的的简单方法是发送您每秒看到的前 5 个日志，但这不公平。您并没有为所有日志提供平等的被选择机会。
#不知道尺寸时采样
相反，我们希望从每秒看到的所有日志中选取一个公平的样本。问题是我们不知道会看到多少。储层采样就是解决这个问题的算法。
1 秒并不是很长的时间，我们不能只存储我们看到的所有消息，然后使用前面的 select 方法吗？
你可以，但为什么要忍受这种不确定性呢？您将在内存中保留未知数量的日志。足够大的峰值可能会给您带来问题。水库采样解决了这个问题，并且不会使用比您要求的更多的内存。
让我们回到我一次向您展示一张卡片的曲线球。以下是规则的回顾：
- 我会一次从一副牌中抽一张牌。
- 每次我向你展示一张牌时，你必须选择保留它或丢弃它。
- 如果您已经持有一张卡，则在用新卡替换之前丢弃您所持有的卡。
- 我可以随时停止抽牌，无论你持有什么牌，都是你选择的牌。
当我决定停止时，您将如何以确保所有牌都有平等的机会被选择的方式玩这个游戏？
我们每张新卡都抛硬币怎么样？如果是正面，我们保留现有的牌。如果是反面，我们就把它换成新卡。
你走在正确的轨道上。让我们看看抛硬币的想法在实践中是如何发挥作用的。下面你会看到一副纸牌。点击“发牌”将会抽出一张牌，50%的情况下它会进入右侧的弃牌堆，50%的情况下它会成为你在中间持有的牌，任何之前持有的牌都会移至弃牌堆。
问题是，虽然持有与放弃的数量大致相等，这感觉很公平，但当我停下来时，后面的牌比前面的牌更有可能被持有。第一张抽到的牌必须赢得 10 次硬币翻转才能在抽到第 10 张牌后仍然留在你的手中。最后一张牌只需赢得 1 点。
滑动下面的滑块，看看当我们抽更多牌时机会如何变化。每个条形代表这副牌中的一张牌，条形的高度是当我停下来时我们持有该牌的机会。滑块下方是我们持有第一张抽出的牌与最后一张抽出的牌的机会。
当我停止时，任何早于 15 张卡之前的东西被持有的几率都小于 0.01%。
你说我走在正确的道路上！当我中彩票的可能性比持有 24 次抽奖前看到的牌的可能性更大时，这怎么可能是正确的道路呢？
因为不管你信不信，我们只需要对这个想法做一点小小的改变就可以使它公平。
我们不是通过掷硬币来决定是否持有该牌，而是为每张新牌提供1/n的持有机会，其中n是迄今为止我们看到的牌的数量。
等等，就这样？这样就公平了吗？
是的！为了公平起见，每张卡牌必须有平等的被选中的机会。所以对于第二张牌，我们希望两张牌都有1/2机会。对于第三张牌，我们希望所有 3 张牌都有1/3机会。对于第 4 张牌，我们希望所有 4 张牌都有1/4的机会，依此类推。因此，如果我们对新卡使用1/n ，我们至少可以说新卡获得了公平的机会。
让我们看看当您使用这种新方法抽更多牌时的机会。
我知道每张新卡都有被选择的正确机会，但这如何使旧卡公平呢？
到目前为止，我们关注的是新卡被选中的机会，但我们还需要考虑您所持有的卡留在手中的机会。让我们看一下这些数字。
#卡 1
第一张牌很简单：我们没有持有任何东西，所以我们总是选择持有第一张牌。我们持有这张牌的几率是1/1 ，即100% 。
#卡 2
这次我们有了真正的选择。我们可以保留现有的卡，也可以更换新卡。我们已经说过，我们将以1/n的机会做到这一点，其中n是我们迄今为止看到的牌的数量。所以我们替换第一张牌的机会是1/2 ，即50% ，而我们保留第一张牌的机会是它上次被选择的机会乘以它没有被替换的机会，所以100% * 1/2 ，又是50% 。
#卡 3
我们持有的卡片有50%机会出现在那里。无论到目前为止发生了什么，这都是事实。无论我们持有卡1还是卡2，都是50% 。
新卡有1/3机会被选中，所以我们持有的卡有1/3机会被替换。这意味着我们持有的卡有2/3的机会继续持有。所以本轮“生存”的几率是50% * 2/3 。
#卡 N
只要您想抽多少张牌，这种模式都会持续下去。我们可以将这两个选项表示为公式。拖动滑块将n替换为实数，您会发现两个公式始终相等。
如果1/n是选择新卡的几率， 1/(n-1)就是从上次抽牌中选择新卡的几率。不选择新卡的概率是1/n的补数，即1-(1/n) 。
下面再次是卡片，只不过这次设置为使用1/n而不是硬币翻转。单击到牌组的末尾。你觉得公平吗？
很有可能，在这副牌的第二半部分，你永远不会交换你选择的牌。这感觉是错误的，至少对我来说，但正如我们在上面看到的数字表明这是完全公平的。
#选择多张卡
现在我们知道如何选择单张卡，我们可以将其扩展到选择多张卡。我们需要进行 2 项更改：
- 新卡牌不再有
1/n机会被选中，而是现在有k/n机会，其中k是我们要选择的卡牌数量。 - 当我们决定更换一张持有的牌时，我们会随机选择持有的
k张牌中的一张。
因此，我们之前的新牌选择公式变为k/(n-1) ，因为我们现在持有k张牌。那么我们持有的任何一张牌被替换的机会是1-(1/n) 。
让我们看看这如何用实数来表现。
公平性仍然成立，并且对于任何k和n对都成立。这是因为所有持有的牌都有相同的机会被替换，这使得它们在每次抽奖时仍然在你手中的可能性相同。
实现此目的的一个好方法是使用大小为k的数组。对于每张新卡，生成一个 0 到n之间的随机数。如果随机数小于k ，则用新卡替换该索引处的卡。否则，丢弃新卡。
这就是水库取样的工作原理！
#将其应用于日志收集
让我们利用我们现在所了解的水库采样知识并将其应用到我们的日志收集服务中。我们将设置k=5 ，因此我们一次最多“保留”5 条日志消息，并且每秒我们都会将选定的日志发送到日志收集服务。完成此操作后，我们清空大小为 5 的数组并重新开始。
这会在下图中创建一个“块状”模式，并突出显示使用水库采样时的权衡。它不再是实时的日志流，而是每隔一段时间发送的日志块。然而，发送的日志永远不会超过阈值，并且在安静期间，两条线路几乎完美地相互跟踪。
在安静期间不会丢失任何日志，并且在高峰期间每秒发送的日志数不会超过阈值。两全其美。它也不会存储超过k=5日志，因此它将具有可预测的内存使用情况。
#进一步阅读
在阅读本文时，您可能会想到某些日志比其他日志更有价值。例如，您几乎肯定希望保留所有错误日志。
对于该用例，存在水库采样的加权变体。我无法找到更简单的解释，所以该链接是维基百科，我个人觉得有点难以理解。但关键是它存在，如果你需要它，你可以使用它。
＃结论
储层采样是我最喜欢的算法之一，多年来我一直想写一篇关于它的文章。它可以让您以一种既优雅又高效的方式解决乍一看似乎不可能的问题。
再次感谢ittybit赞助这篇文章。我真的不能指望有一个比这更支持我的第一个赞助商了。感谢您相信并理解我在这里所做的事情。
感谢所有阅读这篇文章并提供反馈的人。你写的这篇文章比我自己写的要好得多，并引导我远离了几条行不通的道路。
如果您想通过向我发送一条直接发送到我手机的匿名消息来告诉我您对这篇文章的看法，请访问https://samwho.dev/ping 。