CMU15445 (Spring 2023) #Project0
前言
写这篇文章,初衷是因为网上很少有关于CMU15445-2023的博客文章。记录下我在做的过程中走过的弯路,一方面是对自己工作的一个总结,另一方面也能帮助到在做这门课的 #project 时踩坑而无从下手的同学,何乐而不为?
一、你需要提前知道的
我使用的编译环境:
系统:Ubuntu 20.04.1
IDE:Clion
语法要求
- 掌握 基本C++11语法(C++Primer)
- 简单的 C++17语法,如:string_view
重点掌握
- dynamic_cast基本用法
- 智能指针的基本用法
二、四个Task
Task #1 - Copy-On-Write Trie
2023年的 #project0 实现与往年不同,实现的是一棵可持久化的字典树。
具体什么是可持久化的字典树,不建议上网搜索,网上的版本普遍和这个项目的版本有实现上的区别。
其实官方描述中写的较为清晰,建议反复阅读直到真正看懂再开始实践做题。
这一部分,我们要完成 Get、Put、Remove操作
建议先从 Get 入手,最简单。std::string_view 就是一个字符串视图,它支持size、begin、end、下标操作
Get ( ) 思路
我们沿着字符串找到最后的值节点。然后使用dynamic_cast
转换。dynamic_cast
允许指针安全地向下转换(即由基类转为派生类指针),失败则返回 nullptr 。但这里的问题是智能指针不支持这个转换,故我们使用智能指针的 get( ) 方法取得裸指针,然后再进行转换就好了。
接着写 Put
Put ( ) 思路
这里的关键在于阅读好官方对该方法的说明。我们在插入节点时,并非是在原Trie上插入节点,而是在搜索要插入节点的路径上不断 Clone( ),只有这样,我们才能得到非const的节点来对其children_进行操作。我的做法是使用多个指针进行维护,初始时两个指针都指向父节点,然后令一个指针下探进行操作,另一个指针不变,等操作完后更新父节点,再下探。
课程不给展示代码,我附一点点帮助大家理解并开头
std::shared_prt<TrieNode>cur = std::shared_ptr<TrieNode>(root_->Clone());
其次要意识到 Clone( ) 是得到一个全新的节点,我们需要记得将其与它的上一层节点连接
最后附一个想了很久的bug,我在网上找了很久没一个人提到…可能大家都默认了…
//B是A的派生类
//b是B类型的对象
std::shared_ptr<A> a = std::make_shared<A>(b);
看这个例子,我想当然的认为make_shared
会保留多态性质生成一个指向b的基类指针。然而事实是make_shared
会先截断b,只留下A部分的值,然后生成指针。在本题中就是TrieNodeWithValue会被截断为TrieNode,那就错了。
这样的bug非常难找,找到之后也很难绕过来,网上也找不到相关说明,非常折磨。
正确做法是std::shared_ptr<A> a = std::make_shared<B>(b);
更新一个例子
如下:最后分别打印 A B
#include <iostream>
#include <memory>
using namespace std;
class A{
public:
virtual void print() {
cout << "A" << endl;
}
};
class B: public A {
public:
void print() override {
cout << "B" << endl;
}
};
int main() {
shared_ptr<A> ptr1 = make_shared<A>();
shared_ptr<A> ptr2 = make_shared<B>();
ptr1->print();
ptr2->print();
}
最后写Remove
Remove( ) 思路
Remove的过程要意识到不只要删除规定节点。
原因: 如果规定节点的父节点只有这一子节点并且自己不是一个值节点,那么我们也需要顺带把它清理掉。这一过程是递归的,我们要从底往上一个一个清理直到遇到不能清理的。
Remove( ) 实现
这里我的做法是开一个 vector 记录路径节点避免递归,然后从最后向前迭代,按上面的做法删除节点。
顺便一提,const_cast
可以消除指针的const属性,可能有时候要用到。但如果你要大量使用之,无疑是你的设计出现了问题。这道题完全可以不用const_cast
完成。
Task #2 - Concurrent Key-Value Store
这一部分我们要完成并发条件下的读写。
这里不要想复杂了,关键在于好好体会可持久化字典树的优势,好好阅读官方文档。(上面有超链接)
思路
我们在这里完全不用读写锁,只需要两把互斥锁,但得益于可持久化字典树每一次 Put、Remove 都会生成一个新版本的字典树,我们天然地解决了读写者的问题。因为每一个线程的 Put、Remove 都是对新树操作,完全不会影响到别的线程上的 Get,Get 仍在读旧版本的字典树。
(这段可能编完就懂了)
实现
Get 在获取 root_ 时上锁
Put、Remove 对整个函数上锁
如果是C++11之后,请使用 std::page_guard
管理你的std::mutex
C++17之后可以使用std::scoped_lock
管理
我的笔记
写完前两个 Task,便理解可持久化的含义了。它保存了不同版本的字典树,而并非始终对同一棵字典树进行修改。
举个例子:字典树的一个使用场景就是平常我们使用搜索网站的搜索历史。我们每搜索一次就相当于创建一个新的叶结点。如下图:小明想学习C语言和C++,于是小明打开百度搜索这两个关键词,于是搜索历史形成了一个小字典树。其中圆形代表中间节点,正方形代表叶结点。
经过努力,小明速成了C语言,他决定将这个搜索记录删了,因为他认为自己已经掌握了C。于是字典树变成了最不想看到的链表状。
时间过得很快,一年后,小明发现自己已经把 C 忘光了,以至于他忘记自己学的语言是啥名字了,他想搜索可是不知道名字。更糟糕的是,这时他已经把字典树修改了,回不到过去的历史了,看来小明这辈子都学不会 C 语言了。于是,他在心中暗暗发誓:如果上天能给我再来一次的机会,我会对C语言说三个字:… …
但是,如果使用可持久化字典树,小明只需回调到上个版本即可,因为其可以保存每一次搜索的字典树!于是小明又可以愉快地继续学习了。他很感激可持久化字典树又给了他再来一次的机会。
Task #3 - Debugging
在 Clion 下,在配置里,课程已经写好了编译文件,直接选择对应的并调试即可
这里我 debug 出来是 8、1、42
答案是对的,但问题是这个结果依赖于随机数,评测系统生成出来的不是这三个数。
解决方法在这个大佬的文章里:这儿
Task #4 - SQL String Functions
比较简单,可以使用C++自带的算法:std::trannsform
。另外需要注意的就是返回异常类型时,不要使用std::exception()
。 项目里写了自己的Exception()
按要求构造就完事了。
三、评测注意
-
评测网站,官网上的FAQ中有写
-
不知道为什么我在 cmake 时安装clang-format-14失败,最后我是先用clang-format-12改一遍,再上交的。如果安装失败的话,可以写完直接上交到评测网站,它会有一个文件详细的列出哪些地方不合规范,照着改就好了。
-
只有格式对了,才会开始打分,否则一律0分!
四、总结
期中考试期间断断续续写完这个 project 感觉收获不少,尤其是智能指针,总的来说体验还是不错滴!
附上评测
五、最后
一起加油!
遇到bug的 直接评论区问 我看到都会尝试解答文章来源:https://www.toymoban.com/news/detail-485053.html
文章来源地址https://www.toymoban.com/news/detail-485053.html
到了这里,关于CMU15445 (Spring 2023) #Project0的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!