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会将结果输出到多个文件,不易查看。

相关推荐