时间复杂度（ time-efficiency ）与工作量复杂度（ work-efficiency ） • 在“小学二年级”算法课里，我们学过复杂度的概念，意思是算法执行所花费的时间取决于数据量 的大小 n ，比如 O(n²) 表示花费时间和数据量的平方成正比。 • 对于并行算法，复杂度的评估则要分为两种： • 时间复杂度：程序所用的总时间（重点） • 工作复杂度：程序所用的计算量（次要） • 这 这两个指标都是越低越好。时间复杂度决定了快慢，工作复杂度决定了耗电量。 • 通常来说，工作复杂度 = 时间复杂度 * 核心数量 • 1 个核心工作一小时， 4 个核心工作一小时。时间复杂度一样，而后者工作复杂度更高。 • 1 个核心工作一小时， 4 个核心工作 1/4 小时。工作复杂度一样，而后者时间复杂度更低。 • 并行的主要目的是降低时间复杂度，工作复杂度通常是不变的。甚至有牺牲工作复杂度换取时间 复杂度的情形。 8 个元素的映射，花了 8 秒 用电量： 1*8=8 度电 结论：串行映射的时间复杂度为 O(n) ，工作复杂度为 O(n) ，其中 n 是元素个数 并行映射 4 个线程，每人处理 2 个元素的映射，花了 2 秒 用电量： 4*2=8 度电 结论：并行映射的时间复杂度为 O(n/c) ，工作复杂度为 O(n) ，其中 c 是线程数量 封装好了： parallel_for 面向初学者： parallel_for

月，我在书店看到了深入浅出MFC 这本书，让我想起自己曾经暗暗告诉过自 己：Application Framework 真是一个好东西。我在书店驻足察看这本书五分钟之后，我便知 道这本书是一定要买下的。适巧我工作上的项目进度也到了一个即将完成的阶度，所以我便 一口气将这本书给读完了，而且是彻彻底底读了两遍。 我个人特别喜欢第３章：MFC 六大关键技术之仿真。这章内容的设计的确在MFC 丛林中， 大刀阔 书中的每个 中文字都看得懂，但是整段落就是不知他到底在说啥！因此看到书的作者是您，感觉上就是 一个品质上的保证，必定二话不说，抱回家啰！虽然眼前用不到，但是翻翻看，大致了解一 下，待有空时或是工作上需要时再好好细读。 网络书局的盛行，让我也开始上网买些书。但是我只敢买像您的书！有品质嘛！其它的可就 不敢直接买啰，总是必須到书局翻翻看，确定一下內容，才可能考虑。 vii 台北市Jedi What、Why。后来整理书架，发现这本书，就停下来拿来看，结果越看越搞懂这些Windows 程序到底如何How、What、Why。正如您的序所说「只用一样东西，不明白它的道理，实在 不高明」，感谢您能不计代价去做些不求近利的深耕工作，让我们一群读者能少走冤枉路。 谢谢您!! 祝您身体健康!! ix Chengwei chengwei@accton.com.tw 最近正拜读大作深入浅出MFC，明显感受到作者写书之负责用心（不论内容、排版设计、

本项目旨在创建一本开源、免费、对新手友好的数据结构与算法入门教程。 ‧ 全书采用动画图解，内容清晰易懂、学习曲线平滑，引导初学者探索数据结构与算法的知识地图。 ‧ 源代码可一键运行，帮助读者在练习中提升编程技能，了解算法工作原理和数据结构底层实现。 ‧ 提倡读者互助学习，欢迎大家在评论区提出问题与分享见解，在交流讨论中共同进步。 0.1.1 读者对象 若你是算法初学者，从未接触过算法，或者已经有一些刷题经验，对数据结构与算法有模糊的认识，在会与 ch0、MwumLi、martinx、ZnYang2018、hugtyftg、 logan‑qiu、psychelzh、Keynman、KeiichiKasai 和 0130w。 本书的代码审阅工作由 coderonion、curtishd、Gonglja、gvenusleo、hpstory、justin‑tse、khoaxuantu、 krahets、night‑cruise、nuomi1、Reanon 并运行所有代码。 与阅读代码相比，编写代码的过程往往能带来更多收获。动手学，才是真的学。 第 0 章 前言 www.hello‑algo.com 6 图 0‑3 运行代码示例 运行代码的前置工作主要分为三步。 第一步：安装本地编程环境。请参照附录所示的教程进行安装，如果已安装，则可跳过此步骤。 第二步：克隆或下载代码仓库。前往 GitHub 仓库。如果已经安装 Git ，可以通过以下命令克隆本仓库：

