有了无边界的稀疏网格，再也不用担心二维数组要分配多大了。 坐标可以无限延伸，甚至可以是负数！比如 (-1,2) 等…… 他会自动在写入时分配 16x16 的子网格，称之为叶节点 (leaf node) ，而这里的 unordered_map 就是充当根节点 (root node) 。 图片解释稀疏的好处 传统稠密二维数组 无边界稀疏分块哈希表 此外，还是按需分配内存，即使被写入的部分奇形怪状也不会浪费内存。 浪费内存。 这些被写入的部分被称为激活元素 (active element) ，反之则是未激活 (inactive) 。 这就是稀疏的好处，按需分配，自动扩容。 分块则是利用了我们存储的数据常常有着空间局域性的特点，减轻哈希表的压 力，同时在每个块内部也可以快乐地 SIMD 矢量化， CPU 自动预取之类的。 第 2 章：位运算 稀疏的好处：坐标可以是负数 这样即使坐标为负数，或者可以是任意大的坐标，都不会产生越界错误。 结构。 • 下面这个例子中的稀疏数据结构，用这种语言可以表示为 hash().pointer(11).dense(8) 。 封装起来，方便多层解耦 封装起来，方便多层解耦 封装起来，方便多层解耦 封装起来，方便多层解耦 封装起来，方便多层解耦 • 这样就封装好了，通过模板的方式实现了 自定义的稀疏数据结构： • hash().pointer(11).dense(8) 开源的体素处理库：

全部执行完毕。 • 区别在于，一个任务不一定对应一个线程 ，如果任务数量超过 CPU 最大的线程数， 会由 TBB 在用户层负责调度任务运行在 多个预先分配好的线程，而不是由操作系 统负责调度线程运行在多个物理核心。 封装好了： parallel_invoke 更好的例子 第 1 章：并行循环 时间复杂度（ time-efficiency ）与工作量复杂度（ work-efficiency 是元素个数 并行映射 4 个线程，每人处理 2 个元素的映射，花了 2 秒 用电量： 4*2=8 度电 结论：并行映射的时间复杂度为 O(n/c) ，工作复杂度为 O(n) ，其中 c 是线程数量 封装好了： parallel_for 面向初学者： parallel_for 基于迭代器区间： parallel_for_each 二维区间上的 for 循环： blocked_range2d 三维区间上的 log2(n) 次并行 for 即可完成 缩并。 • 这种常用于核心数量很多，比如 GPU 上 的缩并。 结论：改进后的并行缩并的时间复杂度为 O(logn) ，工作复杂度为 O(n) 。 封装好了： parallel_reduce 保证每次运行结果一致： parallel_deterministic_reduce 并行缩并的额外好处：能避免浮点误差，例如求平均值 扫描（ scan ）

container ） C++ 标准库五大件：迭代器（ iterator ） C++ 标准库五大件：算法（ algorithm ） C++ 标准库五大件：仿函数（ functor ） C++ 标准库五大件：分配器（ allocator ） 侯捷 STL 侯捷 STL vector 容器 vector 容器：构造函数 • vector 的功能是长度可变的数组，他里面的数据 存储在堆上。 • vector 的目标长度大于原有的容量时， 就需要重新分配一段更大的连续内存，并 把原数组长度的部分移动过去，多出来的 部分则用 0 来填充。这就导致元素的地址 会有所改变，从而过去 data 返回的指针 以及所有的迭代器对象，都会失效。 vector 容器： resize 到更小尺寸不会导致 data 失效 • 当 resize 的目标长度小于原有的容量时， 不需要重新分配一段连续的内存也不会造 成元素的移动（这个设计是为了性能考 ，因此重新扩容到 5 是不需要重 新分配内存的，也就不会移动元素导致指 针失效。 vector 容器： capacity 函数查询实际的最大容量 • 可以用 capacity() 函数查询已经分配内存的大小，即最大容 量。 • 而 size() 返回的其实是已经存储了数据的数组长度。 • 可以发现当 resize 指定的新长度一个超过原来的最大容量时 时，就会重新分配一段更大容量的内存来存储数组，只有这时

