数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

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

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

并行排序

假设我们要给大小为 8GB 的数据进行排序,并且,我们机器的内存可以一次性容纳这么多数据。对于排序来说,最常用的就是时间复杂度为 O(nlogn) 的三种排序算法,归并排序、快速排序、堆排序。从理论上讲,这个排序问题,已经很难再从算法层面优化了。而利用并行的处理思想,我们可以很轻松地将这个给 8GB 数据排序问题的执行效率提高很多倍。具体的实现思路有下面两种。
第一种是对归并排序并行化处理。我们可以将这 8GB 的数据划分成 16 个小的数据集合,每个集合包含 500MB 的数据。我们用 16 个线程,并行地对这 16 个 500MB 的数据集合进行排序。这 16 个小集合分别排序完成之后,我们再将这 16 个有序集合合并。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(30)

  • 失火的夏天
    思考题用一个有向图来存储任务之间的依赖关系,然后用拓扑排序的思想来执行任务,每次都找到入度为0的,放在队列里,启动线程池开始执行,队列里的任务并行执行完毕,再次调用拓扑排序找到入度为0的人,放入队列,直到所以任务跑完
    2019-01-23
    2
    73
  • Jerry银银
    一看到依赖,就想到了拓扑。

    这种感觉好是还是不好呢?
    2019-01-23
    15
  • hua168
    老师,我就问一个题外问题:
    大专学历,想直接自学考本科或研究生,自考学历IT类公司承认的吗?
    很多都要求全日制本科~~
    2019-01-23
    1
    11
  • DFighting
    现在才明白,其实最底层的数据结构是<addr,value>,按照存储介质是否连续、是否显示制定key又可以分为数组、链表和hash,其中数组可以认为是一种<index,arr[index]>,链表是<p,*p>,然后在这基础之上衍生出了一维的线性表、栈、队列,散列表,二维的树(平衡二叉树、红黑树、跳表),三维的图,还有就是各种数据结构灵活组合的数据结构,这里的跳表可以算是组合类型的,但是它的使用范围很多,所以划到了二维中。这些是存储
    然后是算法:排序、分治、贪心、回溯、动态规划
    第一次真正感觉到了数据结构和算法的关联,好神奇的感觉。至少现在觉得那些难记的算法、数据结构没那么困难了,多思考、实践总会能够像写代码般应用到实际中。
    2019-08-13
    9
  • 🐱您的好友William🐱
    使用拓扑关系来构建图安排计算顺序,这个spark,tensorflow都是这么安排的,效率比最开始的MapReduce还要高很多。
    2019-02-08
    4
  • 茴香根
    思考题讲的够直白了,n个任务有互相依赖。那么并行处理的方法就要采用流水线的思想了。创建n个线程,每个线程完成一个任务。每个线程在它的上游线程结束输出结果后启动,完成之后把结果传递给下游任务线程继续流程。整个工作场景像工厂里面的流水线一样,每一个线程都努力地重复着某一阶段的任务,提高整体资源利用率。
    2019-01-23
    4
  • Smallfly
    并行搜索只用一个队列不可以么?

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

    2019-01-23
    2
  • 刺猬
    王铮老师,你好,学习了这么久一直有一个疑问,之前讲的那个100G订单排序的问题,一大份数据分成多份小数据然后进行排序,原理其实很简单,但是分的时候可以用到什么算法,分完组合的时候用到什么算法,因为100G订单不是之前就分好的,要一次性分,那也需要扫描这100G订单,另外如果分的时候不是采用先对数据按照大小划分区间,然后再排序的话,那么在每一段内是有序的,但是不能保证组合以后也有序,所以组合的时候还有进行排序,这种情况有什么好的解决思路。
    2019-11-24
    1
    1
  • mrlay
    我觉得能够并行执行多少个任务,是取决于这些任务之间的依赖关系;采用拓扑只是为了确认任务的先后执行。 最坏的情况下还是会变成串行的。
    2019-07-21
    1
  • Geek_46cdcd
    请问老师,广度优先搜索中用两个队列是为了解决多线程的并发问题吗?

    作者回复: 是的

    2019-05-09
    1
    1
  • xuery
    想到的第一个思路就是前面所讲的拓扑排序,任务之间的关系用有向图表示,如果是采用khan遍历,则每次找到入度为0的,同时多线程执行,等他们执行完(java可以通过CountDownLatch来模拟实现),然后同理找到入度为0的任务,继续同理执行,直到全部执行完
    2019-04-09
    1
  • 牧民牛仔
    既然有依赖关系,我条件反射想到拓扑排序算法,根据依赖关系把任务分组,各组任务按照依赖关系排序。没有依赖关系的任务组可以并行执行,有依赖关系的任务组内则按依赖关系有序的执行。
    2019-01-24
    1
  • 子嘉
    思考题是:拓扑排序么。。
    2019-01-23
    1
  • 纯洁的憎恶
    并行与分治的区别是什么?前者偏工程,后者偏算法么?还是前者在并发环境中,后者在单核串行环境中?

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

    2019-01-23
    1
  • feifei
    我想到了图,讲依赖关系抽象成边,使用图排序就可以找出依赖关系,然后将每一层的任务放入线程池执行,当一层完成后,继续下一层处理
    2019-01-23
    1
  • Sid
    并行搜索,广度优先遍历,A中每个顶点的处理是并行的,但为了保证扩展出的节点之间的顺序与A队列节点之间的顺序一致,扩展出的顶点“放入”到B队列这个步骤还是要串行的吧。
    2019-11-18
  • CarreyWang
    广度优先搜索里面

    假设这两个队列分别是队列 A 和队列 B。多线程并行处理队列...

    这样先清空A,再清空B的做法,与原来只使用一个队列的方式没有太大的效率提升吧?无法做到在拓展A的时候同时拓展B啊????
    2019-10-25
  • Magic
    拓扑排序
    2019-09-22
  • 李冲
    虽然思考题与前面的编译依赖相似,但在本课程的语境下也许不仅仅只是找出哪些任务可以并行。如果任务是耗时的(相对普通指令周期而言),那思路可能不一样。

    就拿高赞留言来讲,当某一代(就是指入度为0的判定后的任务集合)的任务数量比较少或者耗时离散度高的时候,线程池利用率就可能低了。因为下一代任务的启动必须等待这一代任务全部结束。如有理解题目有误,还请指正。
    2019-09-18
  • 走马
    是不是就类似于spark中rdd 的宽窄依赖了

    作者回复: 😄 不懂spark

    2019-09-17
收起评论
30
返回
顶部