java - 在无穷无尽的流中保持 n 个最大频率的数字

Question

给定无穷无尽的数字流（BigInteger），如何检测和存储具有前 N 次出现（频率）的数字？

内存有限（不能存储每个数字的计数器）。

编辑：

频率值不能超过大小long

Answer 1

在您拥有所有数据（或大部分数据）之前，无法确定前 N 次出现

您可以通过计算它们出现的频率并按计数对它们进行排序来确定到目前为止的 N 次出现。如果您不能存储太多，这可能是一个问题，在这种情况下，您必须决定要做出哪些妥协来节省空间。

我认为long不够大。你在计算什么样的数据？

---

一个简单的例子，展示了你面临的问题。

假设您源源不断的帐户 ID 都是不同的。这意味着记录前 N 个的唯一方法是将它们全部记录下来。没有一些捷径，就没有其他可能的解决方案。

注意：这可能是您真正想要的衰减平均值，因此如果用户已经出现一段时间，您希望减轻他们的体重。您不希望顶级用户成为不再活跃的用户。

Answer 2

如果流是无穷无尽的，一些较低频率的数字会变得更加频繁。这意味着您必须更新所有数字的频率。

另一方面，由于没有限制 for BigIntegers，因此您有无限的存储需求：对于每个 number n，您必须至少存储一些信息（比方说一点）。如果内存是有限的f，那么还有另一个整数m使得m * n > f.

如果没有一些额外的限制，这个问题就无法解决。

编辑

正如您所指出的，您希望跟踪访问者数量。只计算过去一年或一个月的数据不是更容易吗？你只需要一个字典 (visitor,visits) 对。至于 BigIntegers - 您计划拥有超过 2^63-1 个用户吗？

Answer 3

如果您可以假设分布是平稳的并且您接受近似结果，则可以根据流中的有限数字样本来估计结果。