检索计数-最小-草图数据结构中的平均计数

Question

我爱上了概率数据结构。对于我目前的问题，似乎计数最小草图结构几乎是正确的候选者。我想使用计数最小草图来存储每个 ID 的事件。

假设我确实有以下内容

Map<String, Int> {
[ID1, 10],
[ID2, 12],
[ID2, 15]
}

如果我使用计数最小草图，我可以通过 ID 查询数据结构并检索 ~count。

问题

实际上，我对所有ID的平均出现次数感兴趣，在上面的示例中为：12,33。如果我使用计数分钟，那么我似乎需要存储 ID 集，然后迭代该集合并查询每个 ID 的计数分钟并计算平均值。有没有一种改进的方法不存储所有 ID？理想情况下，我只想立即检索平均值，而无需记住所有ID。

希望这有意义！？

Answer 1

如果您知道条目数和不同条目数，您应该能够计算平均计数：

averageCount = totalNumberOfEntries / numberOfDistinctEntries

右？要计算不同条目的数量，您可以使用例如HyperLogLog。您已经在问题中添加了超级日志标签，所以也许您已经知道这一点？