tzyt的博客

题目链接 博客中观看体验更佳 分析 题意非常简洁，即问你通过一系列的字符替换，最少花多少步能把一个 sss 串变成 ttt 串。 拿到题之后，可以先从样例开始分析。 从 BBC→ABC\texttt{BBC} \to \texttt{ABC}BBC→ABC 这个样例可以发现，不可能同时把某个字符替换成两个字符（BB→AB\texttt{BB} \to \texttt{AB}BB→AB），会起冲突。 那直接统计 si≠tis_i \ne t_isi​=ti​ 的个数（给串去重之后，即不存在 s=AA,t=BBs = \texttt{AA}, t = \texttt{BB}s=AA,t=BB 这种）就可以作为答案了吗？可以从最后一个样例发现不是这样的。 环的处理 因为最后一个样例中，CD\texttt{CD}CD 的部分是一样的。我们直接考虑 AB→BA\texttt{AB} \to \texttt{BA}AB→BA 的变换。如果直接执行 A→B\texttt{A} \to \texttt{B}A→B 的操作，会得到一个 BB\texttt{BB}BB 的串。这个时候就有了和前面一样的问 ...

代码实现 TCP 状态流转图 Lab4 的主要作用是把前面的 receiver 和 sender 结合起来，形成一个完整的 TCP 协议栈。所以熟悉 TCP 的状态流转图就很重要了。 下面是一个 TCP 的状态流转图： TCP 连接的建立 参考上图，可以看到 TCP 有两种建立连接的方法。第一种是主动连接，即给对方发送一个 SYN 包。第二种是被动连接，即接收到一个 SYN 包后，回复 SYN+ACK 包。 主动连接 对于主动连接，我们需要实现 connect() 函数： void TCPConnection::connect() { _shutted = false; _sender.fill_window(); send_sender_segs(); } 这里的 shutted 变量表示连接是否已经关闭，之后在 active() 函数中使用。因为我们之前实现过 TCPSender 的 fill_window() 函数，它会记录连接是否已经建立，如果没有会自动发送 SYN 包。 不过 TCPSender 的 fill_window() 仅 ...