C++20 作为扩展阅读。 C++ 有哪些面向对象思想？ C++ 思想：封装 比如要表达一个数组，需要：起始地址指针 v ，数组大小 nv 将多个逻辑上相关的变量包装成一个类 因此 C++ 的 vector 将他俩打包起来，避免程序员犯错 封装：不变性 比如当我要设置数组大小为 4 时，不能只 nv = 4 还要重新分配数组内存，从而修改数组起始地址 v 常遇到：当需要修改一个成员时，其他也成员需要被修改，否则出错 常遇到：当需要修改一个成员时，其他也成员需要被修改，否则出错 这种情况出现时，就意味着你需要把成员变量的读写封装为成员函数 不变性：请勿滥用封装 • 仅当出现“修改一个成员时，其他也成员要 被修改，否则出错”的现象时，才需要 getter/setter 封装。 • 各个成员之间相互正交，比如数学矢量类 Vec3 ，就没必要去搞封装，只会让程序员 变得痛苦，同时还有一定性能损失：特别 是如果 getter/setter ，我们还是需要实现一下的。 • 发现了吗？其实不管是 size/resize 这样的 get/set 模式也好；自定义的拷贝构造函数 也好； RAII 保证异常安全也好；都是在为 面向对象思想的“封装：不变性”服务。 • 即：保证任何单个操作前后，对象都是处于 正确的状态，从而避免程序读到错误数据 （如空悬指针）的情况。 三五法则：拷贝赋值函数 • 区分两种拷贝可以提高性能。 • int

可以到时再回来看这一小节的内容。 简单来说，decltype(auto) 主要用于对转发函数或封装的返回类型进行推导，它使我们无需显式的 指定 decltype 的参数表达式。考虑看下面的例子，当我们需要对下面两个函数进行封装时： std::string lookup1(); std::string& lookup2(); 在 C++11 中，封装实现是如下形式： std::string look_up_a_string_1() C++11 中，统一了这些概念，将能够被调用的对象的类型，统一称 之为可调用类型。而这种类型，便是通过 std::function 引入的。 C++11 std::function 是一种通用、多态的函数封装，它的实例可以对任何可以调用的目标实体进 行存储、复制和调用操作，它也是对 C++ 中现有的可调用实体的一种类型安全的包裹（相对来说，函数 指针的调用不是类型安全的），换句话说，就是函数的容器。当我们有了函数的容器之后便能够更加方便 << v.capacity() << std::endl; // 输出 0 // 如下可看出 std::vector 的存储是自动管理的，按需自动扩张 // 但是如果空间不足，需要重新分配更多内存，而重分配内存通常是性能上有开销的操作 v.push_back(1); v.push_back(2); v.push_back(3); std::cout << "size:" << v.size()

就像你和同学随手“拉钩”定下的约定，这是 printf 约定俗成的。 • \ 就像正式合同，有法律效力的，这是 C 语言编译器规定好的。 C++ 字符串类 第 3 章 C 语言字符串操作繁琐 封装的 std::string 应运而生 封装的 std::string 应运而生 • string 可以从 const char * 隐式构造： • string s = “hello”; • string 具有 + 、 类型的，他们没有 + 运算 符。 • C++ 为了向前兼容，没办法改变 C 语言的这项规定，只能退而求其次，他另 外定义了一个 string 类，重载了 + 运算符，并告诉同学们：以后尽量用我这 个封装好的类，不要直接用 C 语言的 const char * 。 • 因此如果需要把两个字符串加在一起，就必须至少有一方是 string 才行。 • 可以用 string(“hello”) 这种形式包裹住每个字符串常量，这样就方便用 正确： C++14 新特性：自定义字面量后缀 • 不少同学就觉得这样好麻烦，其他语言都是直接 “ hello” 就是字符串类 型， C++ 还得套一层壳 string(“hello”) 才能变成安全封装的类型，才能用他 的成员函数。 • 因此， C++14 引入了一项缓解“键盘压力”的新特性： • 写 “ hello”_s 就相当于写 operator“”_s(“hello”, 5) ，就相当于

2667*16*2=42672 MB/s • 那么，频率相同的情况下，可以考虑插两块 8GB 的内存， 比插一块 16GB 的内存更快，不过价格可能还是翻倍的。 • 系统会自动在两者之间均匀分配内存，保证读写均匀分配 到两个内存上，实现内存的并行读写，这和磁盘 RAID 有 一定相似之处。 验证一下刚刚的 parallel_add 是不是用足了全部带宽 • 刚刚 a 数组的大小是 1024 MB 等待数据抵达前空转浪费时间。 页对齐的重要性 • 为什么要 4KB ？原来现在操作系统管理内存是用分页 （ page ），程序的内存是一页一页贴在地址空间中的， 有些地方可能不可访问，或者还没有分配，则把这个页设 为不可用状态，访问他就会出错，进入内核模式。 • 因此硬件出于安全，预取不能跨越页边界，否则可能会触 发不必要的 page fault 。所以我们选用页的大小，因为本 来就不 同学们可以课后研究一下。 第 5 章：内存分配与分页 vector ：写入两次，时间都是一样的（理所当然） malloc ：写入两次，第一次明显比第二次慢？ new int[n] ：和 malloc 一样，写入两次，第一次明显比第二次慢？ new int[n]{} ：后面加个花括号，就和 vector 一样，两次一样快了 结论 • 原理，当调用 malloc 时，操作系统并不会实际分配那一块内存，而是将这一段内存标记

