基于Spark实现的超大矩阵运算

2024-05-12 23:48

本文主要是介绍基于Spark实现的超大矩阵运算,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

由于标题强调了是在Spark平台实现的矩阵运算,所以本文会非常有针对性的介绍,甚至细节到Spark RDD的算子。

1.算法描述

思想其实很简单,就是矩阵分块计算,而分块矩阵就成了小矩阵,然后就借助于Breeze实现。而对于Spark平台而言,其处理流程如下图:


2.矩阵分块依据

这里仅仅提供一种思路,所以仅供参考。假设有两个矩阵A和B,其中A是m*k的矩阵,B是k*n的矩阵,CPU的总核数是cores,则分块方法:

  • m > k && m > n --> m/2 && cores/2
  • k > m && k > n --> k/2 && cores/2
  • n > k && n > m --> n/2 && cores/2

3.分块矩阵ID标识:BlockID

由于BlockID最后要依靠RDD在集群中通信传输,所以BlockID必须是可序列化的。另外,BlockID要作为分块矩阵的唯一标识,所以BlockID必须具有唯一性,而BlockID的唯一由一下3个属性确定:

  • blockRow:表示该子/分块矩阵在原矩阵中的行号;
  • blockCol:表示该子/分块矩阵在原矩阵中的列号;
  • blockSeq:表示该子/分块矩阵的序列号,默认为0。

4.矩阵分块原理

由于Spark处理文件时,是一行一行的处理的,所以一开始读文件,构成的RDD的类型是:RDD[(seqnum, DenseVector)] (seqnum:输入的行号,DenseVector:对应seqnum的矩阵行)。同时,我们还需要知道2个数据:

  • allrow:矩阵的总行数
  • allcol:矩阵的总列数
另外,由于矩阵运算中,矩阵形状的不同,所以分块的方式也随之而异。如下图,左上图就需要按列分块,右上图就需要按行分块,左下图就需要行列都分块,右下图就需要分别按列分块和按行分块。


4.1按行分块,列不分块

这时需要知道以下2个数据:

  • rowblocknum:按行分块的数量
  • subrow:每块矩阵的行数
然后,分三步处理:

①mapPartitions{map}将RDD[(seqnum, DenseVector)]组成新的数据结构:RDD[(seqnum/subrow, (seqnum, DenseVector))]
②groupByKey作用RDD[(seqnum/subrow, (seqnum, DenseVector))]得到新的数据结构RDD[(seqnum/subrow, Iterable[(seqnum, DenseVector)])]

e.g.
allrow = 1000, rowblocknum = 5, subrow = allrow/rowblocknum = 200

③mapPartitions{map}把Iterable[(seqnum, DenseVector)]的数据填装到子/分块矩阵submatrix中
④构建新的数据结构:RDD[(BlockID, submatrix)]

4.2按行按列分块,和按列分块行不分

这时,我们需要知道3个数据,和准备一个存储行向量的数组:
  • element: Array 读入的每行数据
  • subcol: 每块矩阵的列数
  • colblocknum:按列分块的数量
  • arrayBuff: ArrayBuffer[(BlockID, (Long, Vector))] 存储按列切分的行向量
①mapPartitions{flatMap}将输入的每行数据按列切分,存储到arrayBuff: ArrayBuffer[(BlockID, (Long, Vector))]
②groupByKey作用RDD[(BlockID, (Long, Vector))]得到新的数据结构RDD[(BlockID, Iterable[(seqnum, DenseVector)])]
e.g.
allrow = 1000, rowblocknum = 5, subrow = allrow/rowblocknum = 200
allcol = 1000, colblocknum = 5, subcol = allcol/colblocknum = 200

③mapPartitions{map}把Iterable[(seqnum, DenseVector)]的数据填装到子/分块矩阵submatrix中
④构建新的数据结构:RDD[(BlockID, submatrix)]

5.矩阵乘法的例子

例如:有两个矩阵A和B,其中A是6m*4k的矩阵,被分为3*2块个子矩阵;B是4k*4n的矩阵,被分为2*2块的子矩阵。如图:


下标(x,y,z)是每个子/分块矩阵的唯一标识BlockID(row: Int, col: Int, seq: Int = 0)的参数,即:

  • x:表示该子/分块矩阵在原矩阵中的行号,即blockRow;
  • y:表示该子/分块矩阵在原矩阵中的列号,即blockCol;
  • z:表示该子/分块矩阵的序列号,默认为0,即blockSeq。
和分块块数:
  • mSplitNum:表示矩阵A按行切分的块数;
  • kSplitNum:表示矩阵A按列切分的块数,也是矩阵B按行切分的块数;
  • nSplitNum:表示矩阵B按列切分的块数。
