我需要一个简单的类来计算来自网络监控系统的 IP 地址分布(直方图)。可能有 1 到 1010 个数据包,有 1 到 2 个32 地址(或者更多,如果我们有 IPv6 接口(interface))。我理想中寻找的是一个 C++ 类,它会自动创建直方图,然后在达到限制时,开始通过某种前缀路由组合不太受欢迎的节点。
有没有人知道这样的东西,或者我需要写它吗?
谢谢!
最佳答案
您所描述的听起来像是 Count-Min sketch 的完美用例 数据结构。该数据结构用于近似数据流中各种元素的频率,并且可以进行调整以精确地使用一定数量的内存。此外,给定一个固定的内存限制,您可以调整它的准确性以及与您想要的确切答案的接近程度。我的理解是,Google 使用此数据结构来识别频繁搜索,而无需使用大量磁盘空间。
作为一个额外的好处,数据结构永远不会低估给定值的真实频率。也就是说,如果您想查询您看到给定 IP 地址的频率,Count-Min sketch 将始终为您提供一个不小于真实数字的值。
Count-Min 草图非常容易实现——您只需要一堆不同的哈希函数和一个二维数组。您还可以找到 Count-Min 草图的各种不同实现 at Google's page on the data structure.
希望这对您有所帮助!
关于c++ - 寻找用于计算 IP 地址的算法/类(直方图),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14225306/