数据结构与算法之美
王争
前 Google 工程师
283752 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 81 讲
基础篇 (38讲)
数据结构与算法之美
15
15
1.0x
00:00/00:00
登录|注册

51 | 并行算法:如何利用并行处理提高算法的执行效率?

并行计算在超大规模数据处理中的应用
并行计算的实现思路
动态散列表的并行处理
快速排序并行化处理
归并排序并行化处理
课后思考
总结引申
并行搜索
并行字符串匹配
并行查找
并行排序
并行处理提高算法执行效率

该思维导图由 AI 生成,仅供参考

时间复杂度是衡量算法执行效率的一种标准。但是,时间复杂度并不能跟性能划等号。在真实的软件开发中,即便在不降低时间复杂度的情况下,也可以通过一些优化手段,提升代码的执行效率。毕竟,对于实际的软件开发来说,即便是像 10%、20% 这样微小的性能提升,也是非常可观的。
算法的目的就是为了提高代码执行的效率。那当算法无法再继续优化的情况下,我们该如何来进一步提高执行效率呢?我们今天就讲一种非常简单但又非常好用的优化方法,那就是并行计算。今天,我就通过几个例子,给你展示一下,如何借助并行计算的处理思想对算法进行改造?

并行排序

假设我们要给大小为 8GB 的数据进行排序,并且,我们机器的内存可以一次性容纳这么多数据。对于排序来说,最常用的就是时间复杂度为 O(nlogn) 的三种排序算法,归并排序、快速排序、堆排序。从理论上讲,这个排序问题,已经很难再从算法层面优化了。而利用并行的处理思想,我们可以很轻松地将这个给 8GB 数据排序问题的执行效率提高很多倍。具体的实现思路有下面两种。
第一种是对归并排序并行化处理。我们可以将这 8GB 的数据划分成 16 个小的数据集合,每个集合包含 500MB 的数据。我们用 16 个线程,并行地对这 16 个 500MB 的数据集合进行排序。这 16 个小集合分别排序完成之后,我们再将这 16 个有序集合合并。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

通过并行处理提高算法执行效率 本文介绍了如何利用并行处理来提高算法的执行效率。文章指出时间复杂度并不能完全等同于性能,然后通过并行排序、并行查找、并行字符串匹配和并行搜索等多个例子,展示了如何利用并行计算的处理思想对算法进行改造。作者指出,并行计算是一种工程上的实现思路,尽管跟算法关系不大,但在实际的软件开发中,它可以非常巧妙地提高程序的运行效率,是一种非常好用的性能优化手段。特别是在处理超大规模数据时,无法通过继续优化算法来提高执行效率时,利用更多的硬件资源进行并行处理是非常重要的。文章总结了并行处理的实现思路,即对数据进行分片,对没有依赖关系的任务并行地执行。并指出在很多超大规模数据处理中,并行处理的思想应用非常广泛,比如MapReduce实际上就是一种并行计算框架。通过本文的总结,读者可以快速了解并行处理对算法执行效率的提升,以及在实际软件开发中的应用价值。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《数据结构与算法之美》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(53)

  • 最新
  • 精选
  • Geek_46cdcd
    请问老师,广度优先搜索中用两个队列是为了解决多线程的并发问题吗?

    作者回复: 是的

    2019-05-09
    3
    10
  • Smallfly
    并行搜索只用一个队列不可以么?

    作者回复: 也可以的。不过就有可能导致没法找到最短路径了。

    2019-01-23
    8
  • 纯洁的憎恶
    并行与分治的区别是什么?前者偏工程,后者偏算法么?还是前者在并发环境中,后者在单核串行环境中?

    作者回复: 并行是一种工程思路。分治是一种算法思想。感觉差不多哈;)你理解就好,不要太纠结;)

    2019-01-23
    8
  • 走马
    是不是就类似于spark中rdd 的宽窄依赖了

    作者回复: 😄 不懂spark

    2019-09-17
  • 朱东旭
    老师,并行搜索在你的描述中是先操作队列A,再操作队列B,这是有先后顺序,这意味着是串行的不是并行呀。

    作者回复: 是并行处理完队列a,然后并行处理队列b这个样子的。并不是a、b的处理是并行的。

    2019-05-10
  • 少盐
    计算机不一定都是n核的,怎么实现性能提升n倍呢

    作者回复: 即便是n核也不一定提高n倍,毕竟还共享内存呢:) 我这里本就是粗略的表示:)

    2019-01-23
  • 失火的夏天
    思考题用一个有向图来存储任务之间的依赖关系,然后用拓扑排序的思想来执行任务,每次都找到入度为0的,放在队列里,启动线程池开始执行,队列里的任务并行执行完毕,再次调用拓扑排序找到入度为0的人,放入队列,直到所以任务跑完
    2019-01-23
    7
    221
  • Jerry银银
    一看到依赖,就想到了拓扑。 这种感觉好是还是不好呢?
    2019-01-23
    3
    52
  • DFighting
    现在才明白,其实最底层的数据结构是<addr,value>,按照存储介质是否连续、是否显示制定key又可以分为数组、链表和hash,其中数组可以认为是一种<index,arr[index]>,链表是<p,*p>,然后在这基础之上衍生出了一维的线性表、栈、队列,散列表,二维的树(平衡二叉树、红黑树、跳表),三维的图,还有就是各种数据结构灵活组合的数据结构,这里的跳表可以算是组合类型的,但是它的使用范围很多,所以划到了二维中。这些是存储 然后是算法:排序、分治、贪心、回溯、动态规划 第一次真正感觉到了数据结构和算法的关联,好神奇的感觉。至少现在觉得那些难记的算法、数据结构没那么困难了,多思考、实践总会能够像写代码般应用到实际中。
    2019-08-13
    2
    48
  • hua168
    老师,我就问一个题外问题: 大专学历,想直接自学考本科或研究生,自考学历IT类公司承认的吗? 很多都要求全日制本科~~
    2019-01-23
    9
    16
收起评论
显示
设置
留言
53
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部