数据结构与算法之美
王争
前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 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想

王争 2018-12-19
MapReduce 是 Google 大数据处理的三驾马车之一,另外两个是 GFS 和 Bigtable。它在倒排索引、PageRank 计算、网页分析等搜索引擎相关的技术中都有大量的应用。
尽管开发一个 MapReduce 看起来很高深,感觉跟我们遥不可及。实际上,万变不离其宗,它的本质就是我们今天要学的这种算法思想,分治算法。

如何理解分治算法?

为什么说 MapRedue 的本质就是分治算法呢?我们先来看,什么是分治算法?
分治算法(divide and conquer)的核心思想其实就是四个字,分而治之 ,也就是将原问题划分成 n 个规模较小,并且结构与原问题相似的子问题,递归地解决这些子问题,然后再合并其结果,就得到原问题的解。
这个定义看起来有点类似递归的定义。关于分治和递归的区别,我们在排序(下)的时候讲过,分治算法是一种处理问题的思想,递归是一种编程技巧。实际上,分治算法一般都比较适合用递归来实现。分治算法的递归实现中,每一层递归都会涉及这样三个操作:
分解:将原问题分解成一系列子问题;
解决:递归地求解各个子问题,若子问题足够小,则直接求解;
合并:将子问题的结果合并成原问题。
分治算法能解决的问题,一般需要满足下面这几个条件:
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(71)

  • Williamzhang 置顶
    第一个留言有问题可以再理解一下,不要误导后边人,作者的num+=语句位置正确

    作者回复: 哈哈 终于有人看懂了 我的跟留言那位同学的思路不一样而已 他的更简洁些

    2018-12-20
    13
  • 三木子
    在统计方面比较多,比如统计我国人口,要知道我国人口就要先知道每个省人口,要知道省人口就要知道每个市人口,要知道市人口就要知道每个区县人口,直到村社区,然后汇总求的总人数。

    作者回复: 👍

    2018-12-19
    31
  • MIAN-勉
    把归并排序merge方法的参数列表 由merge(int[] a, int p, int q, int r) 改为 merge(int[] a, int low, int middle, int high) 更容易理解😂,小细节,哈哈
    2018-12-27
    30
  • Jiemr
    老师,我有两个疑问:
    给 10GB 的订单排序,我们就可以先扫描一遍订单
    -------------------------------------
    1.场景中描述的机器内存只有2、3GB,我理解的是直接加载文件内存应该不够用来扫描一次10GB订单文件,对吗?如果不能,那应该怎么扫描呢?
    2.如果用buffer来缓存扫描结果的话,即使能扫描完成,又该怎么对文件根据金额区间进行分割呢?
    2019-01-11
    3
    19
  • 刘远通
    第一个求最近的点对
    分成两块 单独求其中一块点对最小距离
    然后求这两块之间点对的最小距离 通过一些排序和删除 可以减少到6个点之间比较 很神奇

    第二个矩阵计算
    v.斯特拉森提出了2*2分块矩阵的计算公式 从原来的8次乘法 缩减到了7次
    当n规模很大的时候 缩减效果就很明显 (7/8)^(logn)
    2018-12-20
    16
  • Yves
    代码略有问题:1,num += (q - i + 1),应该是在 a[i] <= a[j] 这个条件分支里面;2,while (i <= q) 里面不应该有 num += (q - i + 1),3,最后的修改原数组迭代条件应该是 i < r - p + 1 而不是 i < r - p 。

    private void merge(int[] a, int p, int q, int r) {
            int i = p, j = q + 1, k = 0;
            int[] tmp = new int[r - p + 1];
            while (i <= q && j <= r) {
                if (a[i] <= a[j]) {
                    tmp[k++] = a[i++];
                } else {
                    num += (q - i + 1);
                    tmp[k++] = a[j++];
                }
            }
            while (i <= q) {
                tmp[k++] = a[i++];
            }
            while (j <= r) {
                tmp[k++] = a[j++];
            }
            for (i = 0; i < r - p + 1; ++i) {
                a[p + i] = tmp[i];
            }
        }

    作者回复: 是的 大家代码直接看这位同学的 我晚点改正下。写的时候匆忙 不好意思

    2018-12-19
    14
  • Smallfly
    「创新并非离我们很远,创新的源泉来自对事物本质的认识。无数优秀架构设计的思想来源都是基础的数据结构和算法,这本身就是算法的一个魅力所在。」

    这句话讲的太好啦。各种前端框架层出不穷,本质的东西,也是基本都没有变。

    与其最新,不如求本。
    2018-12-19
    8
  • h…
    王争老师,我是后台开发,想换算法类工作,能不能给我点建议

    作者回复: 算法现在很火啊 供不应求 如果年轻的话 并且愿意学习的话 转起来也不难 建议找几本书看看 多代码练习一下 入了门之后 先找个一般的公司干干 积累些项目经验 以此再去好点公司

    2018-12-20
    1
    5
  • 刘文坛
    分治算法本质上就是利用多核cpu并行计算能力,如果只是单核cpu,分治算法是不是就不可行了?

    作者回复: 不。单核也可以利用多线程并行。毕竟一般的算法代码都包括:内存访问、CPU计算两部分,并不只是CPU计算。

    2019-02-02
    1
    4
  • ALAN
    老师,你好,有一个建议,就是对于代码每一行里不是很显然易懂的地方,能否注释下此行代码的作用,不然有时看了代码也不知为啥这样写。
    2018-12-19
    1
    4
  • 不上进的码农
    if (a[i] <= a[j]) {
          num += (j - q - 1);
          tmp[k++] = a[i++];
        } else {
          tmp[k++] = a[j++];
        }
    我想了想,这段代码应该求的是有序对而不是逆序对吧

    作者回复: 逆序对

    2018-12-19
    3
  • CathyLin
    本来已经刷完了,但感觉没想明白怎样合并平面中两个距离最近的点对于是又网上查资料嗑了 2 个晚上。
    发现通过数学公式的计算,对于左区间中的一个点,我们最多只需要比较右区间中 7 个点就可以了,所以也是相当于是 linear time。
    然后通过 T(n) = 2*T(n/2) + O(n) 得到最后的时间复杂度是 O(NlogN)。
    Ref: https://en.wikipedia.org/wiki/Closest_pair_of_points_problem

    课后思考:深刻的理解到了递归就是实现分治的最好方法,例如我们在构建树的问题时,首先构建左子树,然后再构建右子树,最后把两个子树合并起来形成当前节点。
    生活中:就像评论区所留言的那样,美国大选,先从镇开始,然后到州,最后在合并起来。

    2019-08-06
    2
  • 康斯坦丁
    前面的数据结构与算法中: 归并排序、桶排序、快速排序使用了分治算法.
    工作/生活中: 美国大选统计选票.
    2019-07-02
    2
  • 寻路人
    团队目标达成也是采用分治思想。
    leader:设置一个团队的整体目标。
    module owner: 分取整体目标的一个模块。
    developer: 分取模块里面一个任务。
    整体目标 = 模块任务A + 模块任务B
    模块任务A = 个人任务A + 个人任务B + 个人任务C
    最后达到整个任务
    2019-06-10
    2
  • www.xnsms.com小鸟接码
    归并排序忘记了,又跑头前面看一下,不然看不懂了……忘的好快……
    2019-01-06
    2
  • Sharry
    使用归并排序求逆序度, 实在是太妙了! 老师的代码一点儿问题都没有, (j-q-1) 记录的是比子序列 A 中当前即将添加到 tmp 数组中的元素的逆序对的个数, 看到留言里小伙伴说应该放在下面的 else 里, 可能需要再斟酌斟酌
    2018-12-20
    2
  • 辣么大
    二维平面的最近点对比较难理解。我们先从一维的入手吧。也是使用分治思想来求解。
    代码实现如下:
    public static void find(int[] a) {
        int mindist = mindist(a, 0, a.length - 1);
        System.out.println(mindist);
      }

      public static int mindist(int[] a, int lo, int hi) {
        if (lo >= hi) {
          return Integer.MAX_VALUE;
        } else if (lo == hi - 1) {
          return a[hi] - a[lo];
        } else {
          int m = lo + (hi - lo) / 2;
          int delta_1 = mindist(a, lo, m); // left points set
          int delta_2 = mindist(a, m + 1, hi); // right points set
          int delta_3 = a[m + 1] - a[m]; // strip points min distance
          return _Math.min(delta_1, delta_2, delta_3);
        }
      }

      public static void main(String[] args) {
        int[] a = {1, 3, 4, 10, 20, 100};
        find(a);//1
      }
    2019-11-07
    1
  • Jeff.Smile
    老师,请问我做java但是不从事算法岗位,这门课需要学习到什么程度呢?总觉得心里有目标会更好点。

    作者回复: 把比较基础的算法看懂就可以了,我后面有一篇文章分享关于新手如何循序渐进学习的,你可以看下。

    2019-08-13
    1
  • 未来的胡先森
    公司的管理也是分治吧,先把大的任务分到各大部门,部门再划分任务到团队,团队划分到个人(达到能够独立求解),个人完成任务,到团体完成任务,到大任务完成即合并。
    2019-08-02
    1
  • Geek_54edc1
    用快排也可以算逆序度,只要记录数据交换的次数就可以了
    2019-05-23
    1
收起评论
71
返回
顶部