从计算机组成原理看 C 语言指针 by 彭于斌（ @archibate ） 往期录播： https://www.bilibili.com/video/BV1fa411r7zp 课程 PPT 和代码： https://github.com/parallel101/course 请问下面这三段代码有什么错误？ • float x = -3.14; • printf(“%f\n”, abs(x)); 如果你没看出来（哪怕是其中一个），那就要好好上小彭老师的课哦！ 字节（ byte ） 和位（ bit ）有什么区别 • 众所周知，计算机是二进制的，存储的实际上是一个个 0 和 1 。 • 每个存储 0 或 1 的空间称为一个位（ bit ），一位可以存储 0 或 1 两个可能的值。 • 现在的计算机都会把 8 个位打包成一个字节（ byte ），也就是说： 1 字节 = 8 位。 • 一字节可以表示 0 到 类型 。 不同位数的计算机，字（ word ）的大小也不一样 • 刚刚说把 2 个字节（ byte ）拼成一个字（ word ），实际上是 16 位计算机的做法。 • 16 位计算机得名就是因为他的字由 16 个位组成，早期的 8086 系列 CPU 就是 16 位 的。 • 在 32 位计算机上会把 4 个字节拼成一个字，字由 32 个位组成。 • 在 64 位计算机上会把 8 个字节拼成一个字，字由

时间复杂度（ 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 秒 用电量：

，内存管理与对象生命周期 ASCII 码 第 1 章 计算机如何表达字符 https://zh.wikipedia.org/wiki/ASCII 计算机如何表达字符 • 众所周知，计算机只能处理二进制 整数，字符要怎么办呢？ • 于是就有了 ASCII 码表，他规定， 每个英文字符（包括大小写字母、 数字、特殊符号）都对应着一个整 数。在计算机里只要存储这个的整 数，就能代表这个字符了。 • 代表空格， 48 代表 ‘ 0’ ， 65 代表 ‘ A’ ， 97 代表 ‘ a’…… • 32~126 这些整数就用于是表示这些 可显示字符 (printable character) 的。 计算机如何表达字符 • 除了可显示字符 (printable character) 外， ASCII 还规定了一 类特殊的控制字符 (control character) ： • 0 表示空字符（‘ Enter 键一样，按 Ctrl+H 的效果和退格键 一样。 • 这是因为 ASCII 表中规定 ^I 就是 ‘ \t’ ， ^J 就是 ‘ \ n’ ， ^H 就是 ‘ \b’ ，所以以前原始的计算机键盘上其 实还没有 Enter 键，大家都是按 Ctrl+J 来换行的… … • 不过，如果直接在控制台输入 ‘ ^’ 和 ‘ C’ 两个字符并 没有 Ctrl+C 的效果哦！因为 ‘ ^C’ 是

小彭老师说“我在拉答辩。”那么同学认为这个答辩指的是答辩（物理），小彭老师在上厕所。 而不会认为小彭老师在制作三体动画。 • 所以这位同学是人类思维，相当于 Python 的精分 API 。而如果另一个同学是硬核的计算 机思维，相当于 C++ 的一视同仁 API ，他会以为小彭老师真的在吃答辩。 • 这是通常来说，不过万一小彭老师真的这么重口味在吃答辩呢？要怎么传达这个信息？ C++ 一视同仁的接口就能处理这种罕见的情况，不过 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 又称集合（数学概念），是专为查找优化的容器，查找元素要用他自带的 ，查找元素要用他自带的 find 函数。 • set a = { 1, 4, 2, 8, 5, 7 }; • a.find(5); • set 之所以能够实现 O(logn) 复杂度高效查找，是因为他内部预先构建好了一棵二叉排序树。 • 如何构建的？请看动画： 1 4 2 8 5 7 待插入的数 set 查找为什么高效 • set 又称集合（数学概念），是专为查找优化的容器，查找元素要用他自带的

• 抽象数据类型 • 时空复杂度 • 复杂度计算 • 基本数据结构复杂度 抽象数据类型 什么是抽象数据类型？ 为什么需要抽象数据类型？ 时空复杂度 • 时间复杂度更被看重 • 时间和空间复杂度不是对立的，可以协同 时间和空间复杂度 复杂度计算 • 大Ｏ标记法（数量级近似） • 用 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 算法总结 • 复杂度分析及算法优化 • 别自己实现，用标准库 • 利用

，不再 等待烧完开水才开始刷牙，而是针对性地为“没烫伤”的那个剧本优化。把刷牙、看比站和烧 开水同时进行，但刷牙、看比站在烧完开水前都处于“虚”的状态，也就是虽然在做但是不写 到日记里（提前执行数学计算，但不实际写回数据到内存）。直到烧完开水确认没有被烫伤 后，才实际把刷牙、看比站的操作写到日记本里（ CPU 确认执行这条分支，才会真正写回 内存，产生副作用）。 洗脸 刷牙 烧开水 吃饭 看比站 10 烫伤了 去医院 10 烫伤了 多次训练 现代 CPU 流水线如何应付跳转指令：分支预测 • 假如有分支 A 和分支 B ，一开始 CPU 不确定会执行哪一条，会两条都预先执行（只计算 出中间结果，先不写回内存），等到了跳转指令（烧开水）处确定了要走分支 A 以后，就 把分支 A 的操作落到实处（写回内存），再把流水线中关于分支 B 的所有指令和数据删了 （浪费了 50% 的算力）。这就是说 和原来一样； • 对于 x >= 0 的情况会变成 sqrt(1 * x) = sqrt(x) 也和原来一样。成功了！ 存在大量分支的情形 • 但是很多时候并不是单独的一个分支。那 么“妙用加减乘”计算量就会很大，而且写起 来也麻烦。 存在大量分支的情形 • 很多同学通常都会用 switch 来处理这种 大量判断的情况。可能你误以为 switch 比一堆 if-else 更高效。但是实际上在编译

