defl; • } • } • 封装成函数方便使用： • auto val = map_get(m, “key”, “default”); • ss map 常用函数不同情况下的行为分析 类型 C++ 代码 key 已存在 key 不存在 读取 val = m.at(key) 读取这个值 抛出 out_of_range 异常 val = m[key] 读取这个值 创建并零初始化（默认构造函数） erase(key) 删除这个值 默默放弃 小彭老师四定律： 读取，要用 at 。 写入，要用 [] 。 判断存在，用 count 。 删除，用 erase 。 这四个已经够用了。 map 常用函数不同情况下的行为分析 类型 C++ 代码 key 已存在 key 不存在 读取 val = m.at(key) 读取这个值 抛出 out_of_range 异常 val = m[key] 读取这个值 创建并零初始化（默认构造函数） 1 次比较运算就能找到（例如查找 1 ）。 • 最坏需要 n 次比较运算才能找到或者发现找不到（例如查找 7 ，或者找一个不存在的 数）。 • 所以我们说 vector 查找指定元素的最坏复杂度为 O(n) 。 1 4 2 8 5 7 要找的数 内存 5 ==? 地址 a a+1 a+2 a+3 a+4 a+5 set 查找为什么高效 • set 又称集合（数学概念），是专为查找优化的容器，查找元素要用他自带的

e 等于 equal ne 不等于 not equal http://unixwiz.net/techtips/x86-jumps.html 手动进行无分支优化的方法 无分支优化：从汇编角度分析 • 发生了什么？让我们把源码和汇编逐个对应。 • x 是第一个参数（通过 edi 传入，被存入 rbp 指向的堆 栈） • 比较 x 和 0 的大小（ cmp 命令把刚存入堆栈的 x 和 0 3 字节 填充零） • 返回类型 int 占据 4 字节（ eax 寄存器就是 4 字节的） • 返回值都放 eax 寄存器（刚刚算得的就在 eax ，直接返 回） 无分支优化：从语法角度分析 • 刚刚其实是利用了 C 语言把 bool 类型的 true 当做 1 ， false 当做 0 的特性。 • (int)true == 1 (int)false == 0 • 例如： • ifelse 的。 “ 摆大烂”的效果和 ifelse 几乎一样，也就是说根本没用，三目运算符还是生成了 低效的跳转指令，自己不上进，还指望编译器来救你？你还不如坐等天上掉馅饼。 从汇编角度分析（ -O0 ） 从汇编角度分析（ -O3 ） 因为 clamp 用了两次分支， if-else-if-else ，刚才 -O0 时是需要连续两次条件跳转指令的。 但是在 -O3 的淫威下，编译器把其中一个条件跳转自动优化掉了（

• 抽象数据类型 • 时空复杂度 • 复杂度计算 • 基本数据结构复杂度 抽象数据类型 什么是抽象数据类型？ 为什么需要抽象数据类型？ 时空复杂度 • 时间复杂度更被看重 • 时间和空间复杂度不是对立的，可以协同 时间和空间复杂度 复杂度计算 • 大Ｏ标记法（数量级近似） • 用 AI 来估计 算步骤、算存储 Rust 基本数据结构复杂度 线性数据结构 非线性数据结构 非线性数据结构 总体来看，时间复杂度没有超过 O(n) 的！ Rust 实现数据结构 • 栈 • 链表 • Vec Rust 实现数据结 构 栈 借助 Vec 容器 泛型支持 Option ？ 链表 链接可能为空 多种迭代 Vec 借助链表 随机插入 插入新的 Vec Rust 实现算法 • 蒂姆排序 • 字典树 • 图 Rust 实现算 法 蒂姆排序 什么是蒂姆排序？ 联想：图数据结构的的点、边、面似乎满足欧拉公式 : V – E + F = 2 、则时间复杂度为： O(V+E) = O(2E – F + 2) • V = 14; E = 18; F = 5 + 1; • V+E = 32 • 2E – F + 2 = 32 总结及学习资源 • 算法总结 • 学习资源 总结及学习资源 Rust 算法总结 • 复杂度分析及算法优化 • 别自己实现，用标准库 • 利用 Rust

