码代码的冰果果

个人在线笔记

0%

稀疏数组

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 6.4k 阅读时长 ≈ 12 分钟

导语：矩阵是很多领域中研究的数学对象，在数据结构中主要讨论的是如何存储矩阵中的元素，从而使矩阵的各种运算能有效进行。一般在高级编程语言中，我们都是使用二维数组来存储矩阵的，所以稀疏矩阵又可以叫做稀疏数组。稀疏数组可以看作是对普通数组的压缩处理，从而节约存储空间、运算资源。什么？你没有听说过稀疏数组？那你一定不要错过了。

介绍

关于稀疏矩阵引用一下“官方”的定义：在矩阵中，若数值为0的元素数目远远多于非0元素的数目，并且非0元素分布没有规律时，则称该矩阵为稀疏矩阵；与之相反，若非0元素数目占大多数时，则称该矩阵为稠密矩阵。

矩阵是很多领域中研究的数学对象，在数据结构中主要讨论的是如何存储矩阵中的元素，从而使矩阵的各种运算能有效进行。由于在实际应用中总会有数组中存在大量无意义0的情况，所以在存储数组时不仅会浪费掉大量的存储空间还会占用运算资源、程序运行时间，使用稀疏数组可以有效的解决上述的问题。

上图中，左侧为一个稀疏矩阵（数组），右侧为它所对应的三元组表（也是一个二维数组）。在三元组表中，为了便于描述稀疏数组，会加上一行“总体”信息在前边，表示总行数、总列数、非0元素总个数。从第二行开始以行、列、值的顺序存放二维数组的数据，一行一个数据。当一个二维数组符合稀疏数组的要求时（非0元素数目占大多数），存放其所对应的三元组表明显比存放原始二维数组更加地节约磁盘空间。

总结一下：

  • 普通二维数组非0元素数目占大多数时，使用稀疏数组（三元组表）进行存储可以节约存储空间，优化程序性能。
  • 普通二维数组转换为稀疏数组，是指转换为其对应的三元组表。
  • 三元组表，第一行保存总行数、总列数、非0元素总个数，第二行开始以行、列、值的顺序保存原始二维数组的数据。

应用场景

稀疏数组，也是一个二维数组，所以在应用普通二维数组的场景中都可以使用稀疏数组，以压缩数组的存储空间。那非0元素数目占多少才是上边所说的大多数呢？通过观察原始数组和其对应的三元组表，不难发现这个大多数得是三分之二以上，否则其作用反而会适得其反。稀疏数组的应用场景可以是存储棋盘、地图等等。

代码实现

下边的代码实现以存储围棋棋局为案例，使用java语言实现普通二维数组转换为稀疏数组并保存到磁盘中，从磁盘中读取稀疏数组并转换为普通二维数组。围棋的棋盘可以看作是一个19行19列的二维数组，无子用0表示，白字用1表示，黑子用2表示。往往一个棋局都不会布满棋盘，而是使用少数的棋子摆谱，这就导致存在大量的无子区域，使用稀疏数组来存放棋局可以有效的压缩存储空间。

通过编写一个工具类SparseTool来实现稀疏数组的转换和存储功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
public class SparseTool {
	public static int[][] parseSparse(int[][] arr){//普通二维数组 转换为 稀疏数组
    ...
    }
	public static int[][] parseGeneral(int[][] sparseArr){//稀疏数组  转换为 普通二维数组
    ...
    }	
    private static void checkArr(int[][] arr) {//数组判空
		if(arr==null) {
			throw new IllegalArgumentException("arr can not be null!");
		}
    }
    public static void writeFile(String filePath,int[][] sparseArr) {//保存稀疏数组 到磁盘
    ...
    }
    public static int[][] readFile(String filePath){//从磁盘 读取稀疏数组
    ...
    }
}

普通二维数组转换为稀疏数组

思路：

  1. 计算非0元素的个数sum；遍历普通二维数组。
  2. 创建稀疏数组sparseArr；根据sum可以创建稀疏数组，列数是固定的为3列，行数为sum+1。
  3. 将普通二维数组的非0元素存储到稀疏数组中。

如果看了代码不能理解第三步，可以再复习一下三元组表的特点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
public static int[][] parseSparse(int[][] arr){
	checkArr(arr);//数组判空，若数组为空则抛出异常，下边的语句不会执行
	int sum=0;//记录非0元素总个数
	for(int row=0; row<arr.length; row++) {//row 行；col 列
		for(int col=0; col<arr[row].length; col++) {
			if(arr[row][col]!=0) {
				sum++;
			}
		}
	}
	int[][] sparseArr=new int[sum+1][3];//创建稀疏数组
	sparseArr[0][0]=arr.length;//第一行保存总行数、总列数、非0元素总个数
	sparseArr[0][1]=arr[0].length;
	sparseArr[0][2]=sum;
	int count=0;
	for(int row=0; row<arr.length; row++) {//开始转换
		for(int col=0; col<arr[row].length; col++) {
			if(arr[row][col]!=0) {//第二行开始以行、列、值的顺序保存原始二维数组的数据
				count++;
				sparseArr[count][0]=row;//行
				sparseArr[count][1]=col;//列
				sparseArr[count][2]=arr[row][col];//值
			}
		}
	}
	return sparseArr;
}

