从稀疏数据结构到量化数据类型 by 彭于斌（ @archibate ） 往期录播： https://www.bilibili.com/video/BV1fa411r7zp 课程 PPT 和代码： https://github.com/parallel101/course 本课涵盖：稀疏矩阵、 unordered_map 、空间稀 疏网格、位运算、浮点的二进制格式、内存带宽优 化 面向人群：图形学、 >> 3 。 >> 2 = 位运算 >> 对负数的处理 signed 类型的 >> n 会把最高位复制 n 次。 因为补码的特性，这导致负数 >> 的结果仍是负 数。 这样就实现了和 Python 一样的始终向下取整除 法。 >> 2 = unsigned 类型的位运算 >> 不一样 而 unsigned 类型的 >> n 会不会复制最高位， 只是单纯的位移，这会导致负数的符号位单独被位 只是单纯的位移，这会导致负数的符号位单独被位 移，补码失效，造成结果不对。 unsigned 类型的 >> 会生成 shr 指令， signed 类型的 >> 会生成 sar 指令。 我们需要负方向无限延伸的稀疏数据结果，那就只 要 signed 那个就行。 >> 2 = 没有重合时可以用高效的加法：位运算 | • 如果可以保证 a 和 b 满足 a & b = 0 ， 如： • 1011000 和 0000110

表结构设计原则 表结构设计原则 选择字段的一般原则是保小不保大，能用占用字节 少的字段就不用大字段。比如，主键，强烈建议用 int 整型 . 不用 bigint ，为什么 ? 省空间啊。空间是什么 ? 空间就是效率！按 4 个字节和按 32 个字节定位一条记 录，谁快谁慢太明显了。涉及几个表做 join 时， 效果 就更明显了。更小的字段类型占用的内存就更少，占用 的磁盘空间和磁盘 I/O 也会更少，而且还会占用更少的 带宽。因此 . 在日常选择字段时必须要遵守这一规则。 应用优化 应用优化 索引建立原则（一） 索引建立原则（一）  一般针对数据分散的关键字进行建立索引，比如 一般针对数据分散的关键字进行建立索引，比如 像性别、状态值等等建立索引没有意义 像性别、状态值等等建立索引没有意义  字段唯一，最少，不可为 字段唯一，最少，不可为 null null  等 类型的字段建立索引 类型的字段建立索引  需要的时候建立联合索引，但是要注意查询 需要的时候建立联合索引，但是要注意查询 SQL SQL 语句的编写 语句的编写  谨慎建立 谨慎建立 unique unique 类型的索引（唯一索引） 类型的索引（唯一索引）  大文本字段不建立为索引，如果要对大文本字段进行检索， 大文本字段不建立为索引，如果要对大文本字段进行检索，

CMAKE_BUILD_TYPE 和 CMAKE_INSTALL_PREFIX ） -G 选项：指定要用的生成器 • 众所周知， CMake 是一个跨平台的构建系统，可以从 CMakeLists.txt 生成不同类型的构建系 统（比如 Linux 的 make ， Windows 的 MSBuild ），从而让构建规则可以只写一份，跨平 台使用。 • 过去的软件（例如 TBB ）要跨平台，只好 Makefile 放到和源码同一个目录里，我个人的建议是把源码放到 src 目录下 。 第 2 章：项目配置变量 CMAKE_BUILD_TYPE 构建的类型，调试模式还是发布模式 • CMAKE_BUILD_TYPE 是 CMake 中一个特殊的变量，用于控制构建类型，他的值可以 是： • Debug 调试模式，完全不优化，生成调试信息，方便调试程序 • Release 发布模式，优化程度最高，性能最佳，但是编译比 ：根项目源码路径（存放 main.cpp 的地方） • CMAKE_BINARY_DIR ：根项目输出路径（存放 main.exe 的地方） • PROJECT_IS_TOP_LEVEL ： BOOL 类型，表示当前项目是否是（最顶层的）根项目 • PROJECT_NAME ：当前项目名 • CMAKE_PROJECT_NAME ：根项目的项目名 • 详见： https://cmake.org/

