51并行算法:如何利用并行处理提高算法的执行效率?.pdf
《51并行算法:如何利用并行处理提高算法的执行效率?.pdf》由会员分享,可在线阅读,更多相关《51并行算法:如何利用并行处理提高算法的执行效率?.pdf(6页珍藏版)》请在三一文库上搜索。
1、51|并行算法:如何利用并行处理提高算法的执行效率? file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/51并行算法:如何利用并行处理提高算法的执行效率?.html2019/1/31 9:33:40 51|并行算法:如何利用并行处理提高算法的执行效率? 时间复杂度是衡量算法执行效率的一种标准。但是,时间复杂度并不能跟性能划等号。在真实的软件开发中,即便在不降低时间复杂度的情况下,也可以通 过一些优化手段,提升代码的执行效率。毕竟,对于实际的软件开发来说,即便是像10%、20%这样微小的性能提升,也是非常可观的。 算法的目的就是为了提高代码执行的
2、效率。那当算法无法再继续优化的情况下,我们该如何来进一步提高执行效率呢?我们今天就讲一种非常简单但又非常 好用的优化方法,那就是并行计算。今天,我就通过几个例子,给你展示一下,如何借助并行计算的处理思想对算法进行改造? 并行排序 假设我们要给大小为8GB的数据进行排序,并且,我们机器的内存可以一次性容纳这么多数据。对于排序来说,最常用的就是时间复杂度为O(nlogn)的三种排 序算法,归并排序、快速排序、堆排序。从理论上讲,这个排序问题,已经很难再从算法层面优化了。而利用并行的处理思想,我们可以很轻松地将这个 给8GB数据排序问题的执行效率提高很多倍。具体的实现思路有下面两种。 第一种是对归并
3、排序并行化处理。我们可以将这8GB的数据划分成16个小的数据集合,每个集合包含500MB的数据。我们用16个线程,并行地对 这16个500MB的数据集合进行排序。这16个小集合分别排序完成之后,我们再将这16个有序集合合并。 第二种是对快速排序并行化处理。我们通过扫描一遍数据,找到数据所处的范围区间。我们把这个区间从小到大划分成16个小区间。我们将8GB的数据划分 到对应的区间中。针对这16个小区间的数据,我们启动16个线程,并行地进行排序。等到16个线程都执行结束之后,得到的数据就是有序数据了。 对比这两种处理思路,它们利用的都是分治的思想,对数据进行分片,然后并行处理。它们的区别在于,第一
4、种处理思路是,先随意地对数据分片,排序之 后再合并。第二种处理思路是,先对数据按照大小划分区间,然后再排序,排完序就不需要再处理了。这个跟归并和快排的区别如出一辙。 这里我还要多说几句,如果要排序的数据规模不是8GB,而是1TB,那问题的重点就不是算法的执行效率了,而是数据的读取效率。因为1TB的数据肯定是存 在硬盘中,无法一次性读取到内存中,这样在排序的过程中,就会有频繁地磁盘数据的读取和写入。如何减少磁盘的IO操作,减少磁盘数据读取和写入的总 量,就变成了优化的重点。不过这个不是我们这节要讨论的重点,你可以自己思考下。 并行查找 我们知道,散列表是一种非常适合快速查找的数据结构。 如果我们
5、是给动态数据构建索引,在数据不断加入的时候,散列表的装载因子就会越来越大。为了保证散列表性能不下降,我们就需要对散列表进行动态扩 容。对如此大的散列表进行动态扩容,一方面比较耗时,另一方面比较消耗内存。比如,我们给一个2GB大小的散列表进行扩容,扩展到原来的1.5倍,也就 是3GB大小。这个时候,实际存储在散列表中的数据只有不到2GB,所以内存的利用率只有60%,有1GB的内存是空闲的。 实际上,我们可以将数据随机分割成k份(比如16份),每份中的数据只有原来的1/k,然后我们针对这k个小数据集合分别构建散列表。这样,散列表的维护 成本就变低了。当某个小散列表的装载因子过大的时候,我们可以单独
6、对这个散列表进行扩容,而其他散列表不需要进行扩容。 还是刚才那个例子,假设现在有2GB的数据,我们放到16个散列表中,每个散列表中的数据大约是150MB。当某个散列表需要扩容的时候,我们只需要额外 增加150*0.5=75MB的内存(假设还是扩容到原来的1.5倍)。不管从扩容的执行效率还是内存的利用率上,这种多个小散列表的处理方法,都要比大散列表高 效。 51|并行算法:如何利用并行处理提高算法的执行效率? file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/51并行算法:如何利用并行处理提高算法的执行效率?.html2019/1/31 9:33
7、:40 当我们要查找某个数据的时候,我们只需要通过16个线程,并行地在这16个散列表中查找数据。这样的查找性能,比起一个大散列表的做法,也并不会下 降,反倒有可能提高。 当往散列表中添加数据的时候,我们可以选择将这个新数据放入装载因子最小的那个散列表中,这样也有助于减少散列冲突。 并行字符串匹配 我们前面学过,在文本中查找某个关键词这样一个功能,可以通过字符串匹配算法来实现。我们之前学过的字符串匹配算法有KMP、BM、RK、BF等。当在 一个不是很长的文本中查找关键词的时候,这些字符串匹配算法中的任何一个,都可以表现得非常高效。但是,如果我们处理的是超级大的文本,那处理的 时间可能就会变得很长
8、,那有没有办法加快匹配速度呢? 我们可以把大的文本,分割成k个小文本。假设k是16,我们就启动16个线程,并行地在这16个小文本中查找关键词,这样整个查找的性能就提高 了16倍。16倍效率的提升,从理论的角度来说并不多。但是,对于真实的软件开发来说,这显然是一个非常可观的优化。 不过,这里还有一个细节要处理,那就是原本包含在大文本中的关键词,被一分为二,分割到两个小文本中,这就会导致尽管大文本中包含这个关键词,但 在这16个小文本中查找不到它。实际上,这个问题也不难解决,我们只需要针对这种特殊情况,做一些特殊处理就可以了。 我们假设关键词的长度是m。我们在每个小文本的结尾和开始各取m个字符串。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 51 并行 算法 如何 利用 处理 提高 执行 效率
链接地址:https://www.31doc.com/p-5530019.html