最后更新：Aug 26, 2025

不要将您的项目发布到公开的 Github 仓库上。

概述

本学期所有的编程项目都将基于 BusTub 数据库管理系统。该系统使用 C++ 编写。为了确保您具备必要的 C++ 基础，您必须完成一个简单的编程作业来评估您对基本 C++ 特性的了解。本项目不会给您评分，但您必须以满分完成本项目才能继续本课程的学习。任何无法在截止日期前完成此作业的学生将被要求退课。

本编程作业中的所有代码必须使用 C++ 编写。项目将专门为 C++17 编写，但我们发现通常了解 C++11 就足够了。如果您之前没有使用过 C++，以下是一些可以帮助您的资源：

15-445 Bootcamp，其中包含多个小示例，帮助您熟悉 C++11 特性。
Learncpp 是一个有用的资源，包含测试您知识的测验。
cppreference 提供了更详细的语言内部机制文档。
A Tour of C++ 和 Effective Modern C++ 也可以在 CMU 图书馆 digitally 获取。

如果您使用 VSCode，我们建议您安装 CMake Tools、C/C++ Extension Pack 和 clangd。之后，按照本教程学习如何在 VSCode 中使用可视化调试器：Debug a C++ project in VS Code。

如果您使用 CLion，我们建议您按照本教程操作：CLion Debugger Fundamentals。

如果您更喜欢使用 gdb 进行调试，有很多教程可以教您如何使用 gdb。以下是一些我们认为有用的教程：

这是一个个人项目，需要独立完成（即不分组）。

发布日期： Aug 25, 2025
截止日期： Sep 07, 2025 @ 11:59pm

项目规格说明

考虑以下场景：您是一个热门博客网站的管理员，并且一直收到关于某些会计垃圾邮件过度泛滥的报告。为了绘制整体网络使用情况并检测潜在的 DDoS 攻击，您需要一种实时方法来计算每个 IP 地址在传入请求流中出现的频率。然而，流量非常庞大，这使得传统数据结构要么太慢，要么太耗内存。这就是 Count-Min Sketch 发挥作用的地方！

Count-min sketch（CM Sketch）是一种概率型数据结构，使用亚线性内存来近似数据流中项目的频率计数。它维护一个紧凑的二维计数器数组，由 d 个独立种子哈希函数寻址。每次更新在每行递增一个单元格，查询则返回这些计数器的最小值。此外，count-min sketch 是可合并的，意味着两个 sketch 的和等价于在相应输入流的拼接上构建单个 sketch。Count-min sketch 广泛用于网络流量监控、流分析和数据库系统优化。

Count-min sketch 基于以下参数：

width (w) – 哈希矩阵中的列数；每个哈希将项目映射到 [0, w-1] 中的一个索引。w 越大 => 加性误差越小。
depth (d) – 行数 / 独立哈希函数数量。d 越大 => 严重高估的概率越低。
hash family / seeds – 一种推导 d 个成对独立哈希函数的方法（例如，通过为每行使用不同的种子来种子化基础哈希）。

为了解释该数据结构的工作原理，让我们按照开头的示例，考虑以下输入流：["24.156.99.202", "172.217.22.14", "64.104.78.227", "24.156.99.202"]。让我们使用宽度为 4、深度为 3 的 count-min sketch。对于 3 行中的每一行，对字符串进行哈希处理（使用该行的种子）以生成一个整数，对其取模 4 得到列索引，并递增 (行, 列) 处的计数器。

首先，将哈希矩阵（3 行 x 4 列）初始化为全零：

0 0 0 0
0 0 0 0
0 0 0 0

现在处理流。我们首先插入 "24.156.99.202"。假设以下哈希位置（mod 4）：

hash1 → 2
hash2 → 0
hash3 → 3

我们相应地更新单元格：

0 0 1 0
1 0 0 0
0 0 0 1

接下来，我们插入 "172.217.22.14" 并在以下哈希位置递增计数器：

hash1 → 1
hash2 → 0 （与第一个项目在第 1 行发生冲突）
hash3 → 2

更新：

0 1 1 0
2 0 0 0
0 0 1 1

现在我们插入 "64.104.78.227"：

hash1 → 3
hash2 → 1
hash3 → 2 （与第二个项目在第 3 行发生冲突）

表格变为：

