从稀疏数据结构到量化数据类型 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

我知道可以用 accumulate 啦！但是为了引出 lambda 表达式…… 近现代： C++11 引入了 lambda 表达式 现代： C++14 的 lambda 允许用 auto 自动推断类型 当代： C++17 CTAD / compile-time argument deduction / 编 译期参数推断 当代： C++17 引入常用数值算法 未来： C++20 引入区间（ ranges C++17 标准，有时会谈到 C++20 作为扩展阅读。 C++ 有哪些面向对象思想？ C++ 思想：封装 比如要表达一个数组，需要：起始地址指针 v ，数组大小 nv 将多个逻辑上相关的变量包装成一个类 因此 C++ 的 vector 将他俩打包起来，避免程序员犯错 封装：不变性 比如当我要设置数组大小为 4 时，不能只 nv = 4 还要重新分配数组内存，从而修改数组起始地址 v 常遇到： 为成员函数 不变性：请勿滥用封装 • 仅当出现“修改一个成员时，其他也成员要 被修改，否则出错”的现象时，才需要 getter/setter 封装。 • 各个成员之间相互正交，比如数学矢量类 Vec3 ，就没必要去搞封装，只会让程序员 变得痛苦，同时还有一定性能损失：特别 是如果 getter/setter 函数分离了声明和定 义，实现在另一个文件时！ C++ 思想： RAII

com/zenustech/zeno/tree/zeno2 • Zeno 1.0 所在的分支： https://github.com/zenustech/zeno/ Zeno 中的基本类型 • IObject 一切对象的公共基类。 • INode 一切节点的公共基类。 多态的经典案例 • IObject 具有一个 eatFood 纯虚函数，而 CatObject 和 DogObject 继承自 IObject ，他 string m_catFood 。所以 这里的解构函数也是多态的，他根据类型的不同 调用不同派生类的解构函数。 多态用于设计模式之“模板模式” • 这样之后如果有一个任务是要基于 eatFood 做文章，比如要重复 eatFood 两遍。 • 就可以封装到一个函数 eatTwice 里，这个函数只需接受他们共同的基类 IObject 作为参数，然后调 用 eatFood 这个虚函数来做事（而不是直接操作具体的猫和狗本身）。 指针所指向的类型，也就是当前所在类的类型 。 • 宏的缺点是他不遵守命名空间的规则，宏的名 字是全局可见的，不符合 C++ 的高大尚封装思 想。 • 宏： IOBJECT_DEFINE_CLONE • 高大尚 C++ 封装： zeno::IObject::clone() 如何批量定义 clone 函数？ • 另一种方法是定义一个 IObjectClone 模板 类。其模板参数是他的派生类

这些整数就用于是表示这些 可显示字符 (printable character) 的。 计算机如何表达字符 • 除了可显示字符 (printable character) 外， ASCII 还规定了一 类特殊的控制字符 (control character) ： • 0 表示空字符（‘ \0’ ） • 9 表示 Tab 制表符（‘ \t’ ） • 10 表示换行（‘ \n’ ） • 13 表示回车（‘ 命令行中启动 cat 。 • 试试按 Ctrl+R ， Ctrl+E ， Ctrl+C 等一系列 组合键，看到出现了什么？ • 可以看到显示的字符变成了 ^R ^E ^C 等… … • 这是 Unix 类系统显示控制字符的一种方式 。 • 众所周知，我们常用 Ctrl+C 来发送中断信号 （ SIGINT ）强制终止程序，这时常常会看到 一个 ^C 的字样，就是这样出现的。这里我 们的 cat 程序收到 后一次性显示出来的，并不是真的说 Ctrl 就是 ‘ ^’ 这 个字符。 C 语言字符串 第 2 章 C 语言中的字符类型 char • char c = ‘a’; • assert(c == 97); • c = c + 1; • assert(c == ‘b’); • C 语言中规定字符类型为 char 类型，是个 8 位整数。 • 这是因为 ASCII 码只有 0~127 这些整数，而 8 位整数的表示范围是

结构化绑定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3 类型推导 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 auto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 尾返回类型推导 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 decltype(auto) 尖括号 “>” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 类型别名模板 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 变长参数模板

2” 这个 功能，需要： 为什么面向对象在 HPC 不如函数式和元编程香了？ 这个例子要是按传统的面向对象思想，可能是这样： 令 Int, Float, Double 继承 Numeric 接口类并实现 ，其中 multiply(int) 作为虚函数。然后定义： Numeric *twice(Numeric *t) { return t->multiply(2); } 且不说这样的性能问题，你忍得住寂寞去重复定义好 multiply(Numeric *) 的话 依然会违背你们的开 - 闭原则：比如 3.14f * 3 ，两 端是不同的类型，怎么处理所有可能类型的排列组合 ？ 不如放弃类和方法的概念，欣然接受全局函数和重载 。 模板函数：定义 • 使用 template • 其中 T 可以变成任意类型。 • 调用时 twice 即可将 T 替换为 int 。 • 注意有的教材上写做： • template • 是完全等价的，只是个人喜好不同。 模板函数：自动推导参数类型 • 那这样需要手动写 ， 用起 来还不如重载方便了？ • 别担心， C++ 规定： • 当模板类型参数 T 作为函数参数时，则可 以省略该模板参数。自动根据调用者的参 数判断。 模板函数：特化的重载 • 有时候，一个统一的实现（比如 t

