首页天道酬勤三元组表示稀疏矩阵,一元稀疏多项式的定义

三元组表示稀疏矩阵,一元稀疏多项式的定义

张世龙 05-12 10:54 20次浏览

【1】背景

如下图所示,这里有15 15个棋盘。 如果现在用代码方式保存这个盘,怎么办?

面对矩阵数据的保存,我想很多人最先考虑用二维数组进行保存。

【2】将板数据保存在普通数组中

例如,可以将棋盘抽象化,用15 15的二维阵列表示。 然后,用0表示空白点,1表示单身棒糖,2表示黑子,可以抽象为:

因此,可以用以下代码将数据保存在二维数组中。

/**板上的数据二维排列*/public static int[][] saveChess () /初始化板(大小为15 * 15 ) ),int默认为0 (即空点) int () arr[7][5]=1; arr[6][7]=1; //黑子(用2表示) arr(6) )=2; arr[7][6]=2; arr[8][6]=2; arr[7][7]=2; 返回警报; } 【3】普通排列不够的地方

上,我们用最常用的方法将板数据保存到二维数组中。 整个数组使用了15 15 (共计225 )个点保存了数据。 其中218个点是空的。 实际上,我们只要保存有价值的黑单身棒棒糖就行了。 因为只要知道黑单身棒棒糖的数据和盘的大小,这218个空点就不用保存了。

这样排列没有价值的数据不仅浪费了存储空间的大小,而且写入磁盘会增加IO的读写量,影响性能。 这就是用普通二维数组表示板数据的缺点。

那么,针对这种情况,该如何优化数据格式呢? 于是引出了我们下一个稀疏排列的概念。

【4】稀疏排列

正如文字所示,稀疏数组仍然是一个数组。 他的作用是优化相应的数组数据。 例如,优化上面的二维数组。

可以定义只记录黑色单身棒棒糖数据的数组。 具体情况如下:

从这张表中只能看到有价值的数据。 如果将该表进一步抽象为二维数组,则他的大小为7 * 3=21分。

与以前的200多个点相比,这减少了节点数量,大大节省了存储容量。

但是,只有这些是不够的。 因为没有保存原始盘的大小,所以尝试增加一行来保存原始盘的大小(二维排列的大小)。 那么,可以表示为:

在这里,我们约定用第一行的数据记录原始二维数组的规模。 第一个值是原始数组的总行数,第二个值是原始数组的列数,第三个值是有价值的数据总数。

因此,将原始数组数据优化为稀疏数组。

【4】从二维排列到稀疏排列

基于上述原理,我们可以通过编码方式将原始的普通二维数组优化为稀疏数组。 具体代码如下。

/** *常规数组稀疏数组* * @param arr_常规数组* @return稀疏数组*/public static int [ ] [ ] castsparsearray [ ] [ ] arr ] { /原始数组的总行数id //获得黑色单身的棒棒糖总数int sum=0; for(intI=0; i arr.length; I ) for(intj=0; j arr.length; j () if ) ARR[I][j]!=0) sum; }//创建稀疏数组(sum 1行表示sum个黑色单身棒棒糖1行规模) ) ) sparse array=new int (sum1) )3);//第1行原始二维阵列的行、列、棋子总数sparseArray[0][0]=row; sparseArray[0][1]=cloumn; sparseArray[0][2]=sum;//从第2行开始具体数据(每行一个棋子数据) int sparseRow=0; for(intI=0; i arr.length; I ) for(intj=0; j arr.length; j () if ) ARR[I][j]!=0) { sparseRow; 稀疏阵列[稀疏行] [

0] = i; sparseArray[sparseRow][1] = j; sparseArray[sparseRow][2] = arr[i][j]; } } } return sparseArray;}

【5】稀疏数组转二维数组

我们用稀疏数组保存数据,主要是为了节省磁盘空间,优化 IO 读写性能,但在最终复原棋盘的时候,我们还是需要将稀疏数组的数据转化为原普通二维数组数据,那么我们又将如何通过编码的方式去实现稀疏数组转二维数组呢?对应编码如下:

