首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。
时间复杂度是衡量算法执行效率的一种标准。但是，时间复杂度并不能跟性能划等号。算法的目的是为了提高代码执行的效率。当算法无法再继续优化的情况下，需要借助另外一种优化方法提高执行效率——并行计算。那么如何借助并行计算的处理思想对算法进行改造？
并行排序
假如要对8GB大小的数据排序，最常用的就是时间复杂度为 $O(nlogn)$ 三种排序算法——归并排序、快速排序、堆排序。理论上，这个排序问题很难再从算法层面优化了。但是借助并行的处理思想，可以轻松地把执行效率提高很多倍。具体实现思路有如下两种：
第一种是对归并排序并行化处理。可以把这8GB的数据划分为16个大小为500MB的小数据集合，使用16个线程并行地对这16个500MB 的数据集合进行排序，然后再将这16个有序集合合并。
第二种是对快速排序并行化处理。先扫描一遍数据，找到数据所处的范围区间，把这个区间按照从小到大划分成16个小区间。然后把8GB数据划分到对应的区间中。针对这 16 个小区间的数据，启动 16 个线程，并行地进行排序。等到 16 个线程都执行结束之后，得到的数据就是有序数据了。
这两种处理思路，都利用了分治的思想，对数据进行分片，然后并行处理。区别在于，第一种处理思路是，先随意地对数据分片，排序之后再合并。第二种处理思路是，先对数据按照大小划分区间，然后再排序，排完序就不需要再处理了。这个跟归并和快排的区别如出一辙。
若排序的数据规模不是8GB，而是1TB，那问题的重点就不是算法的执行效率了，而是数据的读取效率。如何减少磁盘的 IO 操作，减少磁盘数据读取和写入的总量，就变成了优化的重点。
并行查找
散列表是一种非常适合快速查找的数据结构。若给动态数据构建索引，在数据不断加入时，散列表的装载因子就会越来越大。为了保证散列表性能不下降，就需要对散列表进行动态扩容。对如此大的散列表动态扩容，一方面比较耗时，另一方面比较浪费内存。比如给2GB大小的散列表扩容到之前的1.5倍，即3GB大小。但实际上此时散列表中数据还不到2GB，内存利用率只有60%。
实际上，可以把数据随机分割成 k 份（比如16份），每份中的数据只有原来的 1/k，然后针对这 k 个小数据集合分别构建散列表。这样，散列表的维护成本就变低了。当某个小散列表的装载因子过大时，可以单独对这个散列表进行扩容，而其他散列表不需要进行扩容。
比如刚才例子，有2GB的数据，分别放到16个散列表中，每个散列表中的数据大约是 150MB。当某个散列表需要扩容的时候，只需要额外增加 1500.5=75MB 的内存（假设还是扩容到原来的 1.5 倍）。不管从扩容的执行效率还是*内存的利用率上，这种多个小散列表的处理方法，都要比大散列表高效。
当要查找某个数据的时候，只需要通过 16 个线程，并行地在这 16 个散列表中查找数据。这样的查找性能，比起一个大散列表的做法，也并不会下降，反倒有可能提高。
当往散列表中添加数据的时候，可以选择将这个新数据放入装载因子最小的那个散列表中，这样也有助于减少散列冲突。
并行字符串匹配
在文本中查找某个关键词功能，可以通过字符串匹配算法比如KMP、BM、RK、BF等来实现。对于一个不是很长的文本中查找关键词的时候，任何一个字符串匹配算法都非常高效。但是若处理的是超级大的文本，处理的时间可能会很长。这怎么处理呢？
类似于之前思路，可以把大文本分割成 k 个小文本。假设 k 是 16，就启动 16 个线程，并行地在这 16 个小文本中查找关键词，这样整个查找的性能就提高了 16 倍。不过，有一个漏洞，原本包含在大文本中的关键词被一分为二到两个小文本中，导致尽管大文本中包含这个关键词，但在这 16 个小文本中查找不到它。这时需要针对这种特殊情况做特殊处理。
假设关键词的长度是 m。在每个小文本的结尾和开始各取 m 个字符串。前一个小文本的末尾 m 个字符和后一个小文本的开头 m 个字符，组成一个长度是 2m 的字符串。再拿关键词，在这个长度为 2m 的字符串中再重新查找一遍，就可以补上刚才的漏洞了。
并行搜索
前面学过好几种搜索算法——广度优先搜索、深度优先搜索、Dijkstra 最短路径算法、A* 启发式搜索算法。对于广度优先搜索算法，可以将其改造成并行算法。
广度优先搜索是一种逐层搜索的搜索策略。基于当前这一层顶点，可以启动多个线程，并行地搜索下一层的顶点。在代码实现方面，原来广度优先搜索的代码实现，是通过一个队列来记录已经遍历到但还没有扩展的顶点。现在，经过改造之后的并行广度优先搜索算法，需要利用两个队列来完成扩展顶点的工作。
假设这两个队列分别是队列 A 和队列 B。多线程并行处理队列 A 中的顶点，并将扩展得到的顶点存储在队列 B 中。等队列 A 中的顶点都扩展完成之后，队列 A 被清空，再并行地扩展队列 B 中的顶点，并将扩展出来的顶点存储在队列 A。这样两个队列循环使用，就可以实现并行广度优先搜索算法。
总结引申
上节通过实际开发中”索引“技术点，回顾了之前学过的一些支持动态数据集合的数据结构。本节又通过”并行算法“，回顾了之前学过的一些算法。
本节主要通过并行排序、查找、搜索、字符串匹配，展示了并行处理的实现思路，也就是对数据进行分片，对没有依赖关系的任务，并行地执行。
课后思考
假设有 n 个任务，为了提高执行的效率，希望能并行执行任务，但是各个任务之间又有一定的依赖关系，如何根据依赖关系找出可以并行执行的任务？
答：用一个有向图来存储任务之间的依赖关系，然后用拓扑排序的思想来执行任务，每次都找到所有入度为0的，放在队列里，启动线程池开始执行，队列里的任务并行执行完毕，再次调用拓扑排序找到入度为0的所有任务，放入队列，直到所有任务跑完。
