小言_互联网的博客

什么是稀疏数组?稀疏数组详解

383人阅读  评论(0)

【1】背景

如下图所示,这里有一个 15 × 15 的棋盘,如果现在要让你通过编码的方式,让你将这盘棋局保存起来,你会怎么做呢?

面对行列数据的保存,我相信大多人第一时间都会想到用二维数组进行保存。

【2】普通数组保存棋盘数据

比如,我们可以将棋盘进行抽象化,用一个 15 × 15 的二维数组来表示,然后用 0 表示空点,用 1 表示白子,用 2 表示黑子,于是就可以抽象为如下模样。

于是,我们可以通过如下代码,将数据保存到二维数组中。


  
  1. /**
  2. * 将棋盘数据保存为二维数组
  3. */
  4. public static int[][] saveChess() {
  5. // 初始化棋盘(大小为 15 * 15),int默认为0(即空点)
  6. int[][] arr = new int[ 15][ 15];
  7. // 保存白子(用1表示)
  8. arr[ 5][ 5] = 1;
  9. arr[ 7][ 5] = 1;
  10. arr[ 6][ 7] = 1;
  11. // 保存黑子(用2表示)
  12. arr[ 6][ 6] = 2;
  13. arr[ 7][ 6] = 2;
  14. arr[ 8][ 6] = 2;
  15. arr[ 7][ 7] = 2;
  16. return arr;
  17. }

【3】普通数组的不足之处

上面,我们通过了一个最普通的方法,将棋盘数据保存在了一个二维数组中,整个数组我们用了 15 × 15(共 275)个点来保存数据,其中有 268 个点都是空的。实际来说,我们只需要将有价值的黑白子保存起来即可,因为只要我们知道黑白子数据,以及棋盘的大小,那么这268个空点是可以不用进行保存的。

把这样没有价值的数据起来,不但会浪费存储空间的大小,如果写入到磁盘中,还会增大 IO 的读写量,影响性能,这就是用普通二维数组来表示棋盘数据的不足之处。

那么,针对以上情况,我们该如何将我们的数据格式进行优化呢?于是就引出了我们接下来的稀疏数组的概念。

【4】稀疏数组

所谓稀疏数组,从字面上我们也可以得知,它仍然是一个数组,他的作用就是将一个对应的数组数据进行优化,比如,我们将上面的二维数组进行优化。

我们可以定义一个数组,只记录黑白子的数据,具体如下:

从这个表中,我们可以只看到有价值的数据了,如果我们再将这个表抽象为一个二维数组,那么他的大小就是 7 * 3 = 21 个点了。

这相对之前的200多个点来说,确实少了许多节点,节省了很多存储空间。

但只这样保存也是不够的,因为我们并没有保存原棋盘的大小,那么我们不妨约定增加一行,保存原来棋盘的大小(二维数组的大小),那么我们可以用如下进行表示:

这里我们约定用第1行数据来记录原二维数组的规模,第 1 个值为原数组总行数,第 2 个值为原数组列数,第 3 个值为有价值数据的总数。

这样,我们就将原数组数据,优化为了一个稀疏数组。

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

根据上面的原理,我们就可以通过代码方式,将原来的普通二维数组,优化为一个稀疏数组了,具体编码如下:


  
  1. /**
  2. * 普通数组转稀疏数组
  3. *
  4. * @param arr_普通数组
  5. * @return 稀疏数组
  6. */
  7. public static int[][] castSparseArray( int[][] arr) {
  8. // 原数组的总行数
  9. int row = arr.length;
  10. // 原数组的总列数
  11. int cloumn = arr[ 0].length;
  12. // 获取黑白子总数
  13. int sum = 0;
  14. for ( int i = 0; i < arr.length; i++) {
  15. for ( int j = 0; j < arr.length; j++) {
  16. if (arr[i][j] != 0) {
  17. sum++;
  18. }
  19. }
  20. }
  21. // 创建稀疏数组(sum+1 行表示 sum 个黑白子 + 1行规模)
  22. int[][] sparseArray = new int[sum + 1][ 3];
  23. // 第 1 行原二维数组的行、列、棋子总数
  24. sparseArray[ 0][ 0] = row;
  25. sparseArray[ 0][ 1] = cloumn;
  26. sparseArray[ 0][ 2] = sum;
  27. // 第 2 行开始存具体数据(每行都是一个棋子数据)
  28. int sparseRow = 0;
  29. for ( int i = 0; i < arr.length; i++) {
  30. for ( int j = 0; j < arr.length; j++) {
  31. if (arr[i][j] != 0) {
  32. sparseRow++;
  33. sparseArray[sparseRow][ 0] = i;
  34. sparseArray[sparseRow][ 1] = j;
  35. sparseArray[sparseRow][ 2] = arr[i][j];
  36. }
  37. }
  38. }
  39. return sparseArray;
  40. }

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

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


  
  1. /**
  2. * 稀疏数组转普通数组
  3. *
  4. * @param sparseArr_稀疏数组
  5. * @return 普通二维数组
  6. */
  7. public static int[][] castToArray( int[][] sparseArr) {
  8. // 获取稀疏数组第 1 行(记录了原数组的总行数和总列数)
  9. int[] rowFirst = sparseArr[ 0];
  10. // 初始化数组(棋盘)
  11. int row = rowFirst[ 0];
  12. int column = rowFirst[ 1];
  13. int[][] arr = new int[row][column];
  14. // 初始化数据(黑白子)
  15. for ( int i = 1; i < sparseArr.length; i++) {
  16. int[] sparseRow = sparseArr[i];
  17. arr[sparseRow[ 0]][sparseRow[ 1]] = sparseRow[ 2];
  18. }
  19. return arr;
  20. }

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