/** * 稀疏数组转普通数组 * * @param sparseArr_稀疏数组 * @return 普通二维数组 */public static int[][] castToArray(int[][] sparseArr) { // 获取稀疏数组第 1 行(记录了原数组的总行数和总列数) int[] rowFirst = sparseArr[0]; // 初始化数组(棋盘) int row = rowFirst[0]; int column = rowFirst[1]; int[][] arr = new int[row][column]; // 初始化数据(黑单身的棒棒糖) for (int i = 1; i < sparseArr.length; i++) { int[] sparseRow = sparseArr[i]; arr[sparseRow[0]][sparseRow[1]] = sparseRow[2]; } return arr;}

这样,我们就可以将稀疏数组还原为普通数组了。

【总结】

在存储数组数据的时候,我们如果存在许多默认值的数据,不妨用稀疏数组来进行存储,这样数据相对来说就会瘦小很多,不但可以节省磁盘空间,还可以优化磁盘读写时性能。

最后附上相关的整段代码:

/** * 二维数组与稀疏数组 * * @author ZhangYuanqiang * @since 2021年5月13日 */public class SparseArrayTest { public static void main(String[] args) { // 用二维数组保存棋盘 int[][] arr = saveChess(); // 打印二维数组 print(arr); // 将二维数组转化为稀疏数组 int[][] sparseArr = castSparseArray(arr); // 打印稀疏数组 print(sparseArr); // 稀疏数组转二位数组 int[][] arr2 = castToArray(sparseArr); print(arr2); } /** * 打印普通数组 */ public static void print(int[][] arr) { for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr[i].length; j++) { System.out.print(arr[i][j] + "\t"); } System.out.println(); } System.out.println("--------------------------------------"); } /** * 将棋盘数据保存为二维数组 */ public static int[][] saveChess() { // 初始化棋盘(大小为 15 * 15) int[][] arr = new int[15][15]; // 保存单身的棒棒糖(用1表示) arr[5][5] = 1; arr[7][5] = 1; arr[6][7] = 1; // 保存黑子(用2表示) arr[6][6] = 2; arr[7][6] = 2; arr[8][6] = 2; arr[7][7] = 2; return arr; } /** * 普通数组转稀疏数组 * * @param arr_普通数组 * @return 稀疏数组 */ public static int[][] castSparseArray(int[][] arr) { // 原数组的总行数 int row = arr.length; // 原数组的总列数 int cloumn = arr[0].length; // 获取黑单身的棒棒糖总数 int sum = 0; for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr.length; j++) { if (arr[i][j] != 0) { sum++; } } } // 创建稀疏数组(sum+1 行表示 sum 个黑单身的棒棒糖 + 1行规模) int[][] sparseArray = new int[sum + 1][3]; // 第 1 行原二维数组的行、列、棋子总数 sparseArray[0][0] = row; sparseArray[0][1] = cloumn; sparseArray[0][2] = sum; // 第 2 行开始存具体数据(每行都是一个棋子数据) int sparseRow = 0; for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr.length; j++) { if (arr[i][j] != 0) { sparseRow++; sparseArray[sparseRow][0] = i; sparseArray[sparseRow][1] = j; sparseArray[sparseRow][2] = arr[i][j]; } } } return sparseArray; } /** * 稀疏数组转普通数组 * * @param sparseArr_稀疏数组 * @return 普通二维数组 */ public static int[][] castToArray(int[][] sparseArr) { // 获取稀疏数组第 1 行(记录了原数组的总行数和总列数) int[] rowFirst = sparseArr[0]; // 初始化数组(棋盘) int row = rowFirst[0]; int column = rowFirst[1]; int[][] arr = new int[row][column]; // 初始化数据(黑单身的棒棒糖) for (int i = 1; i < sparseArr.length; i++) { int[] sparseRow = sparseArr[i]; arr[sparseRow[0]][sparseRow[1]] = sparseRow[2]; } return arr; }}

稀疏特征,稀疏线性方程组