小端序的电脑会得到 0x04030201 。 动态数组的分配与释放 如果不是固定长度为 4 的数组呢？ • 刚才的 char a[4] ，数组的长度是一个编译期常 量。如果不是常量呢？ • 比如 char a[n] ，在 gcc 上居然是可以编译通 过的，这是因为他调用了 gcc 特有的 alloca(n) 函数，会在当前函数的栈上分配内存，函数退出 时也会自动释放。 如果不是固定长度为 DIDU_KNOW_THAT_MICROPIG_BUYS_GITHUB 使用 malloc 函数：在堆上分配内存，实现动态数组 • 栈上不能动态分配内存，堆上就可以！ • char a[4] 可以在编译期确定一片栈上的连 续内存，大小为 4 字节， 4 必须是常量 。 • 而调用 stdlib.h 的 malloc(n) 就可以从堆 上分配一段 n 字节的连续内存，这里的 n 就可以不是常量了。 • 栈上的内存会在函数退出时自动释放，而 。 动态数组作为函数参数？不仅要传首地址，还要传数组长度！ • 刚才说定长数组（长度是编译期常量，在栈上分 配的）只需一个起始地址就能确定。 • 而动态长度的数组（通过 malloc 在堆上分配 的）就需要起始地址和数组长度两个，才能确定 下来，也就是 char * 和 int 两个。 • 所以要把动态数组的引用传给函数，需要有两个 参数，一个指针加一个长度。 使用 const 修饰指针指向的值

字。这里显示错误号为 77 ，具体名字是 cudaErrorIllegalAddress 。意思是我们访问了非法的地 址，和 CPU 上的 Segmentation Fault 差不多。 封装好了： helper_cuda.h • 其实 CUDA toolkit 安装时，会默认附带一系列案例代码， 这些案例中提供了一些非常有用的头文件和工具类，比如这 个文件： • /opt/cu ize()) • 即可自动帮你检查错误代码并打印在终端，然后退出。还会 报告出错所在的行号，函数名等，很方便。 堆上分配试试？ • 那你可能会想，难道是因为我的 ret 创建 在栈上，所以 GPU 不能访问，才出错的 ？ • 于是你试图用 malloc 在堆上分配一个 int 来给 GPU 访问，结果还是失败了。 原因： GPU 使用独立的显存，不能访问 CPU 内存 • 原来， (host) 。 GPU 使 用的内存称为设备内存 (device) ，他是显卡上板载 的，速度更快，又称显存。 • 而不论栈还是 malloc 分配的都是 CPU 上的内存 ，所以自然是无法被 GPU 访问到。 • 因此可以用用 cudaMalloc 分配 GPU 上的显存， 这样就不出错了，结束时 cudaFree 释放。 • 注意到 cudaMalloc 的返回值已经用来表示错误代 码，所以返回指针只能通过

3. 两种实现对比 支持操作 两种实现都支持栈定义中的各项操作，数组实现额外支持随机访问，但这已经超出栈的定义范畴，一般不会用 到。 时间效率 在数组（列表）实现中，入栈与出栈操作都是在预先分配好的连续内存中操作，具有很好的缓存本地性，效率 很好。然而，如果入栈时超出数组容量，则会触发扩容机制，那么该次入栈操作的时间复杂度为 ?(?) 。 在链表实现中，链表的扩容非常灵活，不存在上述数组 数组实现的栈在触发扩容时会变慢，但由于扩容是低频操作，因此 总体效率更高； 5. 栈与队列 hello‑algo.com 65 ‧ 链表实现的栈可以提供 更加稳定的效率表现； 空间效率 在初始化列表时，系统会给列表分配“初始容量”，该容量可能超过我们的需求。并且扩容机制一般是按照特 定倍率（比如 2 倍）进行扩容，扩容后的容量也可能超出我们的需求。因此，数组实现栈会造成一定的空间浪 费。 当然，由于结点需要额外存储指针，因此 Addressing」。 6.2.1. 哈希表扩容 哈希函数的最后一步往往是对桶数量 ? 取余，以将哈希值映射到桶的索引范围，从而将 key 放入对应的桶中。 当哈希表容量越大（即 ? 越大）时，多个 key 被分配到同一个桶中的概率就越低，冲突就越少。 因此，在哈希表内的冲突整体比较严重时，编程语言一般通过扩容哈希表来缓解。与数组扩容类似，哈希表扩 容需要将所有键值对从原哈希表移动至新哈希表，开销很大。