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