algorithm - 处理请求百分比的在线算法

Question

要注意的是，并不是所有的请求都应该被处理。表述得更清楚一点:

假设您有一个目标比率 r，并且算法在每次迭代中看到“op”或“nop”。目标是决定是否处理“op”(让我们称处理过的 op 为“pop”)，这样

#pop/(#op + #nop) ~= r

我认为仅跟踪上述比率并确保它保持在合理范围内的天真方法在实践中会正常工作，所以我更感兴趣的是这是否是一个众所周知的问题或者是否有一些代码我可以在这里重复使用。

Answer 1

如果您可以假设任何给定操作是否为 nop 是由概率 p 决定的 iid，那么您可以做的一件事就是选择以某个概率 处理每个 op iid问。目标是

r = P(pop)
  = P(pop|op)P(op) + P(pop|nop)P(nop)
  = qp + 0(1-p)

所以我们应该选择q = r/p。简单俗气。

如果p 未知，可以保留#op 和#nop 的总和来估计p；我建议使用高斯平滑，这样你就可以估计 p = (#op + 1)/(#op + #nop + 1)。

有一个明显的确定性启发式方法也可以很好地工作:即，如果我们的 #op/(#op+#nop) 的运行值低于 r，则处理您看到的下一个操作；否则，不要。这应该会为 r 产生很好的结果；然而，它有一个很大的缺点，即是否处理操作的决定是确定性的，并且仅取决于我们之前处理了多少操作。特别是，如果您目前看到的操作数量与操作的内容之间存在相关性——例如，某些特别有趣的操作不太可能在长字符串后不久出现nops，或操作之间任何其他此类“时间相关性”——这将使您的结果以微妙且难以检测的方式产生偏差。我猜想如果不处理整个数据集(这可能工作量太大)，您就无法真正知道数据中是否存在此类模式。因此，我建议改用概率算法。