April 19, 2019 · 数据结构与算法 本文字数: 1.4k 阅读时长:5 min 全站字数:361.8k

分治算法

  1. 分治算法
  2. 海量数据处理中的分治思想
  3. 分治算法典型框架-MapReduce
    1. 为什么现在硅谷一线公司都不在使用MapReduce了
      1. 系统复杂,维护困难
      2. 时间性能差
  4. 参考资料

分治算法

分治算法(Divide and Conquer)就是分而治之。将问题划分成n个较小规模的问题,每个子问题的结构和原问题相似,递归的解决这些子问题,最后合并这些子问题的结果来得到原问题的解。这里需要说明的是分治算法是一种处理问题的思想,而递归是一种编程技巧。分治算法的实现一般都是使用递归来实现,在每一层的递归进行三个操作:

  1. 分解问题。将原问题按照一定的规则分解成为独立的子问题。
  2. 解决子问题。递归求解各个子问题。
  3. 合并结果。将子问题的结果合并成原问题的结果。

能够用分治算法求解的问题需要满足以下几个条件:

  1. 原问题和分解后的子问题的模式相同。
  2. 子问题可以独立求解,子问题之间没有关联性。
  3. 当子问题规模足够小时,可以直接求解。
  4. 子问题的解合并为原问题的解的复杂度不能太高,否则算法整体复杂度过高。

分治算法最典型的应用就是排序算法中的归并排序。看一下归并排序的模板代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def divide_conquer(problem, p1, p2):
// 递归终止条件
if problem is None:
print_result
return

// 准备数据
data = prepare_data(problem)
sub_problems = split_problem(problem, data)

// 分治子问题
sub_result_0= divide_conquer(sub_problem[0], p1)
sub_result_1 = divide_conquer(sub_problem[1], p1)
// 处理分支结果,生成最终结果
result = process_result(sub_result_0, sub_result_1)

归并排序的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public static int[] mergeSort(int[] nums) {
if (nums == null) {
return new int[0];
}

// 子数组只剩一个元素了,直接返回该数组
if (nums.length == 1) {
return nums;
}

// 将数组分为两半
int mid = nums.length >> 1;
int[] left = Arrays.copyOfRange(nums, 0, mid);
int[] right = Arrays.copyOfRange(nums, mid, nums.length);

// 嵌套调用,处理两个子数组
left = mergeSort(left);
right = mergeSort(right);

// 合并两个已经排好序的数组
int[] merged = merge(left, right);

return merged;
}

private static int[] merge(int[] left, int[] right) {
if (left == null) {
left = new int[0];
}
if (right == null) {
right = new int[0];
}

int[] merged = new int[left.length + right.length];
int i = 0, j = 0, k = 0;

// 合并两个数组
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
merged[k] = left[i];
i++;
} else {
merged[k] = right[j];
j++;
}
k++;
}

// 直接拷贝剩余的数组
if (i < left.length) {
for (int m = i; m < left.length; m++) {
merged[k] = left[m];
k++;
}
}

if (j < right.length) {
for (int m = j; m < right.length; m++) {
merged[k] = right[m];
k++;
}
}
return merged;
}

海量数据处理中的分治思想

海量数据处理的典型问题就是:需要排序的数组很大(比如达到 1024GB 的时候),无法把这些数据都载入一台普通机器的内存里。此时该如何对这个数组排序?

利用分治算法,把这个超级大的数据集,分解为多个更小的数据集(比如 16GB 或者更小),然后分配到多台机器,让它们并行地处理。

在单台机器上实现归并排序的时候,我们只需要在递归函数内,实现数据分组以及合并就行了。而在多个机器之间分配数据的时候,递归函数内除了分组及合并,还要负责把数据分发到某台机器上。

分治算法典型框架-MapReduce

2003 年,Google发布论文《MapReduce: Simplified Data Processing on Large Clusters》,标志着MapReduce的诞生。杰夫(Jeff Dean)和桑杰(Sanjay Ghemawat)从纷繁复杂的业务逻辑中,为我们抽象出了 Map 和 Reduce 这样足够通用的编程模型。

Google的MapReduce框架其实是一个任务调度器,它底层依赖GFS来存储任务数据,依赖Borg管理的机器来处理任务。

为什么现在硅谷一线公司都不在使用MapReduce了

系统复杂,维护困难

使用MapReduce,必须严格遵循分步Map和Reduce的步骤。如果构建复杂的处理架构时,需要协调多个Map和多个Reduce任务,而每一步的MapReduce都可能出错,为了处理这些异常,有人设计自己的协调系统,如一个状态机,这增加了整个系统的复杂度。

例如一个收集数据进行识别的项目,就需要划分成不同的MapReduce任务,如:先进行数据收集,这其中包括数据导入,数据统一化,数据压缩,数据备份等步骤;数据收集完成还需要进行质量控制,如校验数据的时间的有效性,照片对焦较正等;最后才是从图片中识别,包括标注数据,标注结果下载,标注异议整合,标注结果结构化。

在上面的整个过程中,每一步都可能出错,需要重试和异常处理逻辑,需要一个和业务紧密耦合的状态机。如此复杂的系统,维护起来的难度可想而知。

时间性能差

编写优秀的MapReduce程序需要很高的学习门槛。 Google 500 多页的 MapReduce 性能优化手册足够说明其复杂度了。如分片策略,缓冲大小,分片多少,预抓取策略,缓存大小等。

参考资料

  1. 为什么MapReduce会被硅谷一线公司淘汰
  2. 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
  3. 递归(下):分而治之,从归并排序到MapReduce