假设你正在编写一个棋盘游戏，游戏的棋盘是一个很大的正方形网格，但是只有少数几个网格中放置了棋子。在这种情况下，大多数网格都是空的，如果对该数组进行持久化存储是不是就浪费了大部分磁盘空间。所以更好的解决方案就是压缩数据，稀疏数组就是一个很简单的解决方案。
什么是稀疏数组
稀疏数组是一种数据结构，用于表示大部分元素为默认值（通常为零或空）的数组，而仅存储非默认值的元素及其对应的索引。这种表示方式可以有效地节省内存空间，尤其是在处理稀疏数据时，即大多数元素都是默认值的情况下。
稀疏数组通常由两个数组组成：索引数组和值数组。索引数组存储非默认值的元素在原始数组中的索引位置，而值数组则存储这些非默认值元素的值。通过这种方式，只需要存储实际存在值的元素，而不需要存储默认值，从而减少了内存的使用量。
稀疏数组在很多情况下都可以提高存储效率和运算效率，特别是当处理大规模稀疏数据时，例如在图形处理、网络分析和机器学习等领域。
定义一个稀疏数组
首先分析一下一个稀疏数组应该记录哪些东西。
- 棋盘的宽高分别是多少：
width和height - 没有数组的地方，默认值是多少：
defalutVal - 一个存放数据的数组：
List<SparseArrData>
那么数据里面应该是什么结构？非常简单
- 坐标
row和col - 值
val
初始代码如下
public class SparseArray<T> {
private int width;
private int height;
private T defaultValue;
private Class<T> type;
class SparseArrData {
int row;
int col;
T val;
public SparseArrData(int row, int col, T val) {
this.row = row;
this.col = col;
this.val = val;
}
@Override
public String toString() {
return "SparseArrData{" +
"row=" + row +
", col=" + col +
", val=" + val +
'}';
}
}
private List<SparseArrData> data;
public SparseArray(int width, int height, T defaultValue, Class<T> type) {
this.width = width;
this.height = height;
this.defaultValue = defaultValue;
this.data = new ArrayList<>();
this.type = type;
}
@Override
public String toString() {
return "SparseArray{" +
"width=" + width +
", height=" + height +
", defaultValue=" + defaultValue +
",\n data=" + data +
"\n}";
}
}
创建一个棋盘
例如19*19，放8个棋子进去，X白棋，O黑棋,空白位置为·
public static void main(String[] args) {
Character[][] chessBoard = new Character[19][19]; // 创建一个19x19的棋盘数组
char defaultVal = '.';
// 初始化棋盘，所有位置都是'.'
for (int i = 0; i < chessBoard.length; i++) {
for (int j = 0; j < chessBoard[0].length; j++) {
chessBoard[i][j] = defaultVal;
}
}
// 放置8个棋子
chessBoard[3][3] = 'X'; // 白色的棋子
chessBoard[5][5] = 'O'; // 黑色的棋子
chessBoard[7][7] = 'X'; // 白色的棋子
chessBoard[9][9] = 'O'; // 黑色的棋子
chessBoard[11][11] = 'X'; // 白色的棋子
chessBoard[13][13] = 'O'; // 黑色的棋子
chessBoard[15][15] = 'X'; // 白色的棋子
chessBoard[17][17] = 'O'; // 黑色的棋子
// 输出棋盘上的棋子类型
for (Character[] chars : chessBoard) {
for (Character aChar : chars) {
System.out.print(aChar + " ");
}
System.out.println();
}
}
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . X . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . O . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . X . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . O . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . X . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . O . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . X . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . O .
. . . . . . . . . . . . . . . . . . .
分析稀疏数组行为
棋盘转稀疏数组
/**
* 从二维数组转换数据。
*
* @param chessBoard 一个包含数据的二维数组，代表棋盘。
* 注：此方法会遍历chessBoard数组，并将非默认值的元素信息添加到data集合中。
*/
public void convertFromArray(T[][] chessBoard) {
// 遍历二维数组
for (int i = 0; i < chessBoard.length; i++) {
for (int j = 0; j < chessBoard[0].length; j++) {
// 当当前位置的值不等于默认值时，将该位置的信息添加到data列表中
if (!Objects.equals(chessBoard[i][j], defaultValue)) {
data.add(new SparseArrData(i, j, chessBoard[i][j]));
}
}
}
}
SparseArray{
width=19,
height=19,
defaultValue=.,
data=[SparseArrData{row=3, col=3, val=X}, SparseArrData{row=5, col=5, val=O}, SparseArrData{row=7, col=7, val=X}, SparseArrData{row=9, col=9, val=O}, SparseArrData{row=11, col=11, val=X}, SparseArrData{row=13, col=13, val=O}, SparseArrData{row=15, col=15, val=X}, SparseArrData{row=17, col=17, val=O}]
}
稀疏数组转棋盘
/**
* 将数据恢复到二维数组中并返回。
* 该方法创建一个指定类型的二维数组，其维度大小根据对象的宽度和高度属性决定。
* 首先，数组中的每个元素会被初始化为默认值。
* 然后，使用之前存储的数据覆盖数组中对应的位置。
*
* @return T[][] 一个二维数组，其类型与对象的类型属性一致，大小与宽度和高度属性一致，元素初始化后被存储的数据覆盖。
*/
public T[][] recoverToArray() {
// 创建一个指定类型和维度的二维数组
@SuppressWarnings("unchecked")
T[][] chessBoard = (T[][]) Array.newInstance(type, width, height);
// 初始化数组中的每个元素为默认值
for (int i = 0; i < width; i++) {
for (int j = 0; j < height; j++) {
chessBoard[i][j] = defaultValue;
}
}
// 使用存储的数据覆盖数组中的相应位置
data.forEach(e -> {
chessBoard[e.row][e.col] = e.val;
});
return chessBoard;
}
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . X . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . O . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . X . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . O . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . X . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . O . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . X . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . O .
. . . . . . . . . . . . . . . . . . .
稀疏数组持久化到本地
/**
* 将稀疏数组的数据保存到指定文件中。
*
* @param fileName 要保存到的文件名称，包括路径。
* 文件格式为每行存储一个数据条目，格式为"行号 列号 值"，首行存储整个数组的宽度、高度和默认值。
*
* 注意：方法内异常不进行处理，仅打印堆栈跟踪。
*/
public void saveToFile(String fileName) {
try (PrintWriter writer = new PrintWriter(new BufferedWriter(new FileWriter(fileName)))) {
// 写入数组的宽度、高度和默认值
writer.println(width + " " + height + " " + defaultValue.toString());
// 遍历数据条目，将每个条目的行号、列号和值写入文件
for (SparseArrData entry : data) {
writer.println(entry.row + " " + entry.col + " " + entry.val.toString());
}
} catch (IOException e) {
e.printStackTrace();
}
}
文件内容
19 19 .
3 3 X
5 5 O
7 7 X
9 9 O
11 11 X
13 13 O
15 15 X
17 17 O
读取本地文件恢复
由于泛型，我们干脆直接从生成String[][]
/**
* 从指定文件中加载数据到二维字符串数组中。
* 每行代表一个二维数组的元素，并由空格分隔三个部分：宽度、高度和默认值。
* 接下来的内容每一行表示一个元素的坐标和值，用空格分隔。
*
* @param fileName 要加载的文件名
* @return 一个二维字符串数组，其中的元素根据文件内容设置。如果出现异常，则返回null。
*/
public static String[][] loadFromFile(String fileName) {
try (BufferedReader reader = new BufferedReader(new FileReader(fileName))) {
// 读取并解析文件的第一行，获取数组的宽度、高度和默认值
String[] size = reader.readLine().split(" ");
int width = Integer.parseInt(size[0]);
int height = Integer.parseInt(size[1]);
String defaultValue = size[2];
String[][] res = new String[width][height];
// 使用默认值填充整个二维数组
for (String[] re : res) {
Arrays.fill(re, defaultValue);
}
// 读取并处理文件的剩余内容，设置数组特定元素的值
String line;
while ((line = reader.readLine()) != null) {
String[] parts = line.split(" ");
int row = Integer.parseInt(parts[0]);
int col = Integer.parseInt(parts[1]);
String value = parts[2];
res[row][col] = value;
}
return res;
} catch (IOException | NumberFormatException e) {
// 处理文件读取或格式解析异常
e.printStackTrace();
return null;
}
}
打印结果
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . X . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . O . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . X . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . O . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . X . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . O . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . X . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . O .
. . . . . . . . . . . . . . . . . . .
全部代码
package dataStructure;
import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;
/**
* @author ssun
*/
public class SparseArray<T> {
private final int width;
private final int height;
private final T defaultValue;
private final Class<T> type;
class SparseArrData {
int row;
int col;
T val;
public SparseArrData(int row, int col, T val) {
this.row = row;
this.col = col;
this.val = val;
}
@Override
public String toString() {
return "SparseArrData{" +
"row=" + row +
", col=" + col +
", val=" + val +
'}';
}
}
private final List<SparseArrData> data;
public SparseArray(int width, int height, T defaultValue, Class<T> type) {
this.width = width;
this.height = height;
this.defaultValue = defaultValue;
this.data = new ArrayList<>();
this.type = type;
}
/**
* 从二维数组转换数据。
*
* @param chessBoard 一个包含数据的二维数组，代表棋盘。
* 注：此方法会遍历chessBoard数组，并将非默认值的元素信息添加到data集合中。
*/
public void convertFromArray(T[][] chessBoard) {
// 遍历二维数组
for (int i = 0; i < chessBoard.length; i++) {
for (int j = 0; j < chessBoard[0].length; j++) {
// 当当前位置的值不等于默认值时，将该位置的信息添加到data列表中
if (!Objects.equals(chessBoard[i][j], defaultValue)) {
data.add(new SparseArrData(i, j, chessBoard[i][j]));
}
}
}
}
/**
* 将数据恢复到二维数组中并返回。
* 该方法创建一个指定类型的二维数组，其维度大小根据对象的宽度和高度属性决定。
* 首先，数组中的每个元素会被初始化为默认值。
* 然后，使用之前存储的数据覆盖数组中对应的位置。
*
* @return T[][] 一个二维数组，其类型与对象的类型属性一致，大小与宽度和高度属性一致，元素初始化后被存储的数据覆盖。
*/
public T[][] recoverToArray() {
@SuppressWarnings("unchecked")
T[][] chessBoard = (T[][]) Array.newInstance(type, width, height);
// 使用 Arrays.fill() 初始化数组为默认值
for (T[] row : chessBoard) {
Arrays.fill(row, defaultValue);
}
// 使用存储的数据覆盖数组中的相应位置
data.forEach(e -> chessBoard[e.row][e.col] = e.val);
return chessBoard;
}
/**
* 将稀疏数组的数据保存到指定文件中。
*
* @param fileName 要保存到的文件名称，包括路径。
* 文件格式为每行存储一个数据条目，格式为"行号 列号 值"，首行存储整个数组的宽度、高度和默认值。
*
* 注意：方法内异常不进行处理，仅打印堆栈跟踪。
*/
public void saveToFile(String fileName) {
try (PrintWriter writer = new PrintWriter(new BufferedWriter(new FileWriter(fileName)))) {
// 写入数组的宽度、高度和默认值
writer.println(width + " " + height + " " + defaultValue.toString());
// 遍历数据条目，将每个条目的行号、列号和值写入文件
for (SparseArrData entry : data) {
writer.println(entry.row + " " + entry.col + " " + entry.val.toString());
}
} catch (IOException e) {
e.printStackTrace();
}
}
/**
* 从指定文件中加载数据到二维字符串数组中。
* 每行代表一个二维数组的元素，并由空格分隔三个部分：宽度、高度和默认值。
* 接下来的内容每一行表示一个元素的坐标和值，用空格分隔。
*
* @param fileName 要加载的文件名
* @return 一个二维字符串数组，其中的元素根据文件内容设置。如果出现异常，则返回null。
*/
public static String[][] loadFromFile(String fileName) {
try (BufferedReader reader = new BufferedReader(new FileReader(fileName))) {
// 读取并解析文件的第一行，获取数组的宽度、高度和默认值
String[] size = reader.readLine().split(" ");
int width = Integer.parseInt(size[0]);
int height = Integer.parseInt(size[1]);
String defaultValue = size[2];
String[][] res = new String[width][height];
// 使用默认值填充整个二维数组
for (String[] re : res) {
Arrays.fill(re, defaultValue);
}
// 读取并处理文件的剩余内容，设置数组特定元素的值
String line;
while ((line = reader.readLine()) != null) {
String[] parts = line.split(" ");
int row = Integer.parseInt(parts[0]);
int col = Integer.parseInt(parts[1]);
String value = parts[2];
res[row][col] = value;
}
return res;
} catch (IOException | NumberFormatException e) {
// 处理文件读取或格式解析异常
e.printStackTrace();
return null;
}
}
@Override
public String toString() {
return "SparseArray{" +
"\n\twidth=" + width +
", \n\theight=" + height +
", \n\tdefaultValue=" + defaultValue +
", \n\tdata=" + data +
"\n}";
}
public static void main(String[] args) {
Character[][] chessBoard = new Character[19][19]; // 创建一个19x19的棋盘数组
Character defaultVal = '.';
// 初始化棋盘，所有位置都是'.'
for (int i = 0; i < chessBoard.length; i++) {
for (int j = 0; j < chessBoard[0].length; j++) {
chessBoard[i][j] = defaultVal;
}
}
// 放置8个棋子
chessBoard[3][3] = 'X'; // 白色的棋子
chessBoard[5][5] = 'O'; // 黑色的棋子
chessBoard[7][7] = 'X'; // 白色的棋子
chessBoard[9][9] = 'O'; // 黑色的棋子
chessBoard[11][11] = 'X'; // 白色的棋子
chessBoard[13][13] = 'O'; // 黑色的棋子
chessBoard[15][15] = 'X'; // 白色的棋子
chessBoard[17][17] = 'O'; // 黑色的棋子
// 输出棋盘上的棋子类型
for (Character[] chars : chessBoard) {
for (Character aChar : chars) {
System.out.print(aChar + " ");
}
System.out.println();
}
SparseArray<Character> sparseArray = new SparseArray<>(chessBoard.length, chessBoard[0].length, defaultVal, Character.class); // 创建一个19x19的稀疏数组
sparseArray.convertFromArray(chessBoard);
System.out.println(sparseArray);
Character[][] res = sparseArray.recoverToArray();
for (Character[] chars : res) {
for (Character aChar : chars) {
System.out.print(aChar + " ");
}
System.out.println();
}
sparseArray.saveToFile("chessMap.txt");
String[][] loadedSparseArray = SparseArray.loadFromFile("chessMap.txt");
System.out.println("=======================================");
if(loadedSparseArray != null){
for (String[] chars : loadedSparseArray) {
for (String aChar : chars) {
System.out.print(aChar + " ");
}
System.out.println();
}
}
}
}
总结
那么稀疏数组就介绍到这里，希望对大家有帮助。