注：因为实验指导书和课程文件[1]里都明确的写了不能公开代码，所以博客上的实验记录就主要记录思路以及一些核心代码片段，不会公开完整的仓库。 Lab0 networking warmup Lab 要求实现一个在内存层面上可靠的字节流（ByteStream），感觉和 unix 中的管道挺像的。其实这样先进先出的结构完全可以直接使用 STL 的 queue<char> 实现，会非常简单。但是考虑到 lab 的要求是一个固定大小（capacity）的字节流，个人认为直接开个数组模拟更合适，速度也应该会更快。 具体来说，就是开一个 string（没有直接使用字符数组是因为实验指导书提到了最好使用现代 C++ 的风格，避免使用 new 来手动分配内存）来储存数据，以及一个头指针和尾指针指向字节流的开始和结尾。这样就实现了一个环形队列，peek_output() 函数的实现大概是下面这样的： string ByteStream::peek_output(const size_t len) const { size_t peek_size = min(buffer_siz ...

吐槽一下，官方题解写的挺难看懂的，看了好久还是挺迷糊的（其实也是我太菜了）。搞懂之后感觉这题挺妙的，来写下题解。 思路 我们首先需要有一个观察，就是对于 sss 串，最后一个连续字串不会增加可能的获胜人数。比如 s=0011s = \texttt{0011}s=0011 时，后面结尾的 11\texttt{11}11 就不会增加可能的获胜人数。 为啥呢，设我们设经过任意次数对战后，玩家可能组合的集合为 ttt 那么对于任意的 x∈tx \in tx∈t，连续在环境 111 中对战任意次数后，最终的赢家一定是 xxx 中温度最高的（因为每个剩下的玩家都会需要连续在环境 111 中对战，唯一能胜出所有对战的玩家一定是最大的）。同理，ttt 中的玩家连续在环境 000 中对战任意次数后，最终的赢家一定是 xxx 中温度最低的。 例如，s=111s = \texttt{111}s=111 时，最后胜出的一定是 444 号玩家。 这样一来，如果结尾段是 111（000 结尾同理，后面为了方便先用 111 的例子了），我们只需要算出前面的部分最多能构造出多少种最大值（玩家温度）不同的玩家组合，就能 ...

upd@2022/11/5：添加了具体实现，修正了推导中的一些符号错误 反向传播算法的主要目的是计算出神经网络中误差对于偏置和权重等参数的偏导数，以此来进行梯度下降。本文的上半部分主要是算法的推导，后半部分使用全连接神经网络和 mnist 数据集实现手写数字识别。 这个算法对我来说还是很难理解的，为了防止自己忘掉，就写了这篇笔记（还有就是神经网络里这些公式的上标下标太多了，如果用真的笔记本写，稍微一不小心就写错了）。如果你对神经网络还没有基本的概念，推荐去看 3b1b 的神经网络系列视频 这里必须说一句 MqCreaple 大佬真的太巨了，看了视频之后直接手推了全部的公式更令人震惊的是居然把我这种人教会了。 公式推导 符号和语言约定 σ(){\sigma()}σ() 表示激活函数 EEE 表示最终误差 err⁡()\operatorname{err}()err() 表示误差函数 y^\hat{y}y^​ 表示神经网络给出的预测值，而 yyy 表示实际的答案 lll 表示神经网络的层数，值越小代表离输入层越近 wji[l]w^{[l]}_{ji}wji[l]​ 表示一条从 lll 层 ...

一个多月终于断断续续搞完了第二本书里的内容。和前面两篇文章一样，这篇也会写一些我个人花了较长时间才搞懂的部分，以及一些我在原书基础上加的新功能。 对于原书就有的功能，会直接使用书上的代码，如果是我新加进去的功能，会使用自己的代码。因为我的代码在原书基础上做了较大幅度的变化（即使是原来就有的功能），所以只看一段代码可能不太明白，这里可以参考我的 GitHub 仓库： https://github.com/ttzytt/RTOW bvh_node 这部分主要是一些小细节我当时没太理解。首先是 bvh_node::bvh_node( std::vector<shared_ptr<hittable>>& src_objects, size_t start, size_t end, double time0, double time1 ) 首先是这个构造函数的范围问题。每颗子树是不负责 end 位置的 hittable 的。也就是这个构造函数负责的是 [start, end) 这样的一个区间。 这也解释了代码中 sort 的用法： std::sort(obje ...

相机类的实现 除了朗伯体，RTOW 中还有个比较有趣的地方就是相机类的实现，特别是背景虚化这部分。 相机的定位 先来看一下相机类里一个相对简单的部分–相机的定位。只要通过三个参数就能确定相机的位置，分别是相机本身的位置（lookfrom），相机正在拍摄的位置（lookat）和表示相机上方位置的向量（vup），书里的图就能很好的解释： 在构造函数中，我们需要把这三个参数转换成表示相机朝向的三个参数，以及做一些对焦距，光圈和 fov 的处理，书中没有在这部分花很多的篇幅，我当时想明白也花了挺久的，下面是我对书中实现的一些思考。 因为我对书中的代码稍作了一些修改（主要是命名？）所以先贴一下代码： #pragma once #include "rtow.h" // 这里的 f8 就是 double （八个字节的 float） class camera { public: camera(vec3 lookfrom, vec3 lookat, vec3 vup = vec3(0, 1, 0), f8 vfov = 90, f8 asp_ratio ...

最近（距离搞完 RTOW 已经过去一周了，我现在才把这笔记写出来，属实是懒狗）花了一些时间看完了 Ray Tracing in One Weekend （以下简称 RTOW）果然还是我太菜了，这玩意 One Weekend 没搞完，也跟着把代码写出来了。 本书写的非常不错，最后渲染出的效果也是出乎我的意料（封面图）。但是因为我以前对计算机图形学没有任何的认识，很多基本的知识都不了解。 而书上有时会把这些基本知识（或者数学推导和证明）一笔带过，因此准备写个博客把自己的思考过程写一下。 朗伯体材质 （Lambertian） 的实现 在书中，创建一个朗伯体漫反射材质的方法是下面这样： class lambertian : public material { public: lambertian(const color& alb) : albedo(alb) {} virtual optional<pair<ray, color>> get_ray_out(const ray& r_in, c ...

upd@2022/9/14：最近把实验的代码放到 github 上了，如果需要参考可以查看这里： https://github.com/ttzytt/xv6-riscv 里面不同的分支就是不同的实验。 最后一个 lab 了，终于搞完了！！ Lab11: mmap 描述 实现一个 UNIX 操作系统中常见系统调用 mmap() 和 munmap() 的子集。此系统调用会把文件映射到用户空间的内存，这样用户可以直接通过内存来修改和访问文件，会方便很多。 mmap() 的定义如下： void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset); 意思是映射描述符为 fd 的文件，的前 length 个字节到 addr 开始的位置。并且加上 offset 的偏移量（即不从文件的开头映射）。 如果 addr 参数为 0，系统会自动分配一个空闲的内存区域来映射，并返回这个地址。 在实验中我们只需要支持 addr 和 offset 都为 0 的情况，也就是完全不用考虑用户指定内 ...

upd@2022/9/14：最近把实验的代码放到 github 上了，如果需要参考可以查看这里： https://github.com/ttzytt/xv6-riscv 里面不同的分支就是不同的实验。 Lab10: file system Large files 描述 在 xv6 的底层实现中，文件是由 struct dinode 来描述的，如下： struct dinode { short type; // File type short major; // Major device number (T_DEVICE only) short minor; // Minor device number (T_DEVICE only) short nlink; // Number of links to inode in file system uint size; // Size of file (bytes) uint addrs[NDIRECT + 1 ...

upd@2022/8/18: 本文的第二个实验不完全正确，并且还有很多其他的做法，具体可以见这篇博客中我和博主的讨论。以及博主根据讨论新写的代码。 如果接下来有时间，会把第二部分的代码改掉并添加注释。 upd@2022/9/14：最近把实验的代码放到 github 上了，如果需要参考可以查看这里： https://github.com/ttzytt/xv6-riscv 里面不同的分支就是不同的实验。 Lab9: locks Memory allocator 实验描述 这 lab 的描述也是非常长，所以就不截图了。下面描述一下大概的题意： 在原本的 kalloc() 中，只有一个大锁，我们会维护一个 freelist 链表，如果有任何程序申请内存，都需要竞争 freelist 的锁，以修改 freelist 的内容。具体可见 freelist 和 kalloc() 的实现： struct run { struct run *next; }; struct { struct spinlock lock; struct run *freelist ...

upd@2022/9/14：最近把实验的代码放到 github 上了，如果需要参考可以查看这里： https://github.com/ttzytt/xv6-riscv 里面不同的分支就是不同的实验。 Lab8: Networking 这个 lab 的描述属实是长，不过很多的篇幅都在介绍 E1000 网卡。最终的任务其实很简单，就是实现 E1000 网卡驱动中的 transmit() 和 recv() 函数。 这个 lab 的代码不复杂，但写出来需要对 lab 中的提示有很好的理解。同时，也需要查阅 E1000 的文档。 下面先介绍处理器和 E1000 交互的方法，随后再介绍两个函数的具体实现方法。 E1000 的交互方法 E1000 使用了 DMA（direct memory access）技术，可以直接把接收到的数据包写入计算机的内存，这在数据量大的时候非常有用，可以当作缓存。 在发送时也可以把描述符（见下文）写入内存的特定位置，这样 E1000 就会自己去找到待发送的数据，然后发送。 不管是接收还是发送，数据包都是以描述符数组描述的。在下面的接收和发送部分，会分别介绍接收描述符 ...