Map-Reduce实现矩阵乘法

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

矩阵P=MN，p_ik=sum_{j}m_ij*n_jk，把矩阵M看成关系R(I,J,V)，把矩阵N看成关系R(J,K,W).

M,N有公共属性J，M中每个元组(i,j,v)N中的每个元组(j,k,w),两个关系的自然链接会产生元组(i,j,k,v*w),接下来进行分组聚合运算，
也就是矩阵乘法能用两步串联的Map-Reduce实现。


Map函数：将每个矩阵元素m_ij传给键值对(j,(M,i,m_ij)),将每个矩阵元素n_jk传给键值对(j,(N,k,n_jk))。
Reduce函数：对每个键j,检查与之关联的值的列表。对每个来自M的值(M,i,m_ij)和来自N的值(N,k,n_jk),产生元组(i,k,m_ij,n_jk).
                      对于键j，Reduce函数输出满足(i,k,m_ij*n_jk)的所有元组列表作为值。

Map函数：第一步的输出结果传递给该Map函数，这些结果的形式为(j,[(i_1,k_1,v_1),(i_2,k_2,v_2),...,(i_p,k_p,v_p)]),其中每个
                 v_q对应m_{i_qj}和n_{jk_q}的乘积。
                 基于该元素可以产生p个键值对((i_1,k_1),v_1),((i_2,k_2),v_2),...,((i_p,k_p),v_p).
Reduce函数：对每个键(i,k),计算与此键关联的所有值的和，结果记为((i,k),v),其中v是矩阵P=MN的第i行第k列的元素值。

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：Map-Reduce reduce Map edu red

Map函数：对矩阵M中的每个元素m_ij，产生一系列键值对((i,k),(M,j,m_ij))，其中k=1,2,...直到矩阵N的列数。
                 N中的每个元素n_jk,也产生一系列的键值对((i,k),(N,j,n_jk)),其中i=1,2,...,直到矩阵M的行数。

Reduce函数：每个键(i,k)相关联的值(M,j,m_ij)(N,j,n_jk)将组成一个表。Reduce函数必须对每个j将具有相同j值的
                      (M,j,m_ij)和(N,j,n_jk)接通。一个简单的方法是将所有的(M,j,m_ij)和(N,j,n_jk)按照j值排序并放到不同的列表中。
                      将两个列表的第j个元组中m_ij和n_jk抽出来相乘，然后将积相加，与键(i,k)作为Reduce输出。