MapReduce与函数式编程

分而治之

随着互联网的兴起,收集数据的速度越来越快,描述的事物也越来越复杂,所以产生了一些非常大的矩阵,大到计算机的内存无法装下这个矩阵,更别提计算.

为了解决这个问题google公司提出了MapReduce,相当于将非常多的计算机组合起来,形成了一台超级计算机.

解决复杂问题的方法是将问题模块化,而解决大矩阵的计算也是同样的道理,可以将大矩阵矩阵拆成小矩阵,然后把这些小矩阵分发给很多计算机,逐个计算小矩阵.

比如矩阵A与矩阵B相乘得到矩阵C

\begin{pmatrix}a_{11}&a_{12}&a_{13}&a_{14}\\ a_{21}&a_{22}&a_{23}&a_{24}\\ a_{31}&a_{32}&a_{33}&a_{34}\\ a_{41}&a_{42}&a_{43}&a_{44}\\ \end{pmatrix} \cdot \begin{pmatrix} b_{11}&b_{12}&b_{13}&b_{14}\\ b_{21}&b_{22}&b_{23}&b_{24}\\ b_{31}&b_{32}&b_{33}&b_{34}\\ b_{41}&b_{42}&b_{43}&b_{44}\\ \end{pmatrix} = \begin{pmatrix} c_{11}&c_{12}&c_{13}&c_{14}\\ c_{21}&c_{22}&c_{23}&c_{24}\\ c_{31}&c_{32}&c_{33}&c_{34}\\ c_{41}&c_{42}&c_{43}&c_{44}\\ \end{pmatrix}

我们可以将矩阵A拆分成A1和A2分别与矩阵B相乘,得到矩阵C1,C2

\begin{pmatrix}a_{11}&a_{12}&a_{13}&a_{14}\\ a_{21}&a_{22}&a_{23}&a_{24}\\ \end{pmatrix} \cdot \begin{pmatrix} b_{11}&b_{12}&b_{13}&b_{14}\\ b_{21}&b_{22}&b_{23}&b_{24}\\ b_{31}&b_{32}&b_{33}&b_{34}\\ b_{41}&b_{42}&b_{43}&b_{44}\\ \end{pmatrix} = \begin{pmatrix} c_{11}&c_{12}&c_{13}&c_{14}\\ c_{21}&c_{22}&c_{23}&c_{24}\\ \end{pmatrix}

\begin{pmatrix}a_{31}&a_{32}&a_{33}&a_{34}\\ a_{41}&a_{42}&a_{43}&a_{44}\\ \end{pmatrix} \cdot \begin{pmatrix} b_{11}&b_{12}&b_{13}&b_{14}\\ b_{21}&b_{22}&b_{23}&b_{24}\\ b_{31}&b_{32}&b_{33}&b_{34}\\ b_{41}&b_{42}&b_{43}&b_{44}\\ \end{pmatrix} = \begin{pmatrix} c_{31}&c_{32}&c_{33}&c_{34}\\ c_{41}&c_{42}&c_{43}&c_{44}\\ \end{pmatrix}

同样的道理,我们还可以将B矩阵拆分成B1,B2分别与矩阵A1,A2相乘得到矩阵C1,C2,C3,C4

\begin{pmatrix}a_{11}&a_{12}&a_{13}&a_{14}\\ a_{21}&a_{22}&a_{23}&a_{24}\\ \end{pmatrix} \cdot \begin{pmatrix} b_{11}&b_{12}\\ b_{21}&b_{22}\\ b_{31}&b_{32}\\ b_{41}&b_{42}\\ \end{pmatrix} = \begin{pmatrix} c_{11}&c_{12}\\ c_{21}&c_{22}\\ \end{pmatrix}

\begin{pmatrix}a_{31}&a_{32}&a_{33}&a_{34}\\ a_{41}&a_{42}&a_{43}&a_{44}\\ \end{pmatrix} \cdot \begin{pmatrix} b_{11}&b_{12}\\ b_{21}&b_{22}\\ b_{31}&b_{32}\\ b_{41}&b_{42}\\ \end{pmatrix} = \begin{pmatrix} c_{31}&c_{32}\\ c_{41}&c_{42}\\ \end{pmatrix}

\begin{pmatrix}a_{11}&a_{12}&a_{13}&a_{14}\\ a_{21}&a_{22}&a_{23}&a_{24}\\ \end{pmatrix} \cdot \begin{pmatrix} b_{13}&b_{14}\\ b_{23}&b_{24}\\ b_{33}&b_{34}\\ b_{43}&b_{44}\\ \end{pmatrix} = \begin{pmatrix} c_{13}&c_{14}\\ c_{23}&c_{24}\\ \end{pmatrix}

\begin{pmatrix}a_{31}&a_{32}&a_{33}&a_{34}\\ a_{41}&a_{42}&a_{43}&a_{44}\\ \end{pmatrix} \cdot \begin{pmatrix} b_{13}&b_{14}\\ b_{23}&b_{24}\\ b_{33}&b_{34}\\ b_{43}&b_{44}\\ \end{pmatrix} = \begin{pmatrix} c_{33}&c_{34}\\ c_{43}&c_{44}\\ \end{pmatrix}

至此,我们将复杂任务拆分成了多个简单任务.以上的矩阵拆分并且分别计算的过程被称为Map.将小矩阵C1,C2,C3,C4合并为最终结果C的过程被称为Reduce.

函数式编程

谈到函数式编程大家第一时间想到的可能就是lambda,因为lambda无副作用的特点是鲜明的函数式编程.

无副作用是指函数只产生返回值,没有其他的函数调用:

lambda x, y: x + y

:前面是参数列表,:后面是返回值.

除了lambda以外,map和reduce函数也属于函数式编程,其原理与我们所讲的MapReduce从原理上是相同的.

map函数通常用做分而治之:

map(lambda x: x ** 2, [1, 2, 3, 4, 5])

这个例子中需要计算列表中所有值的平方,map函数为每个值分别调用一个lambda,然后返回所有lambda结果的列表.

reduce函数通常用作合并:

reduce(lambda x, y: x+y, [1,2,3,4,5])

这个例子中需要计算列表中所有值的和,lambda接受两个参数,x是之前的累计和,y是本次需要累加的值.

posted @ 2018/06/11 10:03:18