3 min read

CMU 15-445/645 fall2024 p0

15445 C++DataBase

在服务器内按照 bustub 的文档用 copilot 配置好了环境，学习了 git。public 指的是模板仓库，origin 指的是从 public clone 下来的远程仓库。在服务器内运行的是本地仓库（local）；master / main 都指默认分支，main 是 2020 年以后开始使用的默认分支名。

Git 命令

git pull public master # 拉取修改
git push origin main   # 推送修改

hyperloglog.cpp

hyperloglog.cpp 实现了一个简化版 HyperLogLog，用于估算去重基数（distinct count）：

  • HyperLogLog(...) 在 src/primer/hyperloglog.cpp:21 校验 n_bits，并初始化 2^n_bits 个寄存器（bucket）。
  • ComputeBinary 与 PositionOfLeftmostOne 在 src/primer/hyperloglog.cpp:38、src/primer/hyperloglog.cpp:49 将哈希转成 64 位 bitset，并计算 rank（第一个 1 出现的位置）。
  • AddElem 在 src/primer/hyperloglog.cpp:64 对元素哈希（哈希定义见 src/include/primer/hyperloglog.h:58），前 n_bits 选桶、剩余位算 rank，然后更新 register[bucket] = max(old, rank)（有锁保护）。
  • ComputeCardinality 在 src/primer/hyperloglog.cpp:89 按 HLL 估算公式计算：estimate = α * m^2 / Σ 2^{-M[i]}，最后取 floor 存到 cardinality_。
  • src/primer/hyperloglog.cpp:108 显式实例化了 int64_t 和 std::string 两种模板类型。

count_min_sketch.cpp

count_min_sketch.cpp 实现了一个并发友好的 Count-Min Sketch 频次估计器（近似计数）：

  • src/primer/count_min_sketch.cpp:31：构造函数校验 width/depth，分配 width * depth 的原子计数数组并清零，再初始化每一行的带种子哈希函数（哈希生成逻辑在 src/include/primer/count_min_sketch.h:99）。
  • src/primer/count_min_sketch.cpp:51、src/primer/count_min_sketch.cpp:68：实现了移动构造/移动赋值；移动后会重建 hash lambdas（因为 lambda 捕获了 this）。
  • src/primer/count_min_sketch.cpp:92：Insert 对每一行计算列索引并 fetch_add(1)，即每次插入更新 depth 个桶。
  • src/primer/count_min_sketch.cpp:116：Count 查询同一元素在每一行对应桶的值，取最小值作为估计频次（CMS 标准做法）。
  • src/primer/count_min_sketch.cpp:104：Merge 支持同尺寸 sketch 按位相加；尺寸不一致会抛异常。
  • src/primer/count_min_sketch.cpp:131、src/primer/count_min_sketch.cpp:138：Clear 全清零；TopK 对候选集合去重、估计计数、稳定排序并返回前 k。
  • src/primer/count_min_sketch.cpp:168：显式实例化了 std::string、int64_t、int 三种模板类型。