Yuchen You

背景 在编译 C 或者 C++ 文件的时候，我们都会用到链接这一步骤，即 预处理 - 编译 - 汇编 - 链接 四个步骤 我们已经学过了汇编了，那么接下来就该了解一下什么是 linking 了 什么是链接 在汇编中，我们一般是每一个 c/cpp 文件生成一个 汇编代码文件 (obj file, 扩展名 .o)，那么，如果存在跨文件的变量，汇编怎么知道这个变量是来自哪里的呢？ 首先我们联想在编译的时候 (compile time) 我们会在项目编译的内存空间中创建一个格式为 text - data - heap - stack 的空间结构(这里说的不恰当，应该说 compile time 分配的 text - data 空间)，那么类似的，对于每个源文件生成的汇编码，我们都要用一个表来记录全局变量的引用 cross−refcross-refcross−ref 以及外来方法 (即函数) 的对应引用 obj 文件的内容 上述两个表格会在编译的过程中存储在 .o 文件中，因此 obj 文件的格式会表现为: Header - Text - Data - Symbol Table - Reloc ...

排课问题 假设开学季的某一个下午多个社团都想要占用霍体开设招新活动，每个活动的时间长度各不相同且开始和结束的时间都各不相同，那么，学校方希望能尽可能多的开设活动，而并不考虑总活动时长的影响因素 最早结束时间算法 Earliest Ending Time EET 将这些活动按照时间结束的早晚进行排序，然后选中最前面那个，然后去除所有重叠的活动，然后递归选取下一个 选择的可靠性 (safe) 我们需要证明我们选择的这个活动确实是能带来最多活动数量的，或者用数学术语来说，存在最优解集 IOPTI_{OPT}IOPT​, 我们要证明 我们选择的 first ends I∈IOPTI \in I_{OPT}I∈IOPT​ 由于根据定义，结束时间 end(I)≤end(IOPT)end(I) \le end(I_{OPT})end(I)≤end(IOPT​) 那么由于 IOPTI_{OPT}IOPT​ 的下一个元素开始时间一定晚于当前的结束时间，所以 end(I)<start(IOPT,next)end(I) < start(I_{OPT, next})end(I)<start( ...

二维连续变量条件空间理解 假设我们有两个变量 X,YX, YX,Y, 存在一定的概率密度函数 fXY(x,y)f_{XY}(x,y)fXY​(x,y) 来表示在 X=x,Y=yX = x, Y = yX=x,Y=y 情况的概率密度 这个图像在 xyfxyfxyf 三维坐标下表现为 一个 f∈(0,1)f\in(0,1)f∈(0,1) 的一个曲面 其和 f=0f = 0f=0 平面形成的体积为 1 有效坐标 support 我们称 坐标 (x,y)(x,y)(x,y) fXY(x,y)>0f_{XY}(x,y) > 0fXY​(x,y)>0 为有效坐标，也就是在这个坐标上有可能发生事件 边界概率 marginal probability 如果我们想知道某一个变量的概率密度分布，那么我们就需要将这个二维曲面压缩到一维曲线上 例如我们想知道 fXYf_{XY}fXY​ 转变成 fXf_XfX​ 的形状，那么我们就可以将 y 坐标压缩到 x 轴上，也就是将 所有 y 的可能性都累加起来保存到 x 上，公式表达为: fX(x)=∫−∞∞fXY(x,y)dyf_{X}(x) = ...

概率密度函数的变化 假设原函数为 fX(x)={2x,0<x<10,o.w.f_X(x) = \begin{cases}2x &, 0 < x < 1\\ 0 &, o.w.\end{cases}fX​(x)={2x0​,0<x<1,o.w.​ 那对于随机变量 U=3X+1U = 3X + 1U=3X+1 我们如何计算 UUU 的概率密度函数呢？ 首先我们可以尝试将 x 直接变成 uuu 得到 x=u−13x = \frac{u - 1}{3}x=3u−1​ 从而直接带入公式求分布 但是这样其实忽略了一个问题: x→ux \to ux→u 的变换发生了拉伸以及偏移，所以其概率曲线可能是微微变形的 原函数，但是其归一性可能已经不满足了 因此我们直接从 最满足归一性 的 c.d.f 入手 （因为非线性变换之后可能我们不能用除以全积分归一来简单求解）我们使用 fU=dduFU(u)f_U = \frac{d}{du}F_U(u)fU​=dud​FU​(u) 而这里c.d.f 用的是 FU(u)=P[U≤u]=P[3X+1≤u]=P[X≤u ...

堆 我们将一棵树变得更加特别，即限制其必须为完整的，即每一个树的层级都是满的，除了最后一层。 然后，我们联想生活中的常见的堆型结构：稻草堆，其特征是上小下大，那么，我们就可以定义数据结构中堆的特性：具有一定的偏序关系(优先级)，且根节点的值总是该偏序关系的一端。 堆的节点关系 堆在内存中存储为一个 array 的形式，假设当前节点的 index 为 i (假设根节点 id = 1): 父节点 i / 2 左子节点 2i 右子节点 2i + 1 是否为叶节点 return (2 * i > n) 大顶堆的实现 fixUp() 当我们向一个堆进行插入元素操作，那么我们需要保证堆的特性，即根节点的值总是最大的。我们可以通过将新插入的元素与其父节点进行比较，如果新插入的元素大于其父节点，那么我们就将新插入的元素与其父节点进行交换，直到新插入的元素不再大于其父节点。 这个操作的结果是 将新的堆变成符合 父节点大于子节点的属性，且根节点一定是顺序最高的 fixDown() 当我们删除堆顶的元素的时候，我们需要将下面的元素逐个选择大的向上填充，那么我们就需要进行 fixDown() 操作， ...

内存指令集 memory instructions word 单词 表示几个字节的组合，在 lc2k 以及 arm 中，一个 word 通常是 4 个字节 32 位 有些地方写的 double word 就表示 8 字节 注意这里的 word 并不等于 char 之类的字符命令，只是一个长度单位，也可以用于指代长度 4 字节的 int 可寻址性 addressable lc2k 指令集架构下，word 是可寻址的，也就是说，每个地址会指向内存中某个特定的 word，同时这也要求在 lc2k 的内存中 指令必须每 4 字节对齐一次，或者说PC 等指针在内存中的移动长度单位是 4 字节 移动 1 字节（比如 1 char）是非法的 相比较下， ARM 架构是 byte addressable，即每个地址指向一个字节，每次移动的单位也是1字节，可以逐个遍历一个字符串的每一个 char，更可以遍历每个 int （一次性读取 4 个字节） LEGv8 内存指令代码 与 lc2k 指令一样，基于 base + displacement 的寻址方式，base为一个寄存器，displacement 为 ...

std::move() 将参数转换为右值引用，在调用移动构造函数或移动赋值操作符时可以进行资源的转移而非拷贝，从而提高效率 std::swap() 实现 123456template<typename T>void swap(T& a, T& b) { T temp = std::move(a); a = std::move(b); b = std::move(temp);} 功能 可以交换两个动态数组，但是实际上是交换两个数组的指针，操作量非常小，效率非常高 也常常用于所谓需要 “copy” 的地方，特别是需要硬拷贝的类的赋值 一般类的赋值涉及指针的时候，需要额外 new 一个新的指针进行等于，且在判断是否 new 的时候需要判断输入对象和执行对象不相同（相同的话在析构的时候会将当前的数组指针释放且会重复申请同一个数值的多个指针） 使用这个 swap 函数进行 就不需要担心这个问题 STL 依赖的特殊关键字 explicit 阻止编译器隐藏转换数据类型，比如 123explicit FeetInches(int a); ...

问题背景阐述以及分类 在一个有权有向图(weighted directed graph)中，我们想知道从一个节点到其他某一个节点的路径的权和，注意权重可能是负数，我们这里假设图本身没有形成环 那么问题会被分成两类 Single-Source Shortest Paths (SSSP): 单个源出发到达某一节点的最短路径 All-pairs Shortest Paths (ASAP): 任意一对节点之间的最短路径 两则引理 引理1 如果从 sss 到 ttt 的最短路径经过 vvv 节点，那么 sss 到 vvv 和 vvv 到 ttt 均为最短路径 引理2 如果图中没有负权回路，那么从 sss 到 ttt 的最短路径中不会存在回路 递归法解决 SSSP 问题 我们可以得到递归公式: dist(s,t)=min⁡v∈neighbors(s){dist(s,v)+w(v,t)}dist(s, t) = \min_{v \in \text{neighbors}(s)} \{dist(s, v) + w(v, t)\} dist(s,t)=v∈neighbors(s)min​{dist ...

我们为什么需要时钟？ 在一般芯片电路中，光信号的传播速度非常快，可以不计入时间，而电信号如果经过了芯片或者门电路，就会遇到延迟，如果这个延时不能很好的校对清楚，那么就会出现在二者时间差内产生奇怪的输出信号 因此我们在每一个输入到芯片的电路中添加一个时间管理器，即按照一定周期输出方波，芯片内部捕获上升沿，也就是说只有在电路信号在时钟达到上升沿的时候才会将信号传入处理器内部 同时，不同的外设装置例如串口，I2C总线等都有自己的时钟来判断是否要继续发送，这些时钟也需要被统一管理，因此我们需要一个时钟树来管理这些时钟 先进高性能总线 Advanced High-performance Bus AHB 这是 STM32 的内部总线，主要用于连接 CPU 和内部存储器，以及连接外设总线，其时钟线称为 HCLK HCLK 与 cpu、内存、dma 的时间总线直接相连，因此频率相等 在处理器内部会存在一个 SystemTick 计时器用来给程序提供时间基准，一般是 72 MHz 分频器 一般是对频率做除法，比如我们将 HCLK 分频为 1/2，那么我们就可以得到 HCLK/2 的频率 SystemTi ...

如果使用 lc-2k 指令集完成一个乘法操作，要求复杂度是 O(log⁡n)O(\log n)O(logn) 要怎么做？ 问题分析 lc-2k 指令集中涉及计算的部分只有 add 和 nor 两个指令 对于一个十进制的乘法操作，我们一般的做法是 列竖式，即将两个数的每一位相乘，然后将结果相加 但是在二进制中，我们应该想到的是将被乘数（较小的）写成二进制，看每一位是否为1,如果是1,那么即乘数的 cand*2^i ，然后将所有的结果相加 Bit Mask 实现 因为要找到每一位的值是否为 1, 那么我们必然需要一个能计算 每一位逻辑的工具，在 lc-2k 中, 只能用 nor 实现 将一个数字和 0xFFFF 进行 nor 操作，就会得到全 0, 但是如果我们将 0xFFFF 的第 k 位变成 0, 再进行 nor 操作，如果返回为 0, 说明原数字k位为1, 否则为 0 所以我们需要一个常量寄存器存储全1数， 即补码 -1; 我们还需要一个 每次乘 2 的bit mask 寄存器，初始值为 -1 （这里思考的时候不要转到 机器码空间，否则用补码进行计算有点逆天，我们直接用实际效果进行反 ...