当前位置：首页 > news >正文

递归到分治

news 2024/11/1 16:57:15

一、递归与分治：

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);}
}