网站建设实验作业,wordpress整站,app定制开发公司上班怎么样,深圳坪山新楼盘文章目录1. 并行排序2. 并行查找3. 并行字符串匹配4. 并行搜索5. 总结时间复杂度是衡量算法执行效率的一种标准。但是#xff0c;时间复杂度 ! 性能。即便在不降低时间复杂度的情况下#xff0c;也可以通过一些优化手段#xff0c;提升代码的执行效率。即便是像10%、20%这样…
文章目录1. 并行排序2. 并行查找3. 并行字符串匹配4. 并行搜索5. 总结时间复杂度是衡量算法执行效率的一种标准。但是时间复杂度 ! 性能。即便在不降低时间复杂度的情况下也可以通过一些优化手段提升代码的执行效率。即便是像10%、20%这样微小的性能提升也是非常可观的。
算法的目的就是为了提高代码执行效率。当算法无法再继续优化的情况下该如何来进一步提高执行效率呢
一种非常简单又非常好用的优化方法就是并行计算。
1. 并行排序
假设要给8GB的数据进行排序并且机器的内存可以一次容纳这么多数据。对于排序来说最常用的就是时间复杂度为Onlogn的三种排序算法归并排序、快速排序、堆排序。从理论上讲这个排序问题很难再从算法层面优化了。而利用并行的处理思想可以轻松将排序问题的执行效率提高很多倍。实现思路有两种。 归并排序并行处理。将8GB的数据划分成16个小的数据集每个集合包含500MB的数据。我们用16个线程并行对这16个500MB的数据集进行排序。这16个小集合分别排序完之后再将这16个有序集合并。 快速排序并行处理。扫描一遍数据找到数据所处的范围区间。把这个区间从小到大划分成16个小区间。将8GB的数据划分到对应的区间中。针对这16个小区间的数据启动16个线程并行地进行排序。等16个线程都执行结束得到的数据就是有序数据了。
两种处理思路都是分治思想数据分片并行处理。区别在于第一种处理思路是先随意地对数据分片排序之后再合并。第二种处理思路是先对数据按照大小划分区间然后再排序排完序就不需要再处理了。
如果要排序的数据不是8GB而是1TB那问题的重点就不是算法的执行效率了而是数据的读取效率。因为1TB的数据肯定是存在硬盘中无法一次性读取到内存中这样在排序的过程中有频繁地磁盘数据的读写。如何减少磁盘的IO操作就变成了优化的重点。
2. 并行查找
散列表是一种非常适合快速查找的数据结构。
如果是给动态数据构建索引数据不断加入时散列表的装载因子会越来越大。为了保证散列表性能不下降就需要对散列表进行动态扩容。对如此大的散列表进行动态扩容一比较耗时一比较消耗内存。比如给一个2GB大小的散列表进行扩容扩到原来的1.5倍也就是3GB大小。这个时候实际存储在散列表中的数据只有不到2GB所以内存的利用率只有60%有1GB的内存是空闲的。
实际上我们可以将数据随机分割成k份比如16份每份中的数据只有原来的1/k我们针对这k个小数据集分别构建散列表。这样散列表的维护成本就变低了。当某个小散列表的装载因子过大的时候我们可以单独对这个小散列表进行扩容而其他散列表不需要进行扩容。
还是刚才那个例子假设现在有2GB的数据我们放到16个散列表中每个散列表中的数据大约是150MB。当某个散列表需要扩容的时候我们只需要额外增加150*0.575MB的内存假设还是扩容到原来的1.5倍。不管从扩容的执行效率还是内存的利用率上这种多个小散列表的处理方法要比大散列表高效。 要查找某个数据时只需通过16个线程并行地在16个散列表中查找。查找性能比一个大散列表的做法并不会下降反倒有可能提高。 当往散列表中添加数据时可以选择将新数据放入装载因子最小的那个散列表中有助于减少散列冲突。
3. 并行字符串匹配
之前学过的字符串匹配算法有KMP、BM、RK、BF等。如果处理的是超级大的文本处理的时间可能就会变得很长如何加快匹配速度
把大的文本分割成k个小文本。假设k是16我们就启动16个线程并行地在这16个小文本中查找关键词这样整个查找的性能就提高了16倍。16倍效率的提升从理论的角度来说并不多。但对于真实的软件开发来说是一个非常可观的优化。
这里还有一个细节要处理大文本中的关键词被一分为二分割到两个小文本中会导致尽管大文本中包含这个关键词但在16个小文本中查找不到它。需要针对这种特殊情况做特殊处理。
假设关键词的长度是m。在每个小文本的结尾和开始各取m个字符串。前一个小文本的末尾m个字符和后一个小文本的开头m个字符组成一个长度是2m的字符串。在这个长度为2m的字符串中再重新查找一遍就可以补上刚才的漏洞。
4. 并行搜索
前面学习过好几种搜索算法它们是广度优先搜索、深度优先搜索、Dijkstra 最短路径算法、A*启发式搜索算法。对于广度优先搜索算法也可以将其改造成并行算法。
广度优先搜索是一种逐层搜索的搜索策略。基于当前这一层顶点可以启动多个线程并行地搜索下一层的顶点。在代码实现方面原来广度优先搜索的代码实现是通过一个队列来记录已经遍历到但还没有扩展的顶点。现在经过改造之后的并行广度优先搜索算法需要利用两个队列来完成扩展顶点的工作。
假设这两个队列分别是A和B。多线程并行处理队列A中的顶点并将扩展得到的顶点存储在队列B中。等队列A中的顶点都扩展完成之后队列A被清空再并行地扩展队列B中的顶点并将扩展出来的顶点存储在队列A。两个队列循环使用就可以实现并行广度优先搜索算法。
5. 总结
并行计算是一个工程上的实现思路尽管跟算法关系不大但在实际的软件开发中它确实可以非常巧妙地提高程序的运行效率是一种非常好用的性能优化手段。
特别是当要处理的数据规模大之后我们无法通过继续优化算法来提高执行效率的时候就需要在实现的思路上做文章利用更多的硬件资源来加快执行的效率。所以在很多超大规模数据处理中并行处理的思想应用非常广泛比如MapReduce就是一种并行计算框架。
课后思考
假设有n个任务为了提高执行的效率希望能并行执行但是各个任务之间又有一定的依赖关系如何根据依赖关系找出可以并行执行的任务
答拓扑排序没有依赖关系的可以并行处理