s/TBBtutorial.pdf) - [ 并行体系结构与编程 (CMU 15-418)](https://www.bilibili.com/video/av48153629/) - [ 深入理解计算机原理 (CSAPP)](http://csapp.cs.cmu.edu/) - [CMake “ 菜谱” ](https://www.bookstack.cn/read/CMake-Cookbook/README {} 作用域自动释放 手动释放 RAII ：避免犯错误 与 Java ， Python 等垃圾回收语言不同， C++ 的 解构函数是显式的，离开作用域自动销毁，毫不含 糊（有好处也有坏处，对高性能计算而言利大于 弊） 如果没有解构函数，则每个带有返回的分 支都要手动释放所有之前的资源 : RAII ：异常安全（ exception-safe ） C++ 标准保证当异常发生时，会调用已创建对象的解构函数 造函数，那么您必须同时定义或删除拷贝 赋值函数，否则出错。” C++11 ：为什么区分拷贝和移动？ • 有时候，我们需要把一个对象 v2 移动到 v1 上。而不需要涉及实际数据的拷贝。 • 时间复杂度：移动是 O(1) ，拷贝是 O(n) 。 • 我们可以用 std::move 实现移动。 • v2 被移动到 v1 后，原来的 v2 会被清 空，因此仅当 v2 再也用不到时才用移动 。

第 1 章：稀疏网格 稠密网格计算粒子经过的格点数量 改用更小的 char 存储 只用一个 bit 存储，一个 char 可以存储 8 个 bit 用 map 来存储 读取：如果不存在，则读到 0 写入：如果不存在，则创建该表项 用 unordered_map 来存储 map 基于红黑树，会按照键值排序，需要键值具有 operator< 重载，复杂度 O(logn) C++11 新增的 新增的 unordered_map 基于哈希表，不保证顺序但更高效，需要键值能被哈希，复杂度 O(1) 用 unordered_map 按 16x16 分块存储 分块能减少 unordered_map 中存储的表项数量，从而减轻哈 希的压力。但意味着键值在空间上需要具有一定的局域性，否 则 会浪费分块中一 部分空间。 然而我们这里是 要用他记录粒子 经过的点，因此 具有一定空间局 域性，能够被分 ，从而避免负方向上出错。然而这还是避免不了 a < -b 时的出错。 • 正确的写法是： (a % b + b) % b • 如果 b 是常数且为 2 的幂次方，编译器会检测到， 并替换为更高效的位运算，反而减少了计算量。 • 此外如果 b 一定是 2 的幂次方，那么 (unsigned)a % b 也可以（先转换成无符号的取模）。 高效的解决：位运算 & • 如果 b 是 2 的幂次方，即： 2, 4

是一款开源、云原生的时序数据库（ Time Series Database ），专为物联网、工业互联网、金融、 IT 运维监控等场景设计并优化，具有极强的弹性伸缩能力。同时它还带有内建的缓存、流式计算、数据订阅等 系统功能，能大幅减少系统设计的复杂度，降低研发和运营成本，是一个极简的时序数据处理平台。 采用关系型数据库模型  需要建库、建表，  为提升写入和查询效率，要求一个数据采集点一张表  INT, `location` VARCHAR(24)) TDengine - 业务模式 开源版 企业版 云服务版 核心功能开源 • SQL 支持 • 无模式写入 • 缓存 • 流计算 • 数据订阅 • 集群、高可用 高可靠、线性扩展 + 专业技术服务 • 边云数据复制 • 跨云 / 异地数据复制 • 增量备份 • 多级存储 • 工业数据接入 全托管时序数据 管理云服务平台 GCP) CONTENTS 自 我 介 绍 T D e n g i n e t a o s X R u s t 使 用 taosX - 物联网数据接入问题 • 多种不同协议数据对接，开发复杂度高 • 模块之间关联性不高但模块组成复杂，可维护性差 • 大量设备大量数据归集存储，存储压力大 • 数据总线 / 消息队列消息接入，定制化程度要求高 • 数据业务逻辑自定义需求强 • 一定的实时数据分析能力

那如果我确实需要让 set 迭 代器向前移动 3 格怎么办？ • 可以调用三次 ++ 运算，实 现和 + 3 同样的效果。 • vector 迭代器的 + n 复杂度 是 O(1) 。而 set 迭代器模 拟出来的 + n 复杂度为 O(n) 。虽然低效，但至少可 以用了。 std::next 等价于 + • 但是这样手写三个 ++ 太麻烦了 ，而且是就地操作，会改变迭代 器本身。 count(x) != 0 • count 返回的是一个 int 类型，表示 集合中相等元素的个数。 • 等等，不是说 set 具有去重的功能，不会 有重复的元素吗？为什么标准库让 count 计算个数而不是直接返回 bool… 因为他们 考虑到接口的泛用性，毕竟 multiset 就不 去重。对于能去重的 set ， count 只可能 返回 0 或 1 。 • 个数为 0 就说明集合中没有该元素。