【1】背景
如下图所示，这里有一个 15 × 15 的棋盘，如果现在要让你通过编码的方式，让你将这盘棋局保存起来，你会怎么做呢？
面对行列数据的保存，我相信大多人第一时间都会想到用二维数组进行保存。
【2】普通数组保存棋盘数据
比如，我们可以将棋盘进行抽象化，用一个 15 × 15 的二维数组来表示，然后用 0 表示空点，用 1 表示白子，用 2 表示黑子，于是就可以抽象为如下模样。
于是，我们可以通过如下代码，将数据保存到二维数组中。
-
/**
-
* 将棋盘数据保存为二维数组
-
*/
-
public
static
int[][] saveChess() {
-
// 初始化棋盘（大小为 15 * 15），int默认为0（即空点）
-
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;
-
}
【3】普通数组的不足之处
上面，我们通过了一个最普通的方法，将棋盘数据保存在了一个二维数组中，整个数组我们用了 15 × 15（共 275）个点来保存数据，其中有 268 个点都是空的。实际来说，我们只需要将有价值的黑白子保存起来即可，因为只要我们知道黑白子数据，以及棋盘的大小，那么这268个空点是可以不用进行保存的。
把这样没有价值的数据起来，不但会浪费存储空间的大小，如果写入到磁盘中，还会增大 IO 的读写量，影响性能，这就是用普通二维数组来表示棋盘数据的不足之处。
那么，针对以上情况，我们该如何将我们的数据格式进行优化呢？于是就引出了我们接下来的稀疏数组的概念。
【4】稀疏数组
所谓稀疏数组，从字面上我们也可以得知，它仍然是一个数组，他的作用就是将一个对应的数组数据进行优化，比如，我们将上面的二维数组进行优化。
我们可以定义一个数组，只记录黑白子的数据，具体如下：
从这个表中，我们可以只看到有价值的数据了，如果我们再将这个表抽象为一个二维数组，那么他的大小就是 7 * 3 = 21 个点了。
这相对之前的200多个点来说，确实少了许多节点，节省了很多存储空间。
但只这样保存也是不够的，因为我们并没有保存原棋盘的大小，那么我们不妨约定增加一行，保存原来棋盘的大小（二维数组的大小），那么我们可以用如下进行表示：
这里我们约定用第1行数据来记录原二维数组的规模，第 1 个值为原数组总行数，第 2 个值为原数组列数，第 3 个值为有价值数据的总数。
这样，我们就将原数组数据，优化为了一个稀疏数组。
【4】二维数组转稀疏数组
根据上面的原理，我们就可以通过代码方式，将原来的普通二维数组，优化为一个稀疏数组了，具体编码如下：
-
/**
-
* 普通数组转稀疏数组
-
*
-
* @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;
-
}
【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;
-
}
-
}
转载：https://blog.csdn.net/sunnyzyq/article/details/116763427