bigdata - 有人能解释一下概率计数是如何工作的吗？

Question

特别是围绕日志计数方法。

Answer 1

我将尝试阐明概率计数器的使用，但请注意，我不是这方面的专家。

目的是仅使用很少的空间来存储计数器(例如使用 32 位整数)来计数非常非常大的数字。

莫里斯提出了维持“对数计数”的想法，因此计数器不再计数n，而是保存log2(n)。换句话说，给定计数器的值c，计数器表示的实际计数为2ᶜ。

由于日志通常不是整数值，因此当 c 计数器应该递增时就会出现问题，因为我们只能以 1 为步长进行递增。

这里的想法是使用“概率计数器”，因此每次调用计数器上的方法 Increment 时，我们都会以概率 p。这很有用，因为可以证明由具有概率更新的计数器值 c 表示的预期值实际上是n。换句话说，在 n 次调用 Increment 后，计数器所表示的平均值实际上是n(但在任何一个时间点我们的计数器都可能有错误)!我们用准确性来换取用很少的存储空间(例如单个寄存器)计算非常大的数字的能力。

实现此目的的一个方案，如 Morris 所描述的，是让计数器值 c 代表实际计数 2ᶜ(即计数器保存实际计数的 log2)。我们以 1/2ᶜ 的概率更新此计数器，其中 c 是计数器的当前值。

请注意，选择 2 的“基数”意味着我们的实际计数始终是 2 的倍数(因此称为“数量级估计”)。也可以选择其他 b > 1(通常为 b < 2)，以便误差更小，但代价是能够计算更小的最大数。

log log 发挥作用，因为在以 2 为基数的情况下，数字 x 需要 log 2 位来表示。

事实上，还有许多其他方案可以近似计数，如果您需要这样的方案，您可能应该研究哪一种方案对您的应用程序有意义。

引用文献:

参见Philippe Flajolet对于计数器所代表的平均值的证明，或者在“算法导论”一书中的问题 5-1 的解决方案中进行更简单的处理。莫里斯的论文通常是付费墙后面的，我找不到免费版本可以在这里发布。