CMU15445 (Spring 2023) #Project0

这篇具有很好参考价值的文章主要介绍了CMU15445 (Spring 2023) #Project0。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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++,于是小明打开百度搜索这两个关键词,于是搜索历史形成了一个小字典树。其中圆形代表中间节点,正方形代表叶结点。
CMU15445 (Spring 2023) #Project0
经过努力,小明速成了C语言,他决定将这个搜索记录删了,因为他认为自己已经掌握了C。于是字典树变成了最不想看到的链表状。
时间过得很快,一年后,小明发现自己已经把 C 忘光了,以至于他忘记自己学的语言是啥名字了,他想搜索可是不知道名字。更糟糕的是,这时他已经把字典树修改了,回不到过去的历史了,看来小明这辈子都学不会 C 语言了。于是,他在心中暗暗发誓:如果上天能给我再来一次的机会,我会对C语言说三个字:… …
但是,如果使用可持久化字典树,小明只需回调到上个版本即可,因为其可以保存每一次搜索的字典树!于是小明又可以愉快地继续学习了。他很感激可持久化字典树又给了他再来一次的机会。

Task #3 - Debugging

在 Clion 下,在配置里,课程已经写好了编译文件,直接选择对应的并调试即可
这里我 debug 出来是 8、1、42
答案是对的,但问题是这个结果依赖于随机数,评测系统生成出来的不是这三个数。
解决方法在这个大佬的文章里:这儿

Task #4 - SQL String Functions

比较简单,可以使用C++自带的算法:std::trannsform。另外需要注意的就是返回异常类型时,不要使用std::exception()。 项目里写了自己的Exception() 按要求构造就完事了。


三、评测注意

  1. 评测网站,官网上的FAQ中有写

  2. 不知道为什么我在 cmake 时安装clang-format-14失败,最后我是先用clang-format-12改一遍,再上交的。如果安装失败的话,可以写完直接上交到评测网站,它会有一个文件详细的列出哪些地方不合规范,照着改就好了。

  3. 只有格式对了,才会开始打分,否则一律0分!

四、总结

期中考试期间断断续续写完这个 project 感觉收获不少,尤其是智能指针,总的来说体验还是不错滴!

附上评测
CMU15445 (Spring 2023) #Project0

五、最后

一起加油!
遇到bug的 直接评论区问 我看到都会尝试解答

CMU15445 (Spring 2023) #Project0文章来源地址https://www.toymoban.com/news/detail-485053.html

到了这里,关于CMU15445 (Spring 2023) #Project0的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【cmu15445c++入门】(8)C++ 智能指针unique_ptr

    智能指针是一种数据结构,用于没有内置内存管理的语言(例如 C++)中的内存管理(有时还有其他功能)。内置内存管理的语言的指的是具有垃圾回收功能的语言,如Java、Python。 现代C++标准库的两个智能指针(以及您将在类中使用的智能指针)是 std::unique_ptr 和 std::shared_

    2024年02月20日
    浏览(43)
  • 【CMU15-445数据库】bustub Project #0:Trie 树实现(C++ Primer)

    第 0 个 Project 名为 C++ Primer,目标是实现一个字典树(Trie),内容不难,主要是测试参与者的 Modern C++ 编程水平,对于选课的 CMU 学生如果感觉比较吃力可能就要劝退了。 Project 说明:Project #0 - C++ Primer 本节要实现的内容全部在 src/include/primer/p0_trie.h 文件中。 字典树(Trie)是

    2024年02月04日
    浏览(36)
  • 缓存替换策略:LRU-K算法详解及其C++实现 CMU15-445 Project#1

    CMU 15-445 (FALL 2022) Project #1 Task#2 LRU-K 替换策略详解实现,尽量提供思路,也可以为其他同学实现LRU-K算法做参考 参考文献:The LRU-K page replacement algorithm for database disk buffering (acm.org) 在网上都找不到其他参考,只有这一篇1993年的论文 LRU-K替换策略 LRU-K是LRU算法的一种衍生。强烈

    2023年04月12日
    浏览(35)
  • 从零开始学Spring Boot系列-前言

    在数字化和信息化的时代,Java作为一种成熟、稳定且广泛应用的编程语言,已经成为构建企业级应用的首选。而在Java生态系统中,Spring框架无疑是其中最为耀眼的一颗明星。它提供了全面的编程和配置模型,用于构建企业级应用。随着Spring Boot的出现,这一框架变得更加易于

    2024年02月22日
    浏览(56)
  • 性能比较 - Spring Boot 应用程序中的线程池与虚拟线程 (Project Loom)

            本文比较了 Spring Boot 应用程序中的不同请求处理方法:ThreadPool、WebFlux、协程和虚拟线程 (Project Loom)。         在本文中,我们将简要描述并粗略比较可在 Spring Boot 应用程序中使用的各种请求处理方法的性能。         高效的请求处理在开发高性能后端应

    2024年02月12日
    浏览(38)
  • 报错 Project ‘org.springframework.boot:spring-boot-starter-parent’ not found 的解决办法

    先上图:  引入spring-boot-starter-parent 依赖的时候总是会有报错。 网上大多数办法都说是maven的问题,但是maven的配置明明没有问题但还是会报错。 那么有可能是缓存的原因,可以清理一下idea的缓存。 如下:  点击图中高亮的选项  选择图中的Inavalidate and Restart  问题解决。

    2024年02月13日
    浏览(115)
  • Idea新建spring Initializr项目时选择Project SDK为1.8,选择java版本只有是17和21,出现报错信息

    1.项目构建图展示: 2.报错图展示: 3.原因说的很清楚了,是java版本和jdk版本不符合导致的 4.解决方案 改为阿里云的服务器路径: https://start.aliyun.com 5.测试 这时候就有了java8的版本了

    2024年01月17日
    浏览(43)
  • 解决 Spring Boot 和 Gradle Java 版本兼容性问题:A problem occurred configuring root project ‘demo1‘. > Could n

    🌷🍁 博主猫头虎 带您 Go to New World.✨🍁 🦄 博客首页——猫头虎的博客🎐 🐳《面试题大全专栏》 文章图文并茂🦕生动形象🦖简单易学!欢迎大家来踩踩~🌺 🌊 《IDEA开发秘籍专栏》学会IDEA常用操作,工作效率翻倍~💐 🌊 《100天精通Golang(基础入门篇)》学会Golang语言

    2024年02月04日
    浏览(56)
  • CMU 15-445 -- Logging Schemes - 17

    本系列为 CMU 15-445 Fall 2022 Database Systems 数据库系统 [卡内基梅隆] 课程重点知识点摘录,附加个人拙见,同样借助CMU 15-445课程内容来完成MIT 6.830 lab内容。 数据库在运行时可能遭遇各种故障,这时可能同时有许多正在运行的事务,如果这些事务执行到一半时故障发生了,就可能

    2024年02月15日
    浏览(31)
  • CMU-TARE 探索算法官方社区问答汇总

    参考引用 TARE机器人自主导航系统社区-CSDN社区云 TARE平台资源链接汇总 CMU团队的terrainAnalysis地形分析代码笔记 Local Planner 代码详解以及如何适用于现实移动机器人 论文翻译:Autonomous Exploration Development Environment and the Planning Algorithms Tare planner系列代码解析 首先感谢 CMU 团队的

    2024年04月26日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包