一、递归与分治:
1、递归:如果一个问题分可以简化为某些更小的、更简单的子问题来解决,那么可以用递归
2、分治:如果想并行处理,可以用到分治
二、假设我们有一段文本,需要统计每个单词出现的频率。我们将步骤分为以下几部分:
1、分割:
将文本分割为多个小块,每个块会在不同的“Mapper”上处理。
2、映射:
每个 Mapper 会对文本块进行单词计数,输出键值对形式的结果,如 (“word”, 1)。
3、洗牌:
将相同的键(单词)汇总到一起,确保相同的单词会发往同一个 Reducer。
4、归约:
在 Reducer 上,对相同的单词进行累加求和,得到最终的词频统计。
5、合并:
可选择在 Mapper 阶段进行本地归约,以减少传输数据量。
import java.util.*;
import java.util.stream.Collectors;
public class MapReduceExample {
// 模拟文本数据
static String text = "hello world hello map reduce map reduce example example example";
public static void main(String[] args) {
// 1. 分割 - 将文本按空格分割为单词块(每个单词可以认为是一个“分片”)
List<String> words = Arrays.asList(text.split(" "));
// 2. 映射 - 每个分片对应一个键值对 (word, 1)
List<Map<String, Integer>> mappedData = words.stream()
.map(word -> {
Map<String, Integer> map = new HashMap<>();
map.put(word, 1);
return map;
}).collect(Collectors.toList());
// 打印映射后的键值对
System.out.println("Mapped Data: " + mappedData);
// 3. 洗牌 - 将相同的键(单词)聚合到一起
Map<String, List<Integer>> shuffledData = new HashMap<>();
for (Map<String, Integer> entry : mappedData) {
for (Map.Entry<String, Integer> e : entry.entrySet()) {
shuffledData.computeIfAbsent(e.getKey(), k -> new ArrayList<>()).add(e.getValue());
}
}
// 打印洗牌结果
System.out.println("Shuffled Data: " + shuffledData);
// 4. 归约 - 对相同的键(单词)累加值
Map<String, Integer> reducedData = shuffledData.entrySet().stream()
.collect(Collectors.toMap(
Map.Entry::getKey,
e -> e.getValue().stream().reduce(0, Integer::sum)
));
// 打印最终归约结果(词频统计结果)
System.out.println("Reduced Data (Word Frequency): " + reducedData);
}
}