基础、排序、查找、树、图 代码框、颜色、图片绘制均由 Latex 完成 可参考点 为什么 为什么讲这个话题？ 为什么要讲数据结构和算法两部分？ 算法相关知识 算法相关知识 • 抽象数据类型 • 时空复杂度 • 复杂度计算 • 基本数据结构复杂度 抽象数据类型 什么是抽象数据类型？ 为什么需要抽象数据类型？ 时空复杂度 • 时间复杂度更被看重 • 时间和空间复杂度不是对立的，可以协同 时间和空间复杂度不是对立的，可以协同 时间和空间复杂度 复杂度计算 • 大Ｏ标记法（数量级近似） • 用 AI 来估计 算步骤、算存储 Rust 基本数据结构复杂度 线性数据结构 非线性数据结构 总体来看，时间复杂度没有超过 O(n) 的！ Rust 实现数据结构 • 栈 • 链表 • Vec Rust 实现数据结 构 栈 借助 Vec 容器 泛型支持 Option ？ 链表 链接可能为空 多种迭代

density ，而是褪色 temperature 改进褪色：不是单纯地乘以 decayRate ，还和周围环境温度求平均值 改进温度：高温气体往上浮（作为外力来看待） 结果：更像火焰了 改进颜色场：让 clr 作为尘埃密度，密度越高越有向下坠落的趋势 问题：上面的尘埃无止境的飘下来 解决：纹理对象指定为 cudaAddressModeBorder 让越界访问自动变 0 即可 结果：小球加回来

map 里面真正 K-V 对的一份深拷贝。你写入的只是这份拷贝 后的 V ，不是 map 中的那个 V 。 map 的遍历：遍历的同时修改怎么办？ k v map 中的 堆空间 执行你这段代码 的栈空间 未初 始化 v2 要写入的数 执行中的代码 for (auto [k, v]: m) { v = v2; } • 我们现在遍历一个 map ，然后把他里面所有的 V 都设为 map 里面真正 K-V 对的一份深拷贝。你写入的只是这份拷贝 后的 V ，不是 map 中的那个 V 。 map 的遍历：遍历的同时修改怎么办？ k v map 中的 堆空间 执行你这段代码 的栈空间 k v v2 要写入的数 执行中的代码 for (auto [k, v]: m) { v = v2; } • 我们现在遍历一个 map ，然后把他里面所有的 V 都设为 v2 ，不是 map 中的那个 V 。 map 的遍历：遍历的同时修改怎么办？ k v map 中的 堆空间 执行你这段代码 的栈空间 k v2 v2 要写入的数 执行中的代码 for (auto [k, v]: m) { v = v2; } 你修改的是栈空间 ( 周树人 ) 管我堆空间 ( 鲁迅 ) 什么事？ • 我们现在遍历一个 map ，然后把他里面所有的 V 都设为 v2 ，要怎么做？

新特性：自定义字面量后缀 • 如果你觉得 using namespace std; 太危险了不想用他。 • 可以只用 using namespace std::literials; • 这个特殊的名字空间里包含了所有的 operator“” 函数。 小彭老师锐评：何谓“键盘压力” • 高情商：键盘压力，指的是程序员敲击键盘时产生的心理压力。 • 低情商：键盘压力，指的是 rust 键盘侠对 cpp 一样，是内存中连续的数组。注 意这里原来 [4, 4+2) 这里的子字符串为 “ lo” ，替换成 “ pful” 。而因为 “ pful” 比 “ lo” 宽了 2 格，所以为了预留出这 2 格额外的空间，就得 把后面的 “ world” 在内存中整体平移了 2 格（和 vector 的 insert 一 样）。这意味着 replace 最坏是 O(n) 复杂度的，然而如果原来的子字 符串和新的子字符串一样长度，例如 string(“world”, 3) 和 s += “wor” 等价。 • 性能如何？ append 的扩容方式和 vector 的 push_back 一样，每次超过 capacity 就预留两倍空间，所以重复调用 append 的复杂度其实是 amortized O(n) 的。 • 函数原型： • string &append(string const &str);

com/video/BV1fa411r7zp 课程 PPT 和代码： https://github.com/parallel101/course 本课涵盖：稀疏矩阵、 unordered_map 、空间稀 疏网格、位运算、浮点的二进制格式、内存带宽优 化 面向人群：图形学、 CFD 仿真、深度学习编程人 员 第 0 章：稀疏矩阵 稠密数组存储矩阵 用 foreach 包装一下枚举的过程 改用 16x16 分块存储 分块能减少 unordered_map 中存储的表项数量，从而减轻哈 希的压力。但意味着键值在空间上需要具有一定的局域性，否 则 会浪费分块中一 部分空间。 然而我们这里是 要用他记录粒子 经过的点，因此 具有一定空间局 域性，能够被分 块优化。 实际上空间局域 性正是稀疏网格 能够实现的一大 前提，稍后详细 讨论。 在 16x16 分块的基础上，只用一个 bit 存储 浪费内存。 这些被写入的部分被称为激活元素 (active element) ，反之则是未激活 (inactive) 。 这就是稀疏的好处，按需分配，自动扩容。 分块则是利用了我们存储的数据常常有着空间局域性的特点，减轻哈希表的压 力，同时在每个块内部也可以快乐地 SIMD 矢量化， CPU 自动预取之类的。 第 2 章：位运算 稀疏的好处：坐标可以是负数 这样即使坐标为负数，或者可以是任意大的坐标，都不会产生越界错误。

