Yuchen You

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 ...

如果使用 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 （这里思考的时候不要转到 机器码空间，否则用补码进行计算有点逆天，我们直接用实际效果进行反 ...

位数扩展 有符号数的符号位(most significant number)为 1 时，扩展时高位补 1 有符号数的符号位(most significant number) 为 0 时，扩展时高位补 0 无符号数的扩展时高位补 0 寄存器知道存储数值是有符号还是无符号的吗 答案是不知道，寄存器只会存储数值，不会存储数值的符号，符号是由汇编码的不同操作指令来决定的，比如 LDURSW 就是有符号数，LDUR 就是无符号数 例子 比如将一般的 int 进行 bit shift, 那么 1 >> 2 = 0, 而 -1 >> 2 = -1 数字存储顺序 Endian 这个词出自Jonathan Swift书写的《格列佛游记》。这本书根据将鸡蛋敲开的方法不同将所有的人分为两类，从圆头开始将鸡蛋敲开的人被归为Big Endian，从尖头开始将鸡蛋敲开的人被归为Littile Endian（这句话最为形象）。小人国的内战就源于吃鸡蛋时是究竟从大头（Big-Endian）敲开还是从小头（Little-Endian）敲开 注：存储顺序是内存的，寄存器没有这个说法！ 一般来 ...

硬件结构 32 位 处理器: 指令长度是 32 位 , 寄存器大小是 32 位 32 位处理器的关键特征是其寄存器、数据总线和地址总线的宽度为 32 位。这意味着它可以处理 32 位的整数，并且通常可以寻址的最大内存空间为 4 GB。 在 32 位处理器中，寄存器和数据路径通常也是 32 位的，所以处理器可以在一次操作中处理 32 位的数据 其指令长度也是 32 位（这里的32 没有特指王楚钦） 8 个寄存器，其中 reg 0 一般只会被赋值 0 内存寻址范围 4GB 即 65536 words 指令形式 寄存器型指令结构 31 - 25 24 - 22 21 - 19 18 - 16 15 - 3 2 - 0 unused opcode regA regB unused destR 立即数型指令结构 31 - 25 24 - 22 21 - 19 18 - 16 15 - 0 unused opcode regA regB offset J 类型指令 (jalr) 31 - 25 24 - 22 21 - 19 18 - 16 ...

相比于前一节课讲的 lc2k isa, arm 架构的效果会好很多 ISA 的分类 RISC 架构，Reduced Instruction Set Computing 指令数量更少，编码的指令长度是一致的，硬件设备相对更加简单，程序更大，手写会更加困难，但是当前非常常用 应用: lc2k, risc-v, arm (包括其子集 LEG) CISC 架构，Complex Instruction Set Computing 用更多、更复杂的指令集，编码的指令的长度是不一定的，所以硬件更复杂，程序的长度更短，手写更方便，现在比较少用了 应用: x86 指令及其分类 算术指令 Arithmetic 格式：3 operand fields, 一般会将 destination 寄存器放在第一位 ADD X1, X2, X3: 将 X2 + X3 的结果转存到 X1 寄存器中 这个和 lc2k 是反的 只能操作于 ARM 指令集存储形式 | opcode | Rm | shamt | Rn | Rd | 存储了一个指令集 其中 Rm 表示第二个 register operand, Rn 表 ...

尾递归 Tail Recursion 我们称递归调用在函数最后一步的递归方式为 尾递归 例如我们在计算阶乘的时候，如果我们这样写： 1234def factorial(n, acc=1): if n == 0: return acc return factorial(n-1, acc*n) 那么调用自身的步骤在最后，就是尾递归，这种递归形式由于和 正向递推没有很大的区别，有一些编译器会将其变成 iteration 的形式进行执行，从而避免 stack-overflow 的问题，其占用的时间和空间都会比一般的递归小很多 递归与压栈操作 在函数被调用的时候，我们称一个本地变量存储在名为 program stack 的栈结构中 在调用函数之后，其arguments 会被 push onto program stack 在函数执行完之后，arguments 就会被 pop 出栈 在函数中执行 return, 返回值会被push 到 prog stack 中 如果 return 的值被收到，那么返回值会被 pop 走，且本地变量会被重新存储 函数栈可以被嵌套 (nes ...

时间的测量 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⌋ 来 ...