0 1 1 1
2 1 0 0
0 0 2 1

最后，重复 "24.156.99.202"（与之前相同的哈希位置：2, 0, 3）。再次递增这些单元格：

0 1 2 1
3 1 0 0
0 0 2 2

现在，让我们估计 "24.156.99.202" 的频率。让我们查找插入该键时使用的相同列：

Row 0, col 2 → 2
Row 1, col 0 → 3
Row 2, col 3 → 2

估计值为各行中的最小值：

Estimate("24.156.99.202") = min(2, 3, 2) = 2

为什么取最小值？每行的计数器可能因与其他项目的冲突而膨胀，但独立哈希行中的最小值给出了对真实频率的最紧上界。

资源

要更多了解 Count-min sketch 及其工作原理，

一个可视化演示，展示 count-min sketch 的内部工作原理。
一个关于 count-min sketch 及其实际应用的综合概述（完整视频还涵盖了 Bloom Filter 和 HyperLogLog，另外两种广泛应用于大规模数据结构）。
一篇分析该数据结构时间和空间界限的简明论文。

说明

您需要完成本项目的以下任务：

任务 #1

实现一个基本的 Count-min sketch 数据结构，支持插入、计数估计和合并。

在 count_min_sketch.h 中，需要实现以下函数：

CountMinSketch(width, depth)：构造函数，创建一个具有 width 列（桶）和 depth 行（哈希函数）的 count-min sketch。
CountMinSketch(&&other)：移动构造函数，将 sketch 资源的所有权从另一个实例转移。
operator=(&&other)：移动赋值运算符，将 sketch 资源从另一个实例移动到当前实例。
Insert(item)：将指定项目插入 count-min sketch。此函数需要是线程安全的
Count(&item)：返回项目的估计频率。
Clear()：重置数据结构，清除之前流的数据。
Merge(&other)：通过组合两个兼容 sketch 的计数器值来创建新的 sketch。
TopK(k, &candidates)：count-min sketch 的实际应用——给定已存储在 count-min sketch 中的 candidates，返回估计计数最高的 k 个候选项。

您可以自由设计辅助函数来辅助实现。

重要信息

对于矩阵的哈希函数构造，请使用 bustub 仓库中的带种子哈希函数 "common/util/hash_util.h"。请勿使用外部库的哈希函数或自行实现，因为这可能会影响您是否通过我们提供的测试套件！
测试套件包含并行测试。但是，我们只期望 Insert(item) 是线程安全的。换句话说，您的实现必须正确处理多个线程同时向多个 count-min sketch 执行插入的场景。
您可能会注意到最后一个测试将您的 Insert(item) 实现性能与严格顺序实现进行比较。只有当您的实现的相对加速比大于 1.2 时，您才能通过此测试。我们期望您不要仅使用单个全局锁来保护整个数据结构。 如果您这样做，争用比将有效地约为 1.0。有很多方法可以做到这一点。作为提示，尝试思考分解锁粒度的方法，或者更好的是，完全不使用锁（如果您追求后者，您可能会发现 compare_exchange 很有帮助）。如果您发现这难以推理，请先尝试用全局锁通过其他测试，然后再尝试优化此测试。

创建您自己的项目仓库

如果以下 git 概念（例如仓库、合并、拉取、分叉）对您来说不太清楚，请先花一些时间学习 git。

按照说明设置您自己的私有仓库和开发分支。如果您之前通过 GitHub 界面（点击 Fork）分叉了仓库，请不要将任何代码推送到您公开的分叉仓库！在 git push 任何代码之前，请确保您的仓库是私有的。

如果教师对代码进行了任何更改，您可以通过将私有仓库连接到 CMU-DB 主仓库来合并更改到您的代码中。执行以下命令添加远程源：

$ git remote add public https://github.com/cmu-db/bustub.git

然后您可以在学期期间根据需要拉取最新的更改：

$ git fetch public
$ git merge public/master

设置您的开发环境

首先安装 BusTub 所需的软件包：

# Linux
$ sudo build_support/packages.sh
# macOS
$ build_support/packages.sh

请参阅 README 获取有关如何设置不同操作系统环境的更多信息。

要从命令行构建系统，请执行以下命令：

$ mkdir build
$ cd build
$ cmake -DCMAKE_BUILD_TYPE=Debug ..
$ make -j`nproc`