本專案旨在建立一本開源、免費、對新手友好的資料結構與演算法入門教程。 ‧ 全書採用動畫圖解，內容清晰易懂、學習曲線平滑，引導初學者探索資料結構與演算法的知識地圖。 ‧ 源程式碼可一鍵執行，幫助讀者在練習中提升程式設計技能，瞭解演算法工作原理和資料結構底層實 現。 ‧ 提倡讀者互助學習，歡迎大家在評論區提出問題與分享見解，在交流討論中共同進步。 0.1.1 讀者物件 若你是演算法初學者，從未接觸過演算法，或者已經有一些刷題經驗，對資料結構與演算法有模糊的認識， h0、MwumLi、martinx、ZnYang2018、hugtyftg、 logan‑qiu、psychelzh、Keynman、KeiichiKasai 和 0130w。 本書的程式碼審閱工作由 coderonion、curtishd、Gonglja、gvenusleo、hpstory、justin‑tse、khoaxuantu、 krahets、night‑cruise、nuomi1、Reanon 程式碼。 與閱讀程式碼相比，編寫程式碼的過程往往能帶來更多收穫。動手學，才是真的學。 第 0 章 前言 www.hello‑algo.com 6 圖 0‑3 執行程式碼示例 執行程式碼的前置工作主要分為三步。 第一步：安裝本地程式設計環境。請參照附錄所示的教程進行安裝，如果已安裝，則可跳過此步驟。 第二步：克隆或下載程式碼倉庫。前往 GitHub 倉庫。如果已經安裝 Git ，可以透過以下命令克隆本倉庫：

802、primexiao、nidhoggfgg、1ch0、MwumLi、ZnYang2018、hugtyftg、 logan‑qiu、psychelzh 和 Keynman 。 本书的代码审阅工作由 codingonion、curtishd、Gonglja、gvenusleo、hpstory、justin‑tse、krahets、 night‑cruise、nuomi1 和 Reanon 至少通读并运行所有代码。 与阅读代码相比，编写代码的过程往往能带来更多收获。动手学，才是真的学。 第 0 章 前言 hello‑algo.com 6 图 0‑3 运行代码示例 运行代码的前置工作主要分为三步。 第一步：安装本地编程环境。请参照附录所示的教程进行安装，如果已安装，则可跳过此步骤。 第二步：克隆或下载代码仓库。前往 GitHub 仓库。如果已经安装 Git ，可以通过以下命令克隆本仓库： 如果感觉以下内容理解困难，可以在读完“栈”章节后再来复习。 那么，迭代和递归具有什么内在联系呢？以上述递归函数为例，求和操作在递归的“归”阶段进行。这意味 着最初被调用的函数实际上是最后完成其求和操作的，这种工作机制与栈的“先入后出”原则异曲同工。 事实上，“调用栈”和“栈帧空间”这类递归术语已经暗示了递归与栈之间的密切关系。 1. 递：当函数被调用时，系统会在“调用栈”上为该函数分配新的栈帧，用于存储函数的局部变量、参数、

233、xb534、luluxia、yanedie、thomasq0、 YangXuanyi 和 th1nk3r‑ing 。 第 0 章 前言 hello‑algo.com 4 本书的代码审阅工作由 codingonion、Gonglja、gvenusleo、hpstory、justin‑tse、krahets、night‑cruise、 nuomi1 和 Reanon 完成（按照首字母顺 至少通读并运行所有代码。 与阅读代码相比，编写代码的过程往往能带来更多收获。动手学，才是真的学。 第 0 章 前言 hello‑algo.com 6 图 0‑3 运行代码示例 运行代码的前置工作主要分为三步。 第一步：安装本地编程环境。请参照附录所示的教程进行安装，如果已安装，则可跳过此步骤。 第二步：克隆或下载代码仓库。前往 GitHub 仓库。如果已经安装 Git ，可以通过以下命令克隆本仓库： 如果感觉以下内容理解困难，可以在读完“栈”章节后再来复习。 那么，迭代和递归具有什么内在联系呢？以上述递归函数为例，求和操作在递归的“归”阶段进行。这意味 着最初被调用的函数实际上是最后完成其求和操作的，这种工作机制与栈的“先入后出”原则异曲同工。 事实上，“调用栈”和“栈帧空间”这类递归术语已经暗示了递归与栈之间的密切关系。 1. 递：当函数被调用时，系统会在“调用栈”上为该函数分配新的栈帧，用于存储函数的局部变量、参数、

