MapReduce编程——矩阵乘法（Python版本）

数据格式

• 对于矩阵元素$A_{ij}$，将其处理为$<i,j,MatrixName,value>$的四元组格式，例如矩阵[[2, 1, 3, 4], [10, -8, 7, 2], [9, 1, 6, -2]]可被转化为如下形式

  1 1 A 2
  1 2 A 1
  1 3 A 3
  1 4 A 4
  2 1 A 10
  2 2 A -8
  2 3 A 7
  2 4 A 2
  3 1 A 9
  3 2 A 1
  3 3 A 6
  3 4 A -2
  

程序说明

• 假设有矩阵$A_{m\times q}$与$B_{q\times n}$相乘，且矩阵$A$与$B$都被转化为了以上格式存储在一个txt文件中

Map函数

• Map函数接收一个四元组$<i,j,MatrixName,value>$作为输入，对于$A_{ij}$返回键值对$<<i,k>,<A,j,value>>(k=1,2,3,...,n)$；对于$B_{ij}$返回键值对$<<k,j>,<B,i,value>>(k=1,2,3,...,m)$

Reduce函数

• Reduce函数接收shuffle后得到的键值对$<<i,k>,<<来自A的第i行>,<来自B的第k列>>>$，此时只需使得A与B中对应的元素相乘再相加即可得到结果$C_{ij}$

代码

# 文件命名为matmul.py,矩阵数据写在matrix.txt文件中
from mrjob.job import MRJob
import numpy as np# M为矩阵A的行数，N为矩阵B的列数
M, N = 3, 3class MatrixMultiplication(MRJob):def mapper(self, _, line):# 根据数据的格式，解析输入并区分矩阵A和矩阵B的元素# 假设输入格式为 (i, j, matrix_name, value)i, j, matrix_name, value = line.split()if matrix_name == 'A':for k in range(1, N+1):yield (int(i), k), (matrix_name, int(j), int(value))else:for k in range(1, M+1):yield (k, int(j)), (matrix_name, int(i), int(value))def reducer(self, key, values):A_set, B_set = [], []for v in values:if v[0] == 'A':A_set.append(v)else:B_set.append(v)res = 0for v1 in A_set:for v2 in B_set:if v2[1] == v1[1]:res += v1[2]*v2[2]breakyield key, resif __name__ == '__main__':MatrixMultiplication.run()print("np:", np.matmul(np.array([[2, 1, 3, 4], [10, -8, 7, 2], [9, 1, 6, -2]]), np.array([[3, 2, -8], [1, 5, 2], [4, -7, 3], [4, 1, -7]])))

运行命令

python matmul.py -r inline matrix.txt