使用MapReduce实现矩阵相乘算法

看到一篇文章，列出了几个使用MapReduce完成的算法（附有实现案例），但是还是想自己实现下，所以自己写了一个，后来看了下案例，不是太一样，但是我实现了，不管效果如何，或者好不好看，总之我实现了。这里就跟大家分享下，同时也希望能得到一个建议。

首先介绍下我的实现思想：

1.两个矩阵相乘，我们假设为a[i][j]，b[x][y]，若a*b则i==y，即c[n][n]=a[i][j]*b[x][y]（n==i==y），图方便直接使用对称矩阵。

2.使用Matrix对象来封装一个矩阵的节点，Matrix对象有三个变量：flag,script1,script2。flag用来标示该矩阵节点属于左边的矩阵(a)还是右边的矩阵(b)，又或是结果矩阵(c)，因为左右矩阵需要不同的方式进行处理，所以需要区分开。

3.我们知道c[i][j]=sum(a[i][x]*b[x][j])(x=1-->n)，根据此公式，我们可以知道一个c节点的值由a,b的哪些节点决定，我们这些a,b节点同c[i][j]放到一起，作为map的输出，reduce的输入。然后通过使用合适的分组比较器和排序比较器，我们可以让所有决定c[i][j]值的a和b节点放到一个reduce方法中，这样我们就可以方便的计算出c[i][j]的值了。

4.分组比较器：map的输出是[c[i][j],a[i][x]/b[x][j]}，a[i][x]/b[x][j]的值]，这样的方式，而我们需要所有包含c[i][j]的key放到一起，所以分组比较器只要针对key的第一个对象进行比较即可，在对key的第一个对象(c)进行比较时，先flag进行比较（这里不出意外应该都是一样的），再根据script1进行比较，最后根据script2进行比较，这样得到的可能排序结果如下：

c[1][1],c[1][2],c[2][1],c[2][2],...正是我们需要的顺序，我们可以按此顺序将值一次写入输出文件中，配置合理的换行机制，就可以得到一个很清晰的矩阵结果。

5.排序比较器：上面的分组比较器可以使得计算一个c[i][j]所需要的所有a和b矩阵节点都在一个reduce方法中进行计算，这样虽然可以满足我们的需求，但是计算相对来说还是比较麻烦的。比如我们需要计算c[2][3]（假设矩阵大小=10），那么我们需要计算a[2][1]*b[1][3]+a[2][2]*b[2][3]+...+a[2][10]*b[10][3]，而reduce方法提供给我们的只是一个Iterable迭代器，我们需要在这个迭代器中找到a[2][1]，b[1][3]然后再相乘，但是迭代器只能迭代一次，固然我们可以将其保存到一个list中，但是还是需要对该list进行N次遍历，效率低下。这时就需要排序比较器出场了，从前面的计算公式我们可以看出，a的列标和b的行标其实是相同的，同时所有的a的行标是一致的，所有b的列标是一致的，因此我们在对其进行排序时完全可以按照a的列标和b的行标进行排序，这样得到的排序结果如下：a[2][1]，b[1][3]，a[2][2]，b[2][3]，...这样我们可以直接将相邻两个值相乘然后求和即可获得最终的c[2][3]的值。这里不要误会，reduce是先排序，然后再对排序结果进行遍历时才调用分组比较器判断组的，这里先介绍分组后介绍排序只是因为方便讲解。所以在排序时实际上我们实现按照key的第一个矩阵对象，即c矩阵进行排序，然后再根据第二个对象进行排序。

5.在计算出c[i][j]的值之后我们需要将其写入到输出文件中，同时我们想要保持良好的显示风格，保持矩阵的顺序，因为在排序时已经保证了矩阵的顺序，所以我们只需顺序写入输出文件即可，但是我们需要合理的换行。实现方法是自定义RecordWriter对象，然后在每次调用RecordWriter的write方法时将参数key保存到一个变量中(last)，然后每次调用该方法时将last的行标同key的行标进行比较，如果相同则不换行，不相同则换行。

以上就是我的整个实现思想，如有不妥之处还望赐教，顺便附上自己的代码，在运行时可以先调用util里的FileUtil写两个矩阵文件，这里需说明下因为在计算过程中需要根据文件名区分a和b矩阵，所以a矩阵的文件名需要包含”1“，而b矩阵的文件名不能包含1，则文件中每行的第一个值是行号，且从1开始。也可以直接使用files里面的文件。

<<请将文件上传到hdfs中>>

该方法支持文件切分，但是最好使用一个reduce，因为多个reduce会将结果输出到多个文件，不易查看。

推荐阅读：