• OOXML - Excel 解析库 • xlsx2csv - Excel 转 CSV 工具 • Unqlite - 单文件非关系型数据库 • Wisecondor - 生物信息 CNV 分析 • mdsn - A Multi-address DSN(Data Source Name) parser. TDengine 应用开发组 • Python/Rust/Go 连接器 • 数据可视化 Series Database ），专为物联网、工业互联网、金融、 IT 运维监控等场景设计并优化，具有极强的弹性伸缩能力。同时它还带有内建的缓存、流式计算、数据订阅等 系统功能，能大幅减少系统设计的复杂度，降低研发和运营成本，是一个极简的时序数据处理平台。 采用关系型数据库模型  需要建库、建表，  为提升写入和查询效率，要求一个数据采集点一张表  为实现多表聚合，引入超级表概念 u s t 使 用 taosX - 物联网数据接入问题 • 多种不同协议数据对接，开发复杂度高 • 模块之间关联性不高但模块组成复杂，可维护性差 • 大量设备大量数据归集存储，存储压力大 • 数据总线 / 消息队列消息接入，定制化程度要求高 • 数据业务逻辑自定义需求强 • 一定的实时数据分析能力 taosX - 功能路线图 集群运维 数据接入 流式处理 流式处理 数据分享

这样，在 cudaDeviceSynchronize() 以后 ，应该可以获取数据了吧？ • 结果令人失望，尽管给 kernel 传了指向 ret 的指针，但 ret 的值并没有被改写成 功。 分析返回的错误代码 • CUDA 的函数，如 cudaDeviceSynchronize() 。 • 他们出错时，并不会直接终止程序，也不会抛出 C++ 的异常，而是返回一个错误代码，告诉你出的具体什么 使用板块局部数组（共享内存）来加速数组求和 这就是胡渊鸣所说的 BLS （ block-local storage ） 进一步，当数组非常大，缩减后的数组可以继续递归地用 GPU 求和 • 这是第六课说过的方法。递归地缩并，时间复杂度是 O(logn) 。 • 同样是缩并到一定小的程度开始就切断 (cutoff) ，开始用 CPU 串行求和。 https://developer.download.nvidia.cn/asse 没有冲突，并行访问↓ 出现冲突，串行访问↓ 回到矩阵转置的案例：如何解决区块冲突？ • 而刚刚那个矩阵转置的例子，这里的 blockSize 是 32 。可以看到第一个对 tmp 的访问是没冲突的。 • 而分析一下第二个对 tmp 的访问： threadIdx=(0,0) 的线程 0 会访问 tmp[0] 位于 bank 0 ； threadIdx=(0,1) 的线程 1 会访问 tmp[32] 也位于

章：并行循环 时间复杂度（ time-efficiency ）与工作量复杂度（ work-efficiency ） • 在“小学二年级”算法课里，我们学过复杂度的概念，意思是算法执行所花费的时间取决于数据量 的大小 n ，比如 O(n²) 表示花费时间和数据量的平方成正比。 • 对于并行算法，复杂度的评估则要分为两种： • 时间复杂度：程序所用的总时间（重点） • 工作复杂度：程序所用的计算量（次要） 这两个指标都是越低越好。时间复杂度决定了快慢，工作复杂度决定了耗电量。 • 通常来说，工作复杂度 = 时间复杂度 * 核心数量 • 1 个核心工作一小时， 4 个核心工作一小时。时间复杂度一样，而后者工作复杂度更高。 • 1 个核心工作一小时， 4 个核心工作 1/4 小时。工作复杂度一样，而后者时间复杂度更低。 • 并行的主要目的是降低时间复杂度，工作复杂度通常是不变的。甚至有牺牲工作复杂度换取时间 复杂度的情形。 复杂度的情形。 • 并行算法的复杂度取决于数据量 n ，还取决于线程数量 c ，比如 O(n/c) 。不过要注意如果线程 数量超过了 CPU 核心数量，通常就无法再加速了，这就是为什么要买更多核的电脑。 • 也有一种说法，认为要用 c 趋向于无穷时的时间复杂度来衡量，比如 O(n/c) 应该变成 O(1) 。 映射（ map ） 1 个线程，独自处理 8 个元素的映射，花了 8 秒 用电量：

