美文网首页On lzq ways
高级应用篇六

高级应用篇六

作者: zhengqiuliu | 来源:发表于2019-06-24 22:06 被阅读4次

问题:算法的目的就是为了提高代码的执行效率。那当算法无法再继续优化的情况下,我们该如何来进一步提高执行效率呢?那就是并行计算。如何借助并行计算的处理思想对算法进行改造?

并行排序:假设我们要给大小为8GB的数据进行排序,并且我们的机器内存可以一次性容纳这么多数据。对于排序来说,最常用的就是时间复杂度为O(nlogn)的三种排序算法,归并排序,快速排序,堆排序。但是利用并行处理思想,我们可以很轻松地将这个给8GB数据排序问题的执行效率提高很多倍。

第一种是对归并排序并行化处理。将8GB的数据划分成16个小的数据集合,每个集合包含500MB的数据。我们用16个线程,并行地对这16个500MB的数据集合进行排序。分别排序完成之后,再将这16个有序集合合并。

第二种是对快速排序并行化处理。扫描一遍数据,找到数据所处的范围区间。把这个区间从小到大划分成16个小区间。我们将8GB的数据划分到对应的区间中。针对这16个小区间的数据,我们启动16个线程,并行地进行排序。等到16个线程都执行结束之后,得到的数据就是有序数据了。

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

我们给动态数据构建索引,在数据不断加入的时候,散列表的装载因子就会越来越大。为了保证散列表性能不下降,就需要对散列表进行动态扩容。对大的散列表进行动态扩容,一方面比较耗时,另一方面比较消耗内存。

实际上,我们可以将数据随机分割成k份,每份中数据都只有原来的1/k,然后我们针对这k个小数据集合分别构建散列表。这样,散列表的维护成本就变低了。当某个小散列表的装载因子过大的时候,我们可以单独对这个散列表进行扩容,而其它散列表不需要进行扩容。

当我们要查找某个数据的时候,我们只需要通过k个线程,并行地在k个散列表中查找数据。这样的查找性能,比起一个大散列表的做法,不会下降,反倒有可能提高。

并行字符串匹配:前面学过的字符串匹配算法有KMP, BM, RK, BF等。当在一个不是很长的文本中查找关键词的时候,这些字符串匹配算法中的任何一个,都可以表现得非常高效。但是如果处理超级大的文本呢?

我们就可以把大的文本,分割成k个小文本,启动k个线程,并行地在这k个小文本中查找关键词,这样整个查找的性能就提高了16倍。但是原本包含的大文本中的关键词,被一分为二,分割到两个小文本中,就会导致尽管大文本中包含的这个关键词,但在这k个小文本中查找不到它。这就需要特殊处理,假设关键词长度是m。我们在每个小文本的结尾和开始各取m个字符串。前一个小文本的末尾m个字符和后一个小文本的开头m个字符,组成一个2m的字符串,在这个长度为2m的字符串中再重新查找一遍。

并行搜索:前面涉及过好几种搜索算法,分别是广度优先搜索,深度优先搜索,Dijkstra最短路径算法,A*启发式搜索算法。对于广度优先搜索算法,我们可以将其改造成并行算法。

广度优先搜索是一种逐层搜索的搜索策略。基于当前这一层顶点,我们可以启动多个线程,并行地搜索下一层的顶点。

原来广度优先搜索的代码实现,是通过一个队列来记录已经遍历到但还没有扩展的顶点。现在,经过改造之后的并行广度优先搜索算法,我们需要利用两个队列来完成扩展顶点的工作。

两个队列分别是队列A和队列B。多线程并行处理队列A中顶点,并将扩展得到的顶点存储再队列B中。等队列A中顶点都扩展完成之后,队列A被清空,我们再并行的扩展队列B中的顶点,并将扩展出来的顶点存储再队列A。这样两个队列循环使用,就可以实现并行广度优先搜索算法了。

相关文章

  • 高级应用篇六

    问题:算法的目的就是为了提高代码的执行效率。那当算法无法再继续优化的情况下,我们该如何来进一步提高执行效率呢?那就...

  • 高级应用篇五

    问题:人物处于游戏地图的某个位置的时候,我们用鼠标点击另一个相对较远的位置时,人物会自动绕过很多障碍物走过去,玩过...

  • 高级应用篇四

    问题:在工作中,为了加速数据库中数据的查找速度,我们常用的处理思路是,对表中数据创建索引。那你是否思考过,数据库索...

  • 高级应用篇一

    问题一:如何确定代码源文件的编译依赖关系?一个完整的项目会包含很多代码源文件。编译器在编译整个项目时,需要按照依赖...

  • 高级应用篇二

    问题:网页爬虫是搜索引擎中非常重要的系统,负责爬取几十亿,上百亿的网页。而同一个网页链接有可能被包含在多个页面中,...

  • 高级应用篇三

    问题一:如果你是一名手机应用开发工程师,让你实现一个简单的垃圾短信过滤功能以及骚扰电话拦截功能,该用什么样的数据结...

  • Greenplum企业应用实战(笔记):第六章 Greenplu

    第六章 Greenplum 高级应用 [TOC] 本章将介绍一些 Greenplum 的高级特性,主要是与其他关系...

  • iOS开发 多线程的高级应用(一)

    iOS开发 多线程的高级应用(一) OS开发 多线程的高级应用(一)

  • rabbitMQ高级整合应用第三篇 SimpleMessageL

    ​rabbitMQ精讲系列第二十一篇 高级整合应用第三篇SimpleMessageListenerContaine...

  • 最新web前端相关课程学习链接

    js基础篇 js进阶篇 js高级篇 vue基础篇 vue高级篇 react基础 react高级 Nodejs基础 ...

网友评论

    本文标题:高级应用篇六

    本文链接:https://www.haomeiwen.com/subject/ilyaqctx.html