• 11111100 表示 252 11111101 表示 253 11111110 表示 254 11111111 表示 255 • 字节实际上就是 C 语言中的 unsigned char 类型。 表示更大范围的整数：字（ word ） • 但是单单一个字节表示的范围还是太有限了，只能表示 0 到 255 的值。 • 如何扩大表示范围？简单，用两个字节合在一起即可，例如： • 00000000-00000000 11111111-11111110 表示 65534 11111111-11111111 表示 65535 • 这就是两个字节合成了一个字（ word ），实际上就是 C 语言里的 unsigned short 类型 。 不同位数的计算机，字（ word ）的大小也不一样 • 刚刚说把 2 个字节（ byte ）拼成一个字（ word ），实际上是 16 位计算机的做法。 • 16 位计算机得名就是因为他的字由 位计算机反而是因为 16777216 TB 太大，内存地址被阉割到了 39 位（ 512GB ）。 • 64 位计算机：小丑竟是我自己 lscpu 命令查看处理器相关信息 C 语言中的整数类型 C 语言的基础整数类型 类型 Unix 32 位 Unix 64 位 Windows 32 位 Windows 64 位 char 8 位 8 位 8 位 8 位 short 16 位 16 位 16 位 16

multiply(Numeric *) 的话 依然会违背你们的开 - 闭原则：比如 3.14f * 3 ，两 端是不同的类型，怎么处理所有可能类型的排列组合 ？ 不如放弃类和方法的概念，欣然接受全局函数和重载 。 模板函数：定义 • 使用 template • 其中 T 可以变成任意类型。 • 调用时 twice 即可将 T 替换为 int 。 • 注意有的教材上写做： • template • 是完全等价的，只是个人喜好不同。 模板函数：自动推导参数类型 • 那这样需要手动写 ， 用起 来还不如重载方便了？ • 别担心， C++ 规定： • 当模板类型参数 T 作为函数参数时，则可 以省略该模板参数。自动根据调用者的参 数判断。 模板函数：特化的重载 • 有时候，一个统一的实现（比如 t 模板函数：默认参数类型 • 但是如果模板类型参数 T 没有出现在函数 的参数中，那么编译器就无法推断，就不 得不手动指定了。 • 但是，可以通过 • template • 表示调用者没有指定时， T 默认为 int 。 模板参数：整数也可以作为参数 • template • 可以声明类型 T 作为模板尖括号里的参数。除了 类型，任意整数也可以作为模板参数：

后一次性显示出来的，并不是真的说 Ctrl 就是 ‘ ^’ 这 个字符。 C 语言字符串 第 2 章 C 语言中的字符类型 char • char c = ‘a’; • assert(c == 97); • c = c + 1; • assert(c == ‘b’); • C 语言中规定字符类型为 char 类型，是个 8 位整数。 • 这是因为 ASCII 码只有 0~127 这些整数，而 8 位整数的表示范围是 返回。 帮手函数大全 http://c.biancheng.net/ref/ctype_h/ 关于 char 类型的一个冷知识 • C 语言其实只规定了 unsigned char 是无符号 8 位整数， signed char 是有 符号 8 位整数，而 char 类型只需是 8 位整数即可，可以是有符号也可以 是无符号，任凭编译器决定（ C 标准委员会传统异能， khronos 直呼内行） 的指令集处理无符号 8 位整数更高效”，所以擅自把 char 魔改成无 符号的…… • 顺便一提， C++ 标准保证 char ， signed char ， unsigned char 是三个完全 不同的类型， std::is_same_v 分别判断他们总会得到 false ，无论 x86 还是 arm 。 • 但是奇葩的 C 语言却规定 short ， int ， long ， long long