我们知道 push_back 可以往尾部插入数据，那么如何往头 部插入数据呢？用 insert 函数，他的第一个参数是要插入 的位置（用迭代器表示），第二个参数则是要插入的值。 • 注意这个函数的复杂度是 O(n) ， n 是从插入位置 pos 到 数组末尾 end 的距离。没错，他会插入位置后方的元素整 体向后移动一格，是比较低效的，因此为了高效，我们尽量 只往尾部插入元素。如果需要高效的头部插入，可以考虑用 重复多少次 , 插入的值 ); • 你可能会担心，小彭老师刚刚不是说在头部 insert 是 O(n) 复杂度嘛？那如果再重复 n 次岂不是 O(n²) 复杂度了？不 会哦， insert 的这个重载会一次性批量让 pos 之后的元素 移动 n 格，不存在反复移动 1 格的情况，最坏复杂度仍然 是 O(n) 。如果你自己写个 for 循环反复调 insert 那的确 是会 O(n²) 了，这就是为什么 新增的功能，例如这里 这个列表的类型是 std::initializer_list 。 • a.insert( 插入位置 , { 插入值 1, 插入值 2, ...}); • 这个的最坏复杂度同样是 O(n) 的，并且因为其内部 预先知道了要插入列表的长度，会一次性完成扩容， 比重复调用 push_back 重复扩容要高效很多。 • iterator insert(const_iterator

则是从尾部开始查找，返回最后一次出现的地方 。 • 例如 “ helloworld”.rfind(‘l’) 会返回 8 ，因为 rfind 是优先 从尾部开始查找的。 • rfind 和 find 的最坏复杂度都为 O(n) ，最好复杂度都为 O(1) 。 find_first_of 寻找集合内任意字符 • size_t find_first_of(string const &s, size_t pos = 0) insert 一 样）。这意味着 replace 最坏是 O(n) 复杂度的，然而如果原来的子字 符串和新的子字符串一样长度，例如 “ helloworld”.replace(4, 2, “pf”) 会 得到 “ helpfworld” 则后面的 “ world” 不需要被平移，是最好的 O(1) 复 杂度……好吧，其实是 O(len) 复杂度， len 就是这里子字符串的长度 2 。 • 此外，要注意 s += “wor” 等价。 • 性能如何？ append 的扩容方式和 vector 的 push_back 一样，每次超过 capacity 就预留两倍空间，所以重复调用 append 的复杂度其实是 amortized O(n) 的。 • 函数原型： • string &append(string const &str); // str 是 C++

造函数，那么您必须同时定义或删除拷贝 赋值函数，否则出错。” C++11 ：为什么区分拷贝和移动？ • 有时候，我们需要把一个对象 v2 移动到 v1 上。而不需要涉及实际数据的拷贝。 • 时间复杂度：移动是 O(1) ，拷贝是 O(n) 。 • 我们可以用 std::move 实现移动。 • v2 被移动到 v1 后，原来的 v2 会被清 空，因此仅当 v2 再也用不到时才用移动 。 移动构造函数：缺省实现 • 同样，如果对降低时间复杂度不感兴趣： • 移动构造≈拷贝构造 + 他解构 + 他默认构造 • 移动赋值≈拷贝赋值 + 他解构 + 他默认构造 • 只要不定义移动构造和移动赋值，编译器会自 动这样做。虽然低效，但至少可以保证不出错 。 • 若自定义了移动构造，对提高性能不感兴趣： • 移动赋值≈解构 + 移动构造 注： 降低时间复杂度： O(n) >>> O(1) 提高性能：

写入：如果不存在，则创建该表项 用 unordered_map 来存储 map 基于红黑树，会按照键值排序，需要键值具有 operator< 重载，复杂度 O(logn) C++11 新增的 unordered_map 基于哈希表，不保证顺序但更高效，需要键值能被哈希，复杂度 O(1) 用 unordered_map 按 16x16 分块存储 分块能减少 unordered_map 中存储的表项数量，从而减轻哈