对于该例子,mSplitNum=3、kSplitNum=2、nSplitNum=2。
①mapPartitions{flatMap}把RDD[(BlockID, submatrix)],即矩阵A的每个子/分块矩阵按序列号生成nSplitNum个RDD[(BlockID, submatrix)],矩阵B的每个子/分块矩阵按序列号生成mSplitNum个RDD[(BlockID, subMatrix)],使之一一对应。
对于矩阵A
val array = Array.ofDim[(BlockID, DenseMatrix[Double])](nSplitNum)for (i <- 0 until nSplitNum) {val blockSeq = blockRow * nSplitNum * kSplitNum + i * kSplitNum + blockColarray(i) = (new BlockID(blockRow, i, blockSeq), DenseMatrix)
}

对于矩阵B

val array = Array.ofDim[(BlockID, DenseMatrix [Double])](mSplitNum)for (i <- 0 until mSplitNum) {val blockSeq = i * nSplitNum * kSplitNum + blockCol * kSplitNum + blockRowarray(i) = (new BlockID(i, blockCol, blockSeq), DenseMatrix)
}

e.g. mSplitNum=3,kSplitNum=2,nSplitNum=2
MatrixA

MatrixB


即:MatrixA每个子/分块矩阵复制nSplitNum份,MatrixB每个子/分块矩阵复制mSplitNum份,然后把Key值BlockID相同的子/分块矩阵相乘。
②join两矩阵A和B,使每一对subMatrix相乘,同时更新BlockID(blockRow, blockCol)使blockSeq默认为0。
③reduceByKey按BlockID把子/分块矩阵的乘积相加,得到最终的矩阵。


声明:这只是个人思想,仅做参考。按照这个想法,如果不做任何优化(比如,相乘的小矩阵不分块,而是采用广播的方式等等),在我的实验集群中好像最多能处理10000*10000*10000规模的数据集。


参考文献:

http://www.open-open.com/doc/view/dc6d0ce0233d4db397fd677a2d0a55dc

这篇关于基于Spark实现的超大矩阵运算的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/984081

相关文章

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片,默认是输出到项目文件夹中,可以自己选择其他的文件夹,选择需要拆分的行数和列数,可以通过

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表(即列表中包含列表)转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert

Python使用pip工具实现包自动更新的多种方法

《Python使用pip工具实现包自动更新的多种方法》本文深入探讨了使用Python的pip工具实现包自动更新的各种方法和技术,我们将从基础概念开始,逐步介绍手动更新方法、自动化脚本编写、结合CI/C... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

在Linux中改变echo输出颜色的实现方法

《在Linux中改变echo输出颜色的实现方法》在Linux系统的命令行环境下,为了使输出信息更加清晰、突出,便于用户快速识别和区分不同类型的信息,常常需要改变echo命令的输出颜色,所以本文给大家介... 目python录在linux中改变echo输出颜色的方法技术背景实现步骤使用ANSI转义码使用tpu

Python使用python-can实现合并BLF文件

《Python使用python-can实现合并BLF文件》python-can库是Python生态中专注于CAN总线通信与数据处理的强大工具,本文将使用python-can为BLF文件合并提供高效灵活... 目录一、python-can 库:CAN 数据处理的利器二、BLF 文件合并核心代码解析1. 基础合

Python使用OpenCV实现获取视频时长的小工具

《Python使用OpenCV实现获取视频时长的小工具》在处理视频数据时,获取视频的时长是一项常见且基础的需求,本文将详细介绍如何使用Python和OpenCV获取视频时长,并对每一行代码进行深入解析... 目录一、代码实现二、代码解析1. 导入 OpenCV 库2. 定义获取视频时长的函数3. 打开视频文

golang版本升级如何实现

《golang版本升级如何实现》:本文主要介绍golang版本升级如何实现问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录golanwww.chinasem.cng版本升级linux上golang版本升级删除golang旧版本安装golang最新版本总结gola

SpringBoot中SM2公钥加密、私钥解密的实现示例详解

《SpringBoot中SM2公钥加密、私钥解密的实现示例详解》本文介绍了如何在SpringBoot项目中实现SM2公钥加密和私钥解密的功能,通过使用Hutool库和BouncyCastle依赖,简化... 目录一、前言1、加密信息(示例)2、加密结果(示例)二、实现代码1、yml文件配置2、创建SM2工具

Mysql实现范围分区表(新增、删除、重组、查看)

《Mysql实现范围分区表(新增、删除、重组、查看)》MySQL分区表的四种类型(范围、哈希、列表、键值),主要介绍了范围分区的创建、查询、添加、删除及重组织操作,具有一定的参考价值,感兴趣的可以了解... 目录一、mysql分区表分类二、范围分区(Range Partitioning1、新建分区表:2、分

MySQL 定时新增分区的实现示例

《MySQL定时新增分区的实现示例》本文主要介绍了通过存储过程和定时任务实现MySQL分区的自动创建,解决大数据量下手动维护的繁琐问题,具有一定的参考价值,感兴趣的可以了解一下... mysql创建好分区之后,有时候会需要自动创建分区。比如,一些表数据量非常大,有些数据是热点数据,按照日期分区MululbU