C++ 中的计数-最小草图

引言

Count-Min Sketch 是一种概率数据结构，用于在大数据流中进行近似计数查询。它在有限的内存空间下高效地估计数据流中元素的频率。

本质上，Count-Min Sketch 由一个二维计数器数组组成。哈希函数用于将流中的元素映射到此数组中的位置。通常使用多个哈希函数，每个哈希函数确定数组中的不同列。当一个元素到达流中时，它在每一行中对应的计数器都会递增。

Count-Min Sketch 背后的主要思想是，通过使用多个哈希函数并为每个元素维护多个计数器，冲突是不可避免的，但对于任何给定元素，所有计数器中的最小值往往能很好地近似其真实频率。通过调整数组的宽度和深度，用户可以控制准确性和内存使用之间的权衡。

程序

输出

Count of item 42: 7
Count of item 55: 3

说明

Count-Min Sketch 类：代码定义了一个名为 CountMinSketch 的 C++ 类。该类表示 Count-Min Sketch 数据结构。

• 私有成员

宽度和深度：这些变量代表 Count-Min Sketch 的宽度和深度，控制其内存使用和准确性。

计数：这是一个二维向量，表示 sketch 中的计数器数组。

哈希函数：此向量包含 `std::hash` 函数的实例，用于哈希元素。

• 构造函数

构造函数初始化宽度、深度和计数数组。

它还用深度数量的哈希函数填充 hash_functions 向量。

• 更新方法

更新方法将一个项目及其计数作为输入。

它使用每个哈希函数对项目进行哈希，并更新计数数组中相应的计数器。

• 查询方法

查询方法将一个项目作为输入，并返回其计数的估计值。

它使用每个哈希函数对项目进行哈希，并检索所有哈希函数中的最小计数。

• 主函数

在 main 函数内部，使用指定的宽度和深度创建 CountMinSketch 实例。

sketch 使用项目 42 和 55 的计数进行更新。

调用查询方法来估计这些项目的计数，并打印结果。

复杂度分析

时间复杂度

更新操作

使用项目计数更新 sketch 的时间复杂度为 O(d)，其中 ?

d 是 sketch 的深度。

这是因为，对于每个哈希函数（其中有 d 个），更新涉及恒定时间操作以递增相应的计数器。

查询操作

查询 sketch 中项目计数的时间复杂度也为 O(d)。

类似于更新操作，对于每个哈希函数，查询涉及访问相应的计数器并找到最小值。

空间复杂度

Count-Min Sketch 的空间复杂度由其数据结构的大小决定，其中包括

• 二维计数数组的 O(w×d) 空间，其中 w 是宽度（每行计数器数量），d 是深度（哈希函数数量）。
• 用于在 hash_functions 向量中存储哈希函数的 O(d) 空间。