Keynman, youshaoXG, lipusheng, Javesun99, tao363, czruby, gltianwen, liuxjerry, yabo083. 本书的代码审阅工作由 Gonglja, gvenusleo, hpstory, justin‐tse, krahets, nuomi1, Reanon, sjinzh 完 成（按照首字母顺序排列）。感谢他们付出的时 如果时间允许，建议你参照代码自行敲一遍。如果学习时间有限，请至少通读并运行所有代码。 与阅读代码相比，编写代码的过程往往能带来更多收获。动手学，才是真的学。 图 0‑3 运行代码示例 运行代码的前置工作主要分为三步。 第一步：安装本地编程环境。请参照附录教程进行安装，如果已安装则可跳过此步骤。 第二步：下载代码仓。如果已经安装 Git ，可以通过以下命令克隆本仓库。 git clone https://github hello‑algo.com 59 3.4.3 Unicode 字符集 随着计算机的蓬勃发展，字符集与编码标准百花齐放，而这带来了许多问题。一方面，这些字符集一般只定 义了特定语言的字符，无法在多语言环境下正常工作。另一方面，同一种语言也存在多种字符集标准，如果 两台电脑安装的是不同的编码标准，则在信息传递时就会出现乱码。 那个时代的研究人员就在想：如果推出一个足够完整的字符集，将世界范围内的所有语言和符号都收录其

Keynman, youshaoXG, lipusheng, Javesun99, tao363, czruby, gltianwen, liuxjerry, yabo083. 本书的代码审阅工作由 Gonglja, gvenusleo, hpstory, justin‐tse, krahets, nuomi1, Reanon, sjinzh 完 成（按照首字母顺序排列）。感谢他们付出的时 hello‑algo.com 46 3.4.3. Unicode 字符集 随着计算机的蓬勃发展，字符集与编码标准百花齐放，而这带来了许多问题。一方面，这些字符集一般只定 义了特定语言的字符，无法在多语言环境下正常工作；另一方面，同一种语言也存在多种字符集标准，如果 两台电脑安装的是不同的编码标准，则在信息传递时就会出现乱码。 那个时代的人们就在想：如果推出一个足够完整的字符集，将世界范围内的所有语言和符号都收录其中，不 扩容机制：插入元素时可能超出列表容量，此时需要扩容列表。扩容方法是根据扩容倍数创建一个更大 的数组，并将当前数组的所有元素依次移动至新数组。在本示例中，我们规定每次将数组扩容至之前的 2 倍。 本示例旨在帮助读者直观理解列表的工作机制。实际编程语言中，列表实现更加标准和复杂，各个参数的设 定也非常有考究，例如初始容量、扩容倍数等。感兴趣的读者可以查阅源码进行学习。 // === File: my_list.cpp ===

宽。三级缓存也装不下，那就取决于主内存 的带宽了。 • 结论：要避免 mem-bound ，数据量尽量足 够小，如果能装的进缓存就高效了。 L2: 256 KB L3: 12 MB 缓存的工作机制：读 • 缓存中存储的数据结构： • struct CacheEntry { • bool valid; • uint64_t address; • char data[64]; 个字节时，实际会导致 0x0040~0x0080 的 64 字节数据整个被读取到缓存中。 • 这就是为什么我们喜欢把数据结构的起始地址和大小对齐到 64 字节，为的是不要浪费缓存行的存储空间。 缓存的工作机制：写 • 缓存中存储的数据结构： • struct CacheEntry { • bool valid, dirty; • uint64_t address; • char ，决定要预取的地址。一般来说只有线性的地址访问规律（包括顺序、 逆序；连续、跨步）能被识别出来，而如果你的访存是随机的，那就没 办法预测。遇到这种突如其来的访存时， CPU 不得不空转等待数据的抵 达才能继续工作，浪费了时间。 解决：按更大的分块（ 4096 字节）随机访问 • 解决方案就是，把分块的大小调的更大一些，比 如 4KB 那么大，即 64 个缓存行，而不是一个。 • 这样一次随机访问之后会伴随着

这时, stored_value == 100, value == 100. // 因为 copy_value 保存的是引用 } 3. 隐式捕获 手动书写捕获列表有时候是非常复杂的，这种机械性的工作可以交给编译器来处理，这时 候可以在捕获列表中写一个 & 或 = 向编译器声明采用引用捕获或者值捕获. 总结一下，捕获提供了 Lambda 表达式对外部值进行使用的功能，捕获列表的最常用的四种形式可 产生的那个返回值作为一个临时值，一 旦被 v 复制后，将立即被销毁，无法获取、也不能修改。而将亡值就定义了这样一种行为：临时的值能 够被识别、同时又能够被移动。 在 C++11 之后，编译器为我们做了一些工作，此处的左值 temp 会被进行此隐式右值转换，等价于 static_cast &&>(temp)，进而此处的 v 会将 foo 局部返回的值进行移动。也就是 后面我们将会提到的移动语义。 最重要的几个特 性之一的『内存模型』，它们为 C++ 在标准化高性能计算中提供了重要的基础。 习题 1. 请编写一个简单的线程池，提供如下功能： ThreadPool p(4); // 指定四个工作线程 // 将任务在池中入队，并返回一个 std::future auto f = pool.enqueue([](int life) { return meaning; }, 42); //