defl; • } • } • 封装成函数方便使用： • auto val = map_get(m, “key”, “default”); • ss map 常用函数不同情况下的行为分析 类型 C++ 代码 key 已存在 key 不存在 读取 val = m.at(key) 读取这个值 抛出 out_of_range 异常 val = m[key] 读取这个值 创建并零初始化（默认构造函数） 删除这个值 默默放弃 小彭老师四定律： 读取，要用 at 。 写入，要用 [] 。 判断存在，用 count 。 删除，用 erase 。 这四个已经够用了。 map 常用函数不同情况下的行为分析 类型 C++ 代码 key 已存在 key 不存在 读取 val = m.at(key) 读取这个值 抛出 out_of_range 异常 val = m[key] 读取这个值 创建并零初始化（默认构造函数） 判断是否存在，用 m.count(key) 若存在则删除，用 m.erase(key) 第四章：迭代与遍历 物理格式 逻辑格式 面壁者罗辑监督你鞋习 ! 面壁者罗辑监督你鞋习 ! map 的元素类型是…… • set::value_type 是 V 。 • map::value_type 是 pair 。 • 这很合理，虽然只针对 K 排序，但实际上

我知道可以用 accumulate 啦！但是为了引出 lambda 表达式…… 近现代： C++11 引入了 lambda 表达式 现代： C++14 的 lambda 允许用 auto 自动推断类型 当代： C++17 CTAD / compile-time argument deduction / 编 译期参数推断 当代： C++17 引入常用数值算法 未来： C++20 引入区间（ ranges 其实谷歌在其 Code Style 中也明确提出别再通过 () 调用构造函数，需要类型转换时应该 用： 1. static_cast(3.14f) 而不是 int(3.14f) 2. reinterpret_cast(0xb8000) 而不是 (void *)0xb8000 • 更加明确用的哪一种类型转换（ cast ），从而避免一些像是 static_cast(ptr) 译器会自动生成一 个无参构造函数 Pig() ，他会调用每个成员的无参构造函数。 • 但是请注意，这些类型不会被初始化为 0 ： 1. int, float, double 等基础类型 2. void *, Object * 等指针类型 3. 完全由这些类型组成的类 • 这些类型被称为 POD （ plain-old-data ）。 • POD 的存在是出于兼容性和性能的考虑。 <<

https://github.com/zenustech/zeno/tree/zeno2 • Zeno 1.0 所在的分支： https://github.com/zenustech/zeno/ Zeno 中的基本类型 • IObject 一切对象的公共基类。 • INode 一切节点的公共基类。 多态的经典案例 • IObject 具有一个 eatFood 纯虚函数，而 CatObject 和 DogObject IObject * 存储的指针在 delete 时只 会释放 IObject 里的成员，而不会释放 CatObject 里的成员 string m_catFood 。所以 这里的解构函数也是多态的，他根据类型的不同 调用不同派生类的解构函数。 多态用于设计模式之“模板模式” • 这样之后如果有一个任务是要基于 eatFood 做文章，比如要重复 eatFood 两遍。 • 就可以封装到一个函数 eatTwice IOBJECT_DEFINE_CLONE ，其内容是 clone 的实现。这里我们用 std::decay_t 快速获取了 this 指针所指向的类型，也就是当前所在类的类型 。 • 宏的缺点是他不遵守命名空间的规则，宏的名 字是全局可见的，不符合 C++ 的高大尚封装思 想。 • 宏： IOBJECT_DEFINE_CLONE • 高大尚 C++

容器 vector 容器：构造函数 • vector 的功能是长度可变的数组，他里面的数据 存储在堆上。 • vector 是一个模板类，第一个模板参数是数组里 元素的类型。 • 例如，声明一个元素是 int 类型的动态数组 a ： • vector a; vector 容器：构造函数和 size • vector 可以在构造时指定初始长度。 • explicit vector(size_t vector 的这个显式构造函数，默认会把所有元 素都初始化为 0 （不必手动去 memset ）。 • 如果是其他自定义类，则会调用元素的默认构造 函数（例如：数字类型会初始化为 0 ， string 会初始化为空字符串，指针类型会初始化为 nullptr ） • explicit vector(size_t n); vector 容器：构造函数 • 这个显式构造函数还可以指定第二个参数，这样 等价于： • vector a = {1, 2}; • void pop_back() noexcept; vector 容器： back • 要注意的是 pop_back 函数的返回类型是 void ，也就是没有返回值，如果需要获取删除的 值，可以在 pop_back() 之前先通过 back() 获 取末尾元素的值，实现 pop 效果。 • a.back(); • 等价于：