【数据结构与算法】【算法思想】【算法应用】【排序查找搜索】并行

Dear 丶 2022-12-10 03:42 200阅读 0赞

算法的目的就是为了提高代码执行的效率。当算法无法再继续优化的情况下，需要借助并行计算的处理思想对算法进行改造。

#### 并行排序 ####

假设要给大小为 8GB 的数据进行排序，最常用的是三种排序算法，归并排序、快速排序、堆排序，时间复杂度为 O(nlogn) 。从理论上讲，已经很难再从算法层面优化了。而利用并行的处理思想可以将执行效率提高很多倍。

第一种是对归并排序并行化处理

*  将这8GB 的数据**划分**成 16 个小的**数据集合**，每个集合包含 500MB 的数据。
 *  用 16 个线程，并行地对这 16 个 500MB 的数据集合进行排序。
 *  16 个小集合分别排序完成之后，再将这 16 个有序集合合并。

第二种是对快速排序并行化处理

*  将数据扫描一遍，找到数据所处的**范围区间**，在按从小到大划分成 16 个小区间。
 *  将 8GB 的数据划分到对应的16 个小区间中，启动 16 个线程，并行地进行排序。
 *  等到 16 个线程都执行结束后，得到的数据就是有序数据了。

对比这两种处理思路

*  共同点：它们利用的都是分治的思想，对数据进行分片，然后并行处理。
 *  不同点：  
    （1）第一种处理思路是，先随意地对数据分片，排序之后再合并。  
    （2）第二种处理思路是，先对数据按照大小划分区间后再排序，排完序就不需要再处理了。
 *  这个跟归并和快排的区别如出一辙。

#### 并行查找 ####

散列表是一种非常适合快速查找的数据结构。

弊端：

*  如果给动态数据构建索引，数据不断加入会使散列表的**装载因子**越来越大
 *  为了保证散列表性能不下降，就需要对散列表进行动态扩容
 *  对巨大的散列表进行动态扩容，不仅比较耗时，还比较消耗内存  
    优化：
 *  实际上可以将数据随机分割成 k 份（比如 16 份），每份中的数据只有原来的 1/k
 *  然后针对这 k 个小数据集合分别构建散列表。这样，散列表的维护成本就变低了
 *  当某个小散列表的装载因子过大的时，可以单独对这个散列表进行扩容，而其他散列表不需要进行扩容。
 *  当要查找数据时，通过 16 个线程并行地在这16 个散列表中查找数据。这样的查找性能，比起一个大散列表的做法，也并不会下降，反倒有可能提高。
 *  当往散列表中添加数据时，可以将新数据放入装载因子最小的散列表中，这样也有助于减少散列冲突。

假设有 2GB 的数据，放到 16 个散列表中，每个散列表中的数据大约是 150MB。当某个散列表需要扩容的时候，我们只需要额外增加 150\*0.5=75MB 的内存（假设还是扩容到原来的 1.5 倍）。不管从扩容的执行效率还是内存的利用率上，这种多个小散列表的处理方法，都要比大散列表高效

#### 并行字符串匹配 ####

在文本中查找某个关键词可以通过字符串匹配算法来实现，字符串匹配算法有 KMP、BM、RK、BF 等

如果处理的是超级大的文本，可以把大的文本，分割成 k 个小文本。假设 k 是 16，就启动 16 个线程，并行地在这 16 个小文本中查找关键词，这样整个查找的性能就提高了 16 倍

当长度m的待匹配字符串被分割后，可以获取前一段长度为m的尾部和长度为m的当前段的头部组合成2m长的自费赴川进行匹配。

#### 并行搜索 ####

搜索算法有：广度优先搜索、深度优先搜索、Dijkstra 最短路径算法、A\* 启发式搜索算法。对于广度优先搜索算法，也可以将其改造成并行算法。

*  广度优先搜索是一种逐层搜索的搜索策略
 *  基于当前这一层顶点，我们可以启动多个线程，并行地搜索下一层的顶点
 *  在代码实现方面，原来广度优先搜索的代码实现，是通过一个队列来记录已经遍历到但还没有扩展的顶点
 *  经过改造之后的并行广度优先搜索算法，需要利用两个队列来完成扩展顶点的工作（决多线程的并发问题）

### 【算法总结】 ###

**存储**  
实最底层的数据结构是<addr,value>，按照存储介质是否连续、是否显示制定key又可以分为数组、链表和hash，其中数组可以认为是一种<index,arr\[index\]>，链表是<p,\*p>，然后在这基础之上衍生出了一维的线性表、栈、队列，散列表，二维的树(平衡二叉树、红黑树、跳表)，三维的图，还有就是各种数据结构灵活组合的数据结构，这里的跳表可以算是组合类型的，但是它的使用范围很多，所以划到了二维中。  
**算法**  
排序、分治、贪心、回溯、动态规划

[笔记整理来源： 王争 数据结构与算法之美][Link 1]

[Link 1]: https://s1.ax1x.com/2020/08/03/aUh2TS.png