我们建议始终以调试模式配置 CMake。这将使您能够输出调试消息并检查内存泄漏（更多内容见以下部分）。

测试

您可以使用我们的测试框架来测试本次作业的各个组件。我们使用 GTest 进行单元测试。您可以通过在测试名称前添加 DISABLED_ 前缀来禁用 GTest 中的测试。要从命令行运行测试：

$ cd build
$ make -j$(nproc) count_min_sketch_test
$ ./test/count_min_sketch_test

在本项目中，没有隐藏的测试。在以后的项目中，起始代码中提供的测试只是我们用来评估和评分您项目的所有测试的子集。您应该自行编写额外的测试用例来检查您实现的完整功能。

请确保您删除了测试名称中的 DISABLED_ 前缀，否则它们将不会运行！

格式化

您的代码必须遵循 Google C++ 风格指南。我们使用 Clang 自动检查您的源代码质量。如果您的提交未通过这些检查中的任何一项，您的项目成绩将为零。

执行以下命令检查您的语法。format 目标将自动修正您的代码。check-lint 和 check-clang-tidy 目标将打印错误，您必须手动修复这些错误以符合我们的风格指南。

$ make format
$ make check-clang-tidy-p0

内存泄漏

在本项目中，我们使用 LLVM Address Sanitizer (ASAN) 和 Leak Sanitizer (LSAN) 来检查内存错误。要启用 ASAN 和 LSAN，请以调试模式配置 CMake 并照常运行测试。如果存在内存错误，您将看到内存错误报告。请注意，macOS 仅支持地址检测器而不支持泄漏检测器。

在某些情况下，地址检测器可能会影响调试器的可用性。在这种情况下，您可能需要通过以下方式配置 CMake 项目来禁用所有检测器：

$ cmake -DCMAKE_BUILD_TYPE=Debug -DBUSTUB_SANITIZER= ..

开发提示

您可以在调试模式下使用 BUSTUB_ASSERT 进行断言。请注意，BUSTUB_ASSERT 中的语句在发布模式下将不会被执行。如果您需要在所有情况下进行断言，请使用 BUSTUB_ENSURE 代替。

我们将以发布模式测试您的实现。要以发布模式编译您的解决方案，

$ mkdir build_rel && cd build_rel
$ cmake -DCMAKE_BUILD_TYPE=Release ..

请将关于本项目的所有问题发布在 Piazza 上。不要直接给助教发邮件提问。

助教在本项目中不会查看您的代码或帮助您调试。

评分标准

为了通过本项目，您必须确保您的代码遵循以下准则：

提交是否成功执行了所有测试用例并产生了正确答案？
提交是否在没有内存泄漏的情况下执行？
提交是否遵循了代码格式化和风格策略？

请注意，在未来的项目中，我们将使用额外的测试用例来评分您的提交，这些测试用例比我们提供给您的示例测试用例更复杂。

迟交政策

本项目没有迟交天数。

提交

您将把实现提交到 Gradescope：

https://www.gradescope.com/courses/1074751

在 build 目录中运行此命令，它将创建一个名为 project0-submission.zip 的 zip 归档文件，您可以将其提交到 Gradescope。

$ make submit-p0

虽然您可以随时多次提交答案，但您不应将 Gradescope 作为您唯一的调试工具。大多数学生在截止日期前提交项目，因此 Gradescope 将需要更长的时间来处理请求。您可能无法及时获得反馈来帮助您调试问题。此外，Gradescope 的输出不太可能像调试器（如 gdb）的输出那样提供有用的信息，前提是您花了一些时间学习使用它。

CMU 学生应使用在 Piazza 上公布的 Gradescope 课程代码。

协作政策

每位学生必须独立完成本次作业。
学生可以与他人讨论项目的高层次细节。
学生不允许在与其他学生的小组会议后复制白板上的内容。
学生不允许复制他人的答案。
学生可以使用生成式 AI 来辅助开发，但他们最终对自己的工作负责。

警告：本项目的所有代码必须是您自己的。您不得从其他学生或网上找到的其他来源复制源代码。抄袭行为绝不被容忍。更多信息请参见 CMU 的学术诚信政策。

项目 #0 - C++ 入门 最后更新：Aug 26, 2025

概述