复杂度分析：数据结构与算法的评价维度、算法效率的评估方法。时间复杂度、空间复杂度，包括推算 方法、常见类型、示例等。 ‧ 数据结构：常用的基本数据类型，数据在内存中的存储方式、数据结构分类方法。数组、链表、栈、队列、 散列表、树、堆、图等数据结构，内容包括定义、优劣势、常用操作、常见类型、典型应用、实现方法等。 ‧ 算法：查找算法、排序算法、搜索与回溯、动态规划、分治算法，内容包括定义、使用场景、优劣势、时 专有名词和有特指含义的词句会使用“双引号” 标注，以避免歧义。 0. 写在前面 hello‑algo.com 4 本书部分放弃了编程语言的注释规范，以换取更加紧凑的内容排版。注释主要分为三种类型：标题注释、内容 注释、多行注释。 /* 标题注释，用于标注函数、类、测试样例等 */ // 内容注释，用于详解代码 /** * 多行 * 注释 */ 0.2.3. 在动画图解中高效学习 视频和图片相比于文字的信息密 「线性阶」的算法，这也正是时间增长趋势的含义。 时间复杂度的推算方法更加简便。在时间复杂度分析中，我们可以将统计「计算操作的运行时间」简化为统计 「计算操作的数量」，这是因为，无论是运行平台还是计算操作类型，都与算法运行时间的增长趋势无关。因而， 我们可以简单地将所有计算操作的执行时间统一看作是相同的“单位时间”，这样的简化做法大大降低了估算 难度。 时间复杂度也存在一定的局限性。比如，虽然算法

vector 容器 vector 容器：构造函数 • vector 的功能是长度可变的数组，他里面的数据 存储在堆上。 • vector 是一个模板类，第一个模板参数是数组里 元素的类型。 • 例如，声明一个元素是 int 类型的动态数组 a ： • vector a; vector 容器：构造函数和 size • vector 可以在构造时指定初始长度。 • explicit vector(initializer_list list); • explicit vector(size_t n); vector 容器：构造函数 • 这在对于只能用花括号初始化的类成员来说，就 有很大问题： • vector a{4}; • 会得到长度为 1 只有一个元素 4 的数组。 • 但还是可以用这种写法强制调用显式构造函数： • vector vector(initializer_list list); • explicit vector(size_t n); vector 容器：构造函数 • 这在对于只能用花括号初始化的类成员来说，就 有很大问题： • vector a{4}; • 会得到长度为 1 只有一个元素 4 的数组。 • 但还是可以用这种写法强制调用显式构造函数： • vector

3000000 微秒，也就是 3 秒 • C 语言原始的 API ，没有类型区分，导致很容易弄错单位，混淆时间点和时间段。 • 比如 t0 * 3 ，乘法对时间点而言根本是个无意义的计算，然而 C 语言把他们看做一样的 long 类型，从而容易让程序员犯错。 C++11 引入的时间标准库： std::chrono • 利用 C++ 强类型的特点，明确区分时间点与时间段，明确区分不同的时间单位。 • • 时间点例子： 2022 年 1 月 8 日 13 点 07 分 10 秒 • 时间段例子： 1 分 30 秒 • 时间点类型： chrono::steady_clock::time_point 等 • 时间段类型： chrono::milliseconds ， chrono::seconds ， chrono::minutes 等 • 方便的运算符重载：时间点 + 时间段 = 时间点，时间点 案例：计算花费的时间 时间段：作为 double 类型 duration_cast 可以在任意的 duration 类型之间转换 duration 表示用 T 类型表示，且时间单位是 R R 省略不写就是秒， std::milli 就是毫秒， std::micro 就是微秒 seconds 是 duration 的类型别名 milliseconds 是 duration

0 码力 | 79 页 | 14.11 MB | 1 年前

3

3.1. 数据结构分类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2. 基本数据类型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.3. 数字编码 * . . . . 本书主要内容包括： ‧ 复杂度分析：数据结构和算法的评价维度，算法效率的评估方法。时间复杂度、空间复杂度的推算方 法、常见类型、示例等。 ‧ 数据结构：基本数据类型，数据结构的分类方法。数组、链表、栈、队列、散列表、树、堆、图等数据 结构的定义、优缺点、常用操作、常见类型、典型应用、实现方法等。 ‧ 算法：搜索、排序、分治、回溯、动态规划、贪心等算法的定义、优缺点、效率、应用场景、解题步骤、 涉及到编程语言之间不一致的名词，本书均以 Python 为准，例如使用 None 来表示“空”。 ‧ 本书部分放弃了编程语言的注释规范，以换取更加紧凑的内容排版。注释主要分为三种类型：标题注 释、内容注释、多行注释。 /* 标题注释，用于标注函数、类、测试样例等 */ // 内容注释，用于详解代码 /** * 多行 * 注释 */ 0.2.2. 在动画图解中高效学习 相较于文字，视频和图片具有更