MizukiCry's Blog

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

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 函数替代循环，然而真用了也没感觉有多简洁（？） 1234567891 ...

Homework #1 - SQL 对 Lecture #02: Advanced SQL 的一个简单测试，使用 SQLite 练习 SQL 语句。 Ubuntu 安装 SQLite：sudo apt-get install sqlite3 根据 Homework 界面下载数据集并进行配置，需要用到的 relations 结构如下： 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 1 ...

在线测试需要使用 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++ 的智能指针用着怪难 ...

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：一个无序集合，可以看成一个 \(n\) 列的表（n-ary relation），每一列对应一种属性（attributes / keys） Tuple：一个 \(n\) 元组，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 = ["m ...

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

前言 在 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 创建线程，头文件 <thread> 先来看个简单的例子： 123456789101112131415161718192021222324252627282930313233343536373839 ...

其实都是照着抄的 Chapter 1 样本空间与概率 1.3 条件模型 条件概率：\(P(A|B)=\frac{P(A\cap B)}{P(B)}\) 乘法定律：\(P(AB...)=P(A)P(B|A)...\) 1.4 全概率定理与贝叶斯准则 \(A_1...A_n\) 为样本空间的一个分割，则： 全概率定理：\(P(B)=\sum_i P(A_i\cap B)=\sum_i P(A_i)P(B|A_i)\) 贝叶斯准则：\(P(A_i|B)=\frac{P(A_i)P(B|A_i)}{P(B)}=\frac{P(A_i)P(B|A_i)}{P(A_1)P(B|A_1)+...+P(A_n)P(B|A_n)}\) 1.5 独立性 事件 \(A, B\) 独立：\(P(A\cap B) = P(A)P(B)\) 条件独立：\(P(A\cap B|C)=P(A|C)P(B|C)\) Chapter 2 离散随机变量 2.2 分布列 分布列：\(p_X(x)=P(\{X=x\})\) 两点分布（伯努利）：\(B(1,p),E=p,var=p(1- ...

基础概念 系统调用 fork 1234/// 功能：当前进程 fork 出来一个子进程（除返回值外状态机相同）。/// 返回值：对于子进程返回 0，对于当前进程则返回子进程的 PID 。/// syscall ID：220pub fn sys_fork() -> isize; waitpid 1234567/// 功能：当前进程等待一个子进程变为僵尸进程，回收其全部资源并收集其返回值。/// 参数：pid 表示要等待的子进程的进程 ID，如果为 -1 的话表示等待任意一个子进程；/// exit_code 表示保存子进程返回值的地址，如果这个地址为 0 的话表示不必保存。/// 返回值：如果要等待的子进程不存在则返回 -1；否则如果要等待的子进程均未结束则返回 -2；/// 否则返回结束的子进程的进程 ID。/// syscall ID：260pub fn sys_waitpid(pid: isize, exit_code: *mut i32) -> isize; 在一个子进程结束后通常由父进程调用 waitpid 回收资源并获取返回值。 若 ...