如果你没看出来（哪怕是其中一个），那就要好好上小彭老师的课哦！ 字节（ byte ） 和位（ bit ）有什么区别 • 众所周知，计算机是二进制的，存储的实际上是一个个 0 和 1 。 • 每个存储 0 或 1 的空间称为一个位（ bit ），一位可以存储 0 或 1 两个可能的值。 • 现在的计算机都会把 8 个位打包成一个字节（ byte ），也就是说： 1 字节 = 8 位。 • 一字节可以表示 0 到 11111111 + 00000010 = 100000001 • 正好和普通的二进制加法一样，只需要丢弃最前面的那一位进位就可以了。 • 这样就重用了现有的无符号加法器，从而节省了宝贵的电路板空间。 • 补码和反码一样，让有符号整数可以表示 -128 到 127 。 • 其中负数的范围反而比正数大是因为要回避 -0 。 字节的单位： KB ， MB ， GB ， TB • 计算机中规定“一千”是 是用不到。 知识拓展 • 虽然 64 位计算机的寄存器能处理 64 位的整数，实际上的内存地址并没有 64 位。 • 实际上地址的高 16 位始终和第 48 位一致（符号扩展），也就是虚拟地址空间只有 48 位。 • 而经过 MMU 映射后实际给内存的地址只有 39 位，因此如今的 x64 架构实际上只能访 问 512GB 内存，如果插了超过这个大小的内存条他也不会认出来。 • 此外，

4 个字节时，实际会导致 0x0040~0x0080 的 64 字节数据整个被读取到缓存中。 • 这就是为什么我们喜欢把数据结构的起始地址和大小对齐到 64 字节，为的是不要浪费缓存行的存储空间。 缓存的工作机制：写 • 缓存中存储的数据结构： • struct CacheEntry { • bool valid, dirty; • uint64_t address; 量无关，和访问的每个字节所在的缓存行 数量有关。 • 可见，能否很好的利用缓存，和程序访问 内存的空间局域性有关。 缓存行决定数据的粒度（续） • 所以我们设计数据结构时，应该把数据存 储的尽可能紧凑，不要松散排列。最好每 个缓存行里要么有数据，要么没数据，避 免读取缓存行时浪费一部分空间没用。 重新认识结构体 重新认识 AOS * * CPU 检测到，从而启动缓存行预取，避免了 等待数据抵达前空转浪费时间。 页对齐的重要性 • 为什么要 4KB ？原来现在操作系统管理内存是用分页 （ page ），程序的内存是一页一页贴在地址空间中的， 有些地方可能不可访问，或者还没有分配，则把这个页设 为不可用状态，访问他就会出错，进入内核模式。 • 因此硬件出于安全，预取不能跨越页边界，否则可能会触 发不必要的 page fault

少的字段就不用大字段。比如，主键，强烈建议用 int 整型 . 不用 bigint ，为什么 ? 省空间啊。空间是什么 ? 空间就是效率！按 4 个字节和按 32 个字节定位一条记 录，谁快谁慢太明显了。涉及几个表做 join 时， 效果 就更明显了。更小的字段类型占用的内存就更少，占用 的磁盘空间和磁盘 I/O 也会更少，而且还会占用更少的 带宽。因此 . 在日常选择字段时必须要遵守这一规则。

*pret 访问其 返回值了。但是不行，因为 GPU 访问不 了 CPU 的内存地址，同理， CPU 也访 问不了 GPU 的内存地址。一访问 CPU 就奔溃了。 跨 GPU/CPU 地址空间拷贝数据 • 因此可以用 cudaMemcpy ，他能够在 GPU 和 CPU 内存之间拷贝数据。 • 这里我们希望把 GPU 上的内存数据拷贝到 CPU 内存上，也就是从设备内存 (device) std::allocator 接口 • vector 会调用 std::allocator 的 allocate/deallocate 成员 函数，他又会去调用标准库的 malloc/free 分配和释放内存空间 （即他分配是的 CPU 内存）。 • 我们可以自己定义一个和 std::allocator 一样具有 allocate/deallocate 成员函数的类，这样就可以“骗过” vector 刚刚的线程升级为板块，刚刚的 for 升级为线程，然后把 刚刚 local_sum 这个线程局部数组升级为板块局部数组。 那么如何才能实现板块局部数组呢？ • 同一个板块中的每个线程，都共享着一块存储空间，他就 是共享内存。在 CUDA 的语法中，共享内存可以通过定 义一个修饰了 __shared__ 的变量来创建。因此我们可以 把刚刚的 local_sum 声明为 __shared__ 就可以让他从

执行调度的最小单位。也就是说，进程本身并不能获取 CPU 时间，只有它的线程才可以。 • 从属关系：进程 > 线程。一个进程可以拥有多个线程。 • 每个线程共享同样的内存空间，开销比较小。 • 每个进程拥有独立的内存空间，因此开销更大。 • 对于高性能并行计算，更好的是多线程。 为什么需要多线程：无阻塞多任务 • 我们的程序常常需要同时处理多个任务。 • 例如：后台在执行一个很耗时的任务，比