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

2019-07-05

algorithm

定义

将原问题划分成n个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

每一次递归都会涉及三个操作

分解：将原问题分解成一系列子问题；
解决：递归地求解各个子问题，若子问题足够小，则直接求解；
合并：将子问题的结果合并成原问题；

使用分治算法的前提条件

原问题与分解成的小问题具有相同的模式；
原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别；
具有分解终止条件，也就是说，当问题足够小时，可以直接求解；
可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了。

分治算法实践

如何编程求出一组数据的有序对个数或者逆序对个数呢？解答：使用归并排序算法

public class MergeSort {

    private int num = 0;

    public int count(int[] a, int n) {

        num = 0;
        mergeSortCount(a, 0, n - 1);
        return num;
    }

    private void mergeSortCount(int[] a, int p, int r) {

        if (p >= r) {

            return;
        }

        int q = (p + r) / 2;
        mergeSortCount(a, p, q);
        mergeSortCount(a, q + 1, r);
        merge(a, p, q, r);
    }

    private void merge(int[] a, int low, int middle, int high) {

        int i = low;
        int j = middle + 1;
        int k = 0;
        int[] tmp = new int[high - low + 1];
        while (i <= middle && j <= high) {

            if (a[i] <= a[j]) {

                tmp[k++] = a[i++];
            }
            else {

                num += (middle - i + 1); //统计middle-low之间，比a[j]大的元素个数
                tmp[k++] = a[j++];
            }
        }

        while (i <= low) {

            tmp[k++] = a[i++];
        }

        while (j <= high) {

            tmp[k++] = a[j++];
        }

        for (i = 0; i <= high - low; ++i) {

            a[low + i] = tmp[i];
        }
    }
}

二位平面上有n个点，如何快速计算出两个距离最近的点对？解答：分成两块单独求其中一块点对最小距离，然后求这两块之间点对的最小距离，通过一些排序和删除，可以减少到6个点之间比较。
有两个nn的矩阵A，B，如何快速求解两个矩阵的乘积C=AB? 解答：v.斯特拉森提出了2*2分块矩阵的计算公式从原来的8次乘法缩减到了7次当n规模很大的时候缩减效果就很明显（7/8）^(logn)
给10GB的订单文件按照金额排序？解答：我们先扫描一遍订单，根据订单的金额，将10GB的文件划分为几个金额区间。
为什么说MapReduce的本质就是分治思想？解答：MapReduce框架只是一个任务调度器，底层依赖GFS来存储数据，依赖Borg管理处理器。它从GFS中拿数据，交给Borg中的机器执行，并且时刻监控机器执行的速度，一旦出现机器宕机、进度卡壳等，就重新从Borg中调度一台机器执行。

典型的应用场景

用来指导编码，降低问题求解的时间复杂度
解决海量数据处理问题

解释

Google文件系统（英语：Google File System，缩写为GFS或GoogleFS），一种专有分布式文件系统，由Google公司开发，运行于Linux平台上
BigTable是一种压缩的、高性能的、高可扩展性的，基于Google文件系统（Google File System，GFS）的数据存储系统，用于存储大规模结构化数据，适用于云端计算
MapReduce是Google提出的一个软件架构,用于大规模数据集（大于1TB的并行运算)。