MizukiCry's Blog

Project #2 - B+Tree Task #1 - B+Tree Pages 这一部分没什么好说的，把他给的函数写出来就行，基本都是一两行的事 Task #2 - B+Tree Data Structure (Insertion, Deletion, Point Search) 逆天 Task 之一 B+Tree 这东西看着原理简单，在内存池上写起来怪恶心的 比较简单的是查找，直接顺着往下定位到叶子节点就行。关于每个节点上的定位可以直接遍历或者二分定位。我用的二分，不过估计效率差别不大，瓶颈不应该在这一块 至于插入，最好先画个图仔细想清楚再写，不然就会向我一样改了好几版，10 天才摸出来这个 Task，感觉 DSA 白学了（ 我在向上更新的时候用的递归，感觉比较好理解。需要注意 Split 时也要更新子节点的 parent_page_id 然后是删除。因为课件讲得不是很细致，有些细节也稍微卡了一会。在 Merge 时需要给右边节点的第一个子节点增加一个对应的 Key，这个 Key 可以直接取父节点对应的...

背景故事什么的没有。 Bloom Filter 布隆过滤器 用于判断集合中是否存在某个值，但有可能误判（将不存在判断为存在） 原理类似 Hash Table，开一个大小为 nnn 的 bitset，设计 kkk 个 Hash 函数，插入元素时将 bitset 中 Hash 值对应的位设为 111。查询时若 kkk 个位置均为 111 则认为存在。 优点：内存占用小，时间复杂度稳定 O(k)O(k)O(k) 缺点：不能删除（如果需要删除可以将 bitset 改为普通计数数组，但这样内存优势就不大了），存在误判 Bloom Filter Arguments Analysis 考虑插入 mmm 个元素后，某个位置为 111 的概率为 p1=1−p0=1−(1−1n)mk≈1−e−mknp_1 = 1 - p_0 = 1 - (1 - \frac1n)^{mk} \approx 1 - e^{-\frac{mk}{n}} p1​=1−p0​=1−(1−n1​)mk≈1−e−nmk​ 其中用到 lim⁡n→+∞(1−1n)−n=e\lim\limits_{n\rightarrow...

Project #1 - Buffer Pool Project 目标：实现一个线程安全的 buffer pool，用于在硬盘和内存之间移动数据 Task 分为三部分： Extendible Hash Table LRU-K Replacement Policy Buffer Pool Manager Instance 可以使用 C++17 的一些容器辅助（但注意 STL 容器不是线程安全的） Task #1 - Extendible Hash Table 实现一个可以自动扩张的线程安全 Hash Table 这里的 Extendible Hashing 指的是课件中的算法，不是单纯的可扩张，一开始看代码还没看懂 感觉课件上不是特别清楚，附一篇知乎文章 话说阅读框架好痛苦，经常对不上电波（ 首先是 Bucket 的实现，没什么难点 因为 Bucket 只供 ExtendibleHashTable 调用，不需要考虑多线程问题 clang-tidy 经常提示用 STL...

Homework #1 - SQL 对 Lecture #02: Advanced SQL 的一个简单测试，使用 SQLite 练习 SQL 语句。 Ubuntu 安装 SQLite：sudo apt-get install sqlite3 根据 Homework 界面下载数据集并进行配置，需要用到的 relations 结构如下： Q1 一个例子，没有分数，直接给了答案 但恕我没有看懂这 Details 和 Answer 怎么完全对不上 不影响，直接交就完事了 1234SELECT DISTINCT(language)FROM akasORDER BY languageLIMIT 10; Q2 12345SELECT primary_title, premiered, runtime_minutes || ' (mins)'FROM titlesWHERE genres LIKE '%Sci-Fi%'ORDER BY runtime_minutes DESCLIMIT 10; 话说既然 Gradescope...

在线测试需要使用 Gradescope，使用课程提供的课程码 PXWVR5，学校填 Carnegie Mellon University，Student ID 不需要。 Project #0 - C++ Primer 既然这门课用的 C++，那么就需要考察学生的 C++ 水平。CMU 15-445 的要求：C++17, GDB。 鉴于课程使用的工具，最好在 Linux 下做此课程实验。 首先需要 clone 一份 CMU 的 bustub（需要去 Release 手动下载 Fall2022 版本，或者手动 reset 到对应的 commit d830931a9b2aca66c0589de67b5d7a5fd2c87a79，否则内容对应不上）。 Task #1 - Templated Trie 在原有模板上实现一颗 Trie 树。 没什么好说的，只要知道 Trie 树是个什么东西就行了，直接模拟，总共就几十行代码。 在写的时候可能遇到的主要问题：不会用智能指针等现代 C++ 内容，只能边查边写，多用用就会了。 （不过我一直感觉 C++ 的智能指针用着怪难受的，Rust...

CMU 15-445 DBS Fall2022 开新坑.jpg 抄了抄之后感觉不如直接看提供的 Notes（ 就当是强迫自己看课件用的 Lecture #01: Course Overview & Relational Model 通用数据管理系统（DBMS, Database Management System）：支持定义、创建、查询、更新、管理。 Data model：数据模型，描述数据的概念的集合 Schema：模式，指定数据模型下对一类特定数据的描述 本课程重点：关系模型（Relational Model） 将数据存放在简单结构中（relations） 通过高级语言访问数据，由 DBMS 决定最佳方案 存储方式由 DBMS 实现 Relation：一个无序集合，可以看成一个 nnn 列的表（n-ary relation），每一列对应一种属性（attributes / keys） Tuple：一个 nnn 元组，relation 中的每一行就是一个 tuple Primary key：主键，在 relation 中可以唯一确定一个...

Bazel 是由 Google 开源的一款构建工具，支持 C++ 等多种语言 我个人是不喜欢 CMake 或者 GNU Make 的，感觉语法太丑了（？） 最近看了几个项目用的都是 Bazel，看起来语法似乎还行？对我 xp 于是打算简单学一下，记录一点常见用法以后好抄 安装 对 Windows 系统，直接按照官网方法下载即可，也可以去 Github 上下载二进制文件自己配置环境变量。 如果在 VSCode 中使用了 Bazel 插件，似乎还要另外下载 buildtools 文件结构 想要使用 Bazel，只需在项目的根目录下新建一个 WORKSPACE 文件即可。 在项目中在不同地方会有一个或多个 BUILD 文件，用于表示项目的不同模块。 一个例子： 12345> project > src - main.cpp - BUILD - WORKSPACE 然后在 BUILD 文件中写上相应的配置： 1234cc_binary( name = "main", srcs =...

前言 之前在 b 站上刷到了影视飓风的 “扫雷，但是是真人3D版！” 这个视频，总之很有感觉！ 开始想着能不能直接用 UE5 复现一个，不过自己也没有那个能力，但是对扫雷的地图生成算法产生了一些兴趣。高中的时候经常和同学在 seewo 上面多开扫雷，当扫雷地图大了之后总遇到需要猜的死局，虽然后来在网上找到了一个可以生成绝对有解地图的扫雷，不过当时并没有想明白原理，正好这次尝试一下。 扫雷基本定义与规则 游戏初始局面为一块 n×mn\times mn×m 的矩阵，每一格都是未知的，玩家可以点击打开格子，若格子下是雷则游戏结束（一般保证第一次点击不是雷），否则格子下会出现一个数字，代表此格周围 888 格中的地雷数。若周围没有雷则会递归打开周围的 888 个格子。 而因为机制问题，有时候会出现因为条件不够需要猜测的局面。针对此衍生出了几种不同的玩法，详见下图（Source）： 部分玩法的在线试玩： Kaboom Simon Tatham’s Mines 扫雷问题求解 先来看看如何对指定的局面进行求解。 首先需要明确的是，扫雷的求解是一个 NP-Complete...

前言 在 C++ 11 之前，C++ 标准库并没有提供内置的多线程支持，实现多线程编程通常需要引入外部第三方库，Linux 上常用 pthread.h（POSIX Threads），而 Windows 上则需要调用 Windows API，可以使用 pthreads-win32 库或 Boost.Thread 库来实现，跨平台非常麻烦。在 C++ 11 中引入了官方的多线程库 <thread>，大大方便了代码的编写。 不过如果在 Windows 上使用 MinGW-GCC 的话，若根据网上的旧教程使用 MinGW 8.1.0 版本的话需要注意安装时选择 Posix 而非 Win32，否则 <thread> 不完整，推荐去 Github 下载最新版。 std::thread 在 C++ 11 中使用 std::thread 创建线程，头文件...

其实都是照着抄的 Chapter 1 样本空间与概率 1.3 条件模型 条件概率：P(A∣B)=P(A∩B)P(B)P(A|B)=\frac{P(A\cap B)}{P(B)}P(A∣B)=P(B)P(A∩B)​ 乘法定律：P(AB...)=P(A)P(B∣A)...P(AB...)=P(A)P(B|A)...P(AB...)=P(A)P(B∣A)... 1.4 全概率定理与贝叶斯准则 A1...AnA_1...A_nA1​...An​ 为样本空间的一个分割，则： 全概率定理：P(B)=∑iP(Ai∩B)=∑iP(Ai)P(B∣Ai)P(B)=\sum_i P(A_i\cap B)=\sum_i...