基本上我需要跟踪大量计数器。我可以按名称递增或递减每个计数器。最简单的方法是使用哈希表，使用 counter_name作为key及其对应的count作为value为此key .
计数器不需要 100% 准确，count 的近似值很好。所以我想知道是否有任何概率数据结构可以将 N 个计数器的空间复杂度降低到低于 O(N)，有点类似于 HyperLogLog 如何通过仅给出近似结果来减少计算 N 项的内存需求。有什么想法吗？
最佳答案
在我看来，你要找的东西是Count-min sketch .
Reading a stream of elements a1, a2, a3, ..., an where there can be a lot of repeated elements, in any time it will give you the answer to the following question: how many ai elements have you seen so far.
基本上您的独特元素可以双射到您的计数器中。 Countmin sketch 允许您调整参数以用您的内存换取准确性。
附言我描述了一些其他流行的 probabilistic data structures here .
关于algorithm - 有没有什么概率数据结构可以降低大量计数器的空间复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36585688/