Yuchen You

时间的测量 1234567891011#include <chrono>int main(){ Timer t; t.start(); t.stop(); cout << t.seconds() << endl; t.reset(); t.start(); t.stop();} 但是多次查看系统时间会导致程序明显变慢 常用的工具 profiling tools perf 指令会显示某些节点花费的时间、cpu占用等性能 或者在linux 下，可以考虑使用 time prog 指令，该指令会在命令行输出一行 后面的prog 内容加上 各个部分占用的时间以及cpu占用量 11.60s user 0.03s system 95% cpu 1.711 total user: 程序占用时间 system: 系统执行该程序使用的额外时间 elapsed: 从开始打表到结束打表所经过的时间差，会包含期间其他进程占用的时间 cpu: 程序的 cpu 占用量，计算公式 user+system/elapseduser + system / elaps ...

在分治算法中，我们已经知道要将一个问题分裂成不同的子问题来解决，但是，如果有些时候子问题之间存在覆盖问题，那么再利用 分治算法得到的时间复杂度就会非常大，所以，我们往往使用制表法来解决这个问题，中文名“动态规划”。 动态规划的解 （ OP, optimal）往往有很多个, 但是我们会用 value 进行标注这个 解，即我们可以通过比较 value 来找到最优解 (OTV, optimal value)。 从斐波那契讲起 如果我们要求解斐波那契数列中第 n 个数，那么我们可以用递归 (Top-Down) 的方法： 123456def fib(n): if n == 0: return 0 if n == 1: return 1 return fib(n-1) + fib(n-2) 但是这个方法的时间复杂度是 O(2n)O(2^n)O(2n)，时间表达式 T(n)=T(n−1)+T(n−2)+O(1)T(n) = T(n-1) + T(n -2)+ O(1)T(n)=T(n−1)+T(n−2)+O(1) 因为我们会重复计算很多次 fib(n- ...

分治思想 将一个输入变成多个 sub-inputs 将一个 subinput 通过递归找到子解决方法 结合 (combine, or conquer) 子解决方法得到最终解决方法 归并排序 将一个线性数组分割成两个等长的数组，长度 n/2 对左右子数组分别执行归并排序（递归）复杂度 将左右数组进行合并， 复杂度 O(n)O(n)O(n) 递归部分复杂度分析 首先我们明确这是一个类似二叉树的结构，所以，从层数上来讲，一共有 log⁡2n\log_2 nlog2​n 层，每一层的复杂度是 O(n)O(n)O(n) (每一层都有合并)，所以递归部分的复杂度是 O(nlog⁡n)O(n \log n)O(nlogn) 注意区分一般的二叉遍历 比如对分查找，我们想找到有序数组中最靠近 k 的位置，那么用对分查找，相比归并排序少了一个合并 (O(n)) 的步骤，时间复杂度是 O(log⁡n)O(\log n)O(logn) 又或者是将一个数不断的用 ⌊x/2⌋\lfloor x/2\rfloor⌊x/2⌋ 和 x−⌊x/2⌋x - \lfloor x / 2\rfloorx−⌊x/2⌋ 来 ...

位操作 Bit Manipulation 如果我们要将一个十六进制数 0x2020 取出从低到高第二位的值，我们最直接的方法就是使用 mask, 即 12a = 0x2020;a = a & 0x00F0; 如果要将这几位输出，我们就要 a = a >> 4; 就可以将数据向右 bit shift 4 位，然后我们就可以得到 0x0002 的值 为什么不能用 (a << 8) >> 12? 对于向右位移，我们可能会将超过长度的内容赋值 0, 但是向左位移则不是这样，向左的位移会被认为是 直接扩大数字 如果是 int 数据类型向左位移 100 位，这个等价于 << 100 % 32 因为 int 长 4 字节 32 位，编译器会将这一步截断到 4 位从而不为 0 编译器对于补码的理解 如果输入的数字是一个负数，对其进行 >> 操作得到的结果会和正数情况下不同，编译器会按照补码与否来进行操作，如果是 负数，就会填充 F; 如果是 正数，就会填充 0，因此如果要用循环来进行位提取，负数的终点是 0xFF⋯0\text{x}F ...

在使用抽象数据类型的时候，我们往往会需要考虑数据结构的存取api的使用逻辑，这我就需要考虑栈和队列了 数据的存储有两种形式: 连续的 array 型存储 和 离散的 linked list 型存储，我们接下来也会对比二者的效果 栈 Stack 栈的存储顺序是 LIFO, 即 last in - first out 需要两个指针: 指向栈底的 base_ptr 与 指向栈顶的 top_ptr , 其中 top_ptr 指向的是栈顶的下一个位置(悬空) Method Implementation Array Complexity List Complexity push 1. 可能需要申请二倍空间 2. 或者单纯将数据复制到 top 指针并且向后移动一位 top O(n)O(1) O(1)O(1) pop 向前移动 top 指针 O(1) O(1) top 返回 top 前一个指针并且去引用 O(1) O(1) size 用 top 地址减去 base 地址 O(1) O(1) empty 返回 base_ptr == top_ptr O(1) O(1) ...

ISA 可以看作是连接汇编层代码和硬件的操控指令集合, 例如 汇编会有 ADD r1, r2, r3 的指令，我们利用 ISA 就会将指令转换为 r2 + r3 -> r1 常见分类 Classification x86 架构 由 intel 公司开发，为 32 位处理器，一般在上世纪末的电脑中比较常见 由于 232≈22×230=4×10003=4GB2^{32}\approx 2^2 \times 2^{30} = 4\times 1000^3 = 4GB232≈22×230=4×10003=4GB 即地址循迹的范围小于等于 4GB, 也就是内存大小不超过 4G amd64 架构 由 amd 公司在上世纪发明，一般为 64 位处理器，后面 intel 公司也制造这个架构 现在被大量的 pc 使用 ARM 板 Advanced RISC Machine 设计公司是 arm, 非常适用于移动通信领域, 具有 低成本、高性能、低耗电的特性 现在用于大量的手机等可移动设备使用 近年来的 mac silicone 用 arm 架构 RISC-V 锐克五代 开源 学术界青睐，因为没有昂 ...

对于计算机而言，我们常常会讨论到“磁盘”的概念，磁盘就是存储数据信息的重要电子元件，那么，这里就让我们从头开始，看看怎么存储 1 位的数据，再到怎么存储 1 字节的数据，以后再以此类推，我们就可以做出更大的“寄存器”了 1 位寄存器 首先，我们要明确这个寄存器的必备功能: 写入以及输出 写入应该需要有一个信号，不能随便来一个数据就能写入; 输出也要有一个信号，需要的时候输出 输入实现 首先，在输入的时候如果写入信号为 假，那么我们就要保持输出上一帧的数据 那么我们就要想到使用一个常见的基本电路元件 —— 延迟线，即能将输入的信号晚一帧输出 如果将一个延迟线首尾相连并在这个回路中接入一个输入信号(不考虑不输出时候的短路可能性)，那么这个回路就会实现锁存. 但是这时候我们就会面临一个数据选择的问题: 锁存还是更新？那么我们就用一个数据选择器进行分流，通过 写入 信号对选择器控制 这样我们就实现了1位信号的存储 输出实现 这个很简单，我们使用二进制开关就能明确数据输出与否 8 位寄存器 很简单，我们将8个1位寄存器并联就得到了8位寄存器 计数器 我们需要一个优秀的电子元件来记录我们做了一项 ...

继电器 relay 输入小电流，输出大电流，起到中继的作用 为什么bug和虫子是一个意思？ 在早期ibm制造的继电器计算机中，经常会在故障的继电器中找到死掉的虫子，于是我们称计算机的问题为 bug 真空管 热电子发射是真空条件下加热金属的时候电子从材料表面逸出的现象 每一秒可以开闭数千次 与非门 符号 NAND 这是一切逻辑门的基础，我们首先要用原理图来认识它 从这里我们可以看出与非门最简单的形式就是采用两个开关进行控制，但是电路里面要实现自动化，我们就不能用销号人力的开关了，不如使用三极管，通过给基极传输高低电平实现通断来完成开关的功能 TTL 与 CMOS 控制 以下两个电路我们分别使用 TTL 和 CMOS 电路来实现功能 非门 通过将与非门两个输入端接入输入信号就是非逻辑了 与门 将与非门和非门串联 或非门 通过 德摩根定律，利用 A‾+B‾=A⋅B‾\overline{A}+ \overline{B} = \overline{A \cdot B}A+B=A⋅B 我们可以用两个输入分别取非逻辑实现或非门 或门 通过串联或非门和非门实现 恒高电平 ON 将非和原逻辑接入或 ...

全加器 考虑进位的加法称为全加，能够完成全加运算的电路称为全加器，一个基本全加器能够完成两个一位二进制数的全加运算，因此它具有三个输入端和两个输出端，其中 Xi,YiX_i, Y_iXi​,Yi​ 为加数，Ci−1C_{i - 1}Ci−1​ 相邻低位进来的进位数， SiS_iSi​ 为输出和，CiC_iCi​ 为向高位邻位进位数 和位 我们称 s 是和位输出，计算方法是对于 x_i, y_i c_i-1 的异或结果 s=x⊕y⊕cs = x\oplus y\oplus c s=x⊕y⊕c 那么在实际电路中我们只有二元输入的异或门，那么我们就可以用两个异或门进行组合完成 12xor g1(a,x,y);xor g2(s,a,c); 进位位 在三个变量中有两个变量是1的时候发生进位 c=(x⋅y)+(x⋅c)+(y⋅c)c = (x\cdot y) + (x\cdot c) + (y\cdot c) c=(x⋅y)+(x⋅c)+(y⋅c) 考虑到我们需要使用尽量少的逻辑门，那么我们需要对这个逻辑表达式进行化简 c=x⋅y+x⋅c+y⋅c=x⋅y+c⋅(x+y)c = x\cdot y + ...