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

精选留言(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