article20201025

Posted on Edited on

大数据 | 大数据基础--算法之并行计算算法：基本问题（一）

亲爱的读者朋友大家晚上好，从今天开始我们来介绍并行算法。

简介

并行算法一般基于一定的框架进行计算，常用的计算框架主要有PRAM模型，BSP（Bulk Synch Parallel）模型，MapReduce模型。我们主要分析MR模型，这里将的是理论的分析模型，具体的实现计算平台，比如hadoop等在后面会进行分析。

MapReduce

使用MR模型进行计算有几个要点：

  • 计算分轮次进行，每一轮的输入和输出的数据都是形如\(<key,value>\)的
  • 每一轮分为：Map、Shuffle、Reduce
  • Map：每个数据被map函数处理，输出一个新的数据集合，也就是改变了\(<key,value>\)
  • Shuffle：对编程人员透明，所有在Map中输出的数据，被按照key分组，具备相同key 的数据被分配到相同的reducer
  • Reduce：输入\(<k,v_1,v_2,...>\)，输出新的数据集合
  • 针对这样的计算框架，我们的设计目标为：更少的轮数、更少的内存、更大的并行度

问题实例

下面我们来看一些具体的问题实例，这些例子都是可以并行的，当然实现的逻辑不止一种，有多种可能性，这里只是给出一种方法。

构建倒排索引

定义：给定一组文档，统计每一个单词出现在哪些文件中

  • Map函数：\(<docID,content> \rightarrow <word,docID>\)，在map函数处理的时候对content进行拆分，并将分出来的word都转换成word加上对应的docID输出。
  • Reduce函数：\(<word,docID> \rightarrow <word,list\ of\ docID>\)，map函数结束之后，shuffle会自动将key相同的键值对输出到一个机器上，我们直接对这个批次中的数据规整到一起即可。

单词计数

定义： 给定一组文档，统计每一个单词出现的次数

  • Map函数：\(<docID,content> \rightarrow <word,1>\)
  • Reduce函数：\(<word,1>\rightarrow <word,count>\)

检索

定义：给定行号和相应的文档内容，统计指定单词出现的位置（*行号）

  • Map函数：略
  • Reduce函数：略

总结

以上就是并行计算的简单介绍，下次我们会继续应用这个计算框架解决一些更具挑战性的问题，敬请期待。