【总结】

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

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


  
  1. /**
  2. * 二维数组与稀疏数组
  3. *
  4. * @author ZhangYuanqiang
  5. * @since 2021年5月13日
  6. */
  7. public class SparseArrayTest {
  8. public static void main(String[] args) {
  9. // 用二维数组保存棋盘
  10. int[][] arr = saveChess();
  11. // 打印二维数组
  12. print(arr);
  13. // 将二维数组转化为稀疏数组
  14. int[][] sparseArr = castSparseArray(arr);
  15. // 打印稀疏数组
  16. print(sparseArr);
  17. // 稀疏数组转二位数组
  18. int[][] arr2 = castToArray(sparseArr);
  19. print(arr2);
  20. }
  21. /**
  22. * 打印普通数组
  23. */
  24. public static void print(int[][] arr) {
  25. for ( int i = 0; i < arr.length; i++) {
  26. for ( int j = 0; j < arr[i].length; j++) {
  27. System.out.print(arr[i][j] + "\t");
  28. }
  29. System.out.println();
  30. }
  31. System.out.println( "--------------------------------------");
  32. }
  33. /**
  34. * 将棋盘数据保存为二维数组
  35. */
  36. public static int[][] saveChess() {
  37. // 初始化棋盘(大小为 15 * 15)
  38. int[][] arr = new int[ 15][ 15];
  39. // 保存白子(用1表示)
  40. arr[ 5][ 5] = 1;
  41. arr[ 7][ 5] = 1;
  42. arr[ 6][ 7] = 1;
  43. // 保存黑子(用2表示)
  44. arr[ 6][ 6] = 2;
  45. arr[ 7][ 6] = 2;
  46. arr[ 8][ 6] = 2;
  47. arr[ 7][ 7] = 2;
  48. return arr;
  49. }
  50. /**
  51. * 普通数组转稀疏数组
  52. *
  53. * @param arr_普通数组
  54. * @return 稀疏数组
  55. */
  56. public static int[][] castSparseArray( int[][] arr) {
  57. // 原数组的总行数
  58. int row = arr.length;
  59. // 原数组的总列数
  60. int cloumn = arr[ 0].length;
  61. // 获取黑白子总数
  62. int sum = 0;
  63. for ( int i = 0; i < arr.length; i++) {
  64. for ( int j = 0; j < arr.length; j++) {
  65. if (arr[i][j] != 0) {
  66. sum++;
  67. }
  68. }
  69. }
  70. // 创建稀疏数组(sum+1 行表示 sum 个黑白子 + 1行规模)
  71. int[][] sparseArray = new int[sum + 1][ 3];
  72. // 第 1 行原二维数组的行、列、棋子总数
  73. sparseArray[ 0][ 0] = row;
  74. sparseArray[ 0][ 1] = cloumn;
  75. sparseArray[ 0][ 2] = sum;
  76. // 第 2 行开始存具体数据(每行都是一个棋子数据)
  77. int sparseRow = 0;
  78. for ( int i = 0; i < arr.length; i++) {
  79. for ( int j = 0; j < arr.length; j++) {
  80. if (arr[i][j] != 0) {
  81. sparseRow++;
  82. sparseArray[sparseRow][ 0] = i;
  83. sparseArray[sparseRow][ 1] = j;
  84. sparseArray[sparseRow][ 2] = arr[i][j];
  85. }
  86. }
  87. }
  88. return sparseArray;
  89. }
  90. /**
  91. * 稀疏数组转普通数组
  92. *
  93. * @param sparseArr_稀疏数组
  94. * @return 普通二维数组
  95. */
  96. public static int[][] castToArray( int[][] sparseArr) {
  97. // 获取稀疏数组第 1 行(记录了原数组的总行数和总列数)
  98. int[] rowFirst = sparseArr[ 0];
  99. // 初始化数组(棋盘)
  100. int row = rowFirst[ 0];
  101. int column = rowFirst[ 1];
  102. int[][] arr = new int[row][column];
  103. // 初始化数据(黑白子)
  104. for ( int i = 1; i < sparseArr.length; i++) {
  105. int[] sparseRow = sparseArr[i];
  106. arr[sparseRow[ 0]][sparseRow[ 1]] = sparseRow[ 2];
  107. }
  108. return arr;
  109. }
  110. }

 

 

 


转载:https://blog.csdn.net/sunnyzyq/article/details/116763427
查看评论
* 以上用户言论只代表其个人观点,不代表本网站的观点或立场