article20201108

大数据 | 大数据基础--算法之并行计算算法：排序算法

亲爱的读者朋友大家晚上好，上次我们简单介绍了并行算法以及有关矩阵乘法的几个基本问题，这次我们来分析基于MapReduce的排序算法。

简介

上次提到我们主要分析用Map Reduce框架来设计问题的并行计算方法，先简单回顾一下框架的内容。

MapReduce

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

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

问题简介

排序是算法设计分析中非常关键的部分，基本上很多问题的求解都离不开数据的排序，传统的排序算法有很多，比如：冒泡排序、选择排序、归并排序等，其中基于比较的排序算法的时间复杂度为\(O(n\ logn)\)，如果有足够的存储空间，使用桶排序，将获得\(O(n)\)的效率。但是在大数据场景下，这些传统的算法都显得难以满足需求。为此，我们需要借助一定的并行手段，甚至有的时候还需要牺牲一定的算法精度来完成一个具体的任务。

下面，我们就来简单看一下一个基于MapReduce实现的并行排序算法。值得注意的是这部分的知识不涉及非常难懂的理论，只需要把算法的过程搞清楚就可以大概掌握算法的核心思想。因此对这个算法我们只做过程的讲解，不进行理论的证明。

算法

使用\(p\)台处理器，输入\(<i,A[i]>\)

• Map：\(<i,A[i]> \rightarrow <j,(A[i],y)>\)
  • 转化\(<i\%p,((i,A[i]),0)>\)
  • 针对上述转化数据，对所有\(j \in [0,p-1]\)，以概率\(T/n,T=log(p)/\epsilon^2\)，输出\(<j,((i,A[i]),1)>\)，否则输出\(<j,((i,A[i]),0)>\)
• Reduce：
  • 将\(y=1\)的数据收集为\(S\)并排序
  • 将\(y=0\)的数据收集为\(B\)
  • 构造\((s_1,s_2,...,s_{p-1})\)，\(s_j\)为\(S\)中第\(j\left \lceil \frac{|S|}{p} \right \rceil\)，对\((i,x)\in B\)满足\(s_j < x \leq s_{j+1}\)，输出\(<j,(i,x)>\)
• Map：nothing（identity）
• Reduce：将所有\((i,x)\)根据\(x\)排序并输出

思路剖析：整体的思路就是先对整个数据进行一个划分，分成不同的小段，段与段之间的数据具有严格的大小关系，这样每个段内部的数据都是一些很接近的数据，如此我们就可以借助一些高效的排序手段对每个段内部的数据集进行排序。然后解决问题的一个关键就是，我们对数据的划分的好坏，这一点我们可以通过理论来证明有很大概率可以保证划分的效果。但是也不绝对，出现某个计算节点上基本没有数据，而另一个计算节点上出现超量的数据也是有可能的，当然这是极小概率事件。

总结

以上就是利用并行计算解决排序问题的一个简要算法，下次我们会继续应用这个计算框架解决最小支撑树问题，敬请期待。