bigdata – 有人可以解释概率计数的工作原理吗？

目的是仅使用一点空间来计数非常大的数字来存储计数器(例如,使用32位整数).

莫里斯提出了保持“日志计数”的想法,因此计数器不是计数n,而是保持log 2(n).换句话说,给定计数器的值c,计数器表示的实数是2?.

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

这里的想法是使用“概率计数器”,因此对于我们计数器上的方法增量的每次调用,我们用概率p更新实际计数器值.这是有用的,因为可以证明由具有概率更新的计数器值c表示的期望值实际上是n.换句话说,在n次调用Increment之后,我们的计数器表示的值实际上是n(但在任何一个时间点,我们的计数器可能都有错误)！我们正在准确地计算具有很小存储空间的非常大的数字(例如单个寄存器).

如Morris所述,实现这一目的的一种方案是使计数器值c代表实际计数2?(即计数器保持实际计数的log 2).我们以概率1 /2?更新此计数器,其中c是计数器的当前值.

请注意,选择2的“基数”意味着我们的实际计数总是2的倍数(因此称为“数量级估计”).也可以选择其他b> 1(通常使得b <2)使得误差较小,代价是能够计数较小的最大数. 日志日志起作用,因为在base-2中,数字x需要表示log 2位. 实际上还有许多其他方案来近似计算,如果你需要这样的方案,你应该研究哪一个对你的应用有意义. 参考文献： 有关计数器所代表的平均值的证明,请参阅Philippe Flajolet,或者在“算法简介”一书中解决问题5-1的更简单的处理.莫里斯的论文通常在付费墙后面,我找不到免费版本在这里发布.