保存稀疏数组到磁盘

思路：

  1. 使用对象输出流，直接保存整个数组对象。
  2. 使用覆盖模式进行保存。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
public static void writeFile(String filePath,int[][] sparseArr) {//保存稀疏数组到磁盘
	File file=new File(filePath);
	if(!file.exists()) {//文件不存在，则创建文件
		try {
			file.createNewFile();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	try {
		FileOutputStream fos=new FileOutputStream(file,false);//覆盖模式
		ObjectOutputStream os=new ObjectOutputStream(fos);
		os.writeObject(sparseArr);
		os.flush();
		fos.flush();
		os.close();
		fos.close();
	}catch (Exception e) {
		System.err.println("文件保存失败！");
	}
}

稀疏数组转换为普通二维数组

思路：

  1. 创建普通二维数组arr；读取稀疏数组的第一行数据，第一行保存着原始二维数组的总行数、总列数、非0元素总个数。
  2. 将稀疏数组第一行后边的元素存储到普通二维数组中。

如果看了代码不能理解，可以再复习一下三元组表的特点。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
	public static int[][] parseGeneral(int[][] sparseArr){
		checkArr(sparseArr);
		int rows=sparseArr[0][0];//读取稀疏数组的第一行数据
		int cols=sparseArr[0][1];
		int  sum=sparseArr[0][2];
		int[][] arr=new int[rows][cols];//创建普通二维数组
		for(int i=1;i<=sum;i++) {//开始转换（遍历稀疏数组第一行后边的数据（故i=1开始））
//			行-row   => sparseArr[i][0];
//			列-col   => sparseArr[i][1];
//			值-value => sparseArr[i][2];
			arr[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2];
		}
		return arr;
	}

从磁盘读取稀疏数组

思路：

  1. 保存时使用对象输出流，读取时使用对象输入流。
  2. 转换为稀疏数组对应的数据类型再进行return。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
public static int[][] readFile(String filePath){//从磁盘读取稀疏数组
	int[][] sparseArr = null;
	File file=new File(filePath);
	if(file.exists()) {
		try {
			InputStream is = new FileInputStream(file);
			ObjectInputStream ois=new ObjectInputStream(is);
			sparseArr=(int[][])ois.readObject();
			ois.close();
			is.close();
		} catch (Exception e) {
			System.err.println("文件读取失败！");
		}
	}
	return sparseArr;
	
}

测试

新建一个Test类进行测试。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
public class Test {
	public static void main(String[] args) {
		String filePath="e:\\Desktop\\sparseArr.data";//存储路径
		int[][] arr=new int[19][19];
		arr[2][5]=1;//导入几个棋子
		arr[3][5]=1;
		arr[3][7]=2;
		arr[2][6]=2;
		arr[3][6]=2;
		arr[4][6]=2;
		
		printArr(arr);//原始二维数组
		
		int[][] sparseArr=SparseTool.parseSparse(arr);//普通二维数组 转换为 稀疏数组
		SparseTool.writeFile(filePath, sparseArr);//存储到磁盘
		int[][] sparseArr2=SparseTool.readFile(filePath);//从磁盘读取
		printArr(sparseArr2);
		
		int[][] arr2=SparseTool.parseGeneral(sparseArr2);//稀疏数组 转换为 普通二维数组
		printArr(arr2);
	}

	private static void printArr(int[][] arr) {//打印二维数组
		for(int row=0; row<arr.length; row++) {//row 行；col 列
			for(int col=0; col<arr[row].length; col++) {
				System.out.print(arr[row][col]+"  ");
			}
			System.out.println();
		}
	}
}

测试结果：

原始二维数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  1  2  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  1  2  2  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  2  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0

转换后的稀疏数组（三元组表）：

1
2
3
4
5
6
7
 
19  19  6  
2   5   1  
2   6   2  
3   5   1  
3   6   2  
3   7   2  
4   6   2

稀疏数组存储到磁盘后，重新读取出来并转换为普通二维数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  1  2  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  1  2  2  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  2  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0

传送门：查看完整源码！

若图片不能正常显示，请在浏览器中打开

欢迎关注我的其它发布渠道