Sparse array of data structures

Based on the realization of two-dimensional sparse array, I will sort out the concept and application of sparse array.

1. Concept

In fact, it is still an array. Through the regulations, the elements of the array are given specific meanings, and the array with a small amount of data but a large space is saved with a small storage space.

   Regulation:

The first row and the first column of the sparse array store the number of rows in the original array

The first row and the second column of the sparse array store the number of columns of the original array

The first row and the third column of the sparse array store the number of elements in the original array

2. Application example

Here is an example of chessboard storage that is used on the Internet as an example.

On a 10*10 backgammon board, the user places several black and white pieces.

(1) Now it is necessary to save the current chessboard;

(2) The disk reading operation can be performed to restore the current chessboard.

The code is implemented as follows:

(1) Define a two-dimensional array to simulate a chessboard

// Define a two-dimensional array, the array value is 1 for sunspots and 2 for whites
        int[][] chessAr = new int[10][10];
        chessAr[2][2] = 1;
        chessAr[5][6] = 1;
        chessAr[2][3] = 2;
        chessAr[3][3] = 1;
        chessAr[7][2] = 2;
        chessAr[8][6] = 1;
        for(int[] a : chessAr){
            System.out.println(Arrays.toString(a));
        }

// The printing effect is as follows
[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, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 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, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

(2) Define a sparse array to simulate the storage situation

        // Count the number of elements in a 2D array
        int size = 0;
        for (int i = 0;i<chessAr.length;i++){
            for(int j=0;j<chessAr[i].length;j++){
                if (chessAr[i][j] == 1 || chessAr[i][j] == 2){
                    size++;
                }
            }
        }


        // define a sparse array
        int[][] sparseArray = new int[size+1][3];

        sparseArray[0][0] = 10;
        sparseArray[0][1] = 10;
        sparseArray[0][2] = size;

        for(int[] a : sparseArray){
            System.out.println(Arrays.toString(a));
        }

        // Sparse array records two-dimensional data information
        int flag = 1;
        for (int i = 0; i < chessAr.length; i++) {
            for (int j = 0; j < chessAr[i].length; j++) {
                if (chessAr[i][j] == 1 || chessAr[i][j] == 2) {
                    sparseArray[flag][0] = i;
                    sparseArray[flag][1] = j;
                    sparseArray[flag][2] = chessAr[i][j];
                    flag++;
                }
            }
        }
        System.out.println();
        System.out.println();
        System.out.println();
        for(int[] a : sparseArray){
            System.out.println(Arrays.toString(a));
        }

// The sparse array is printed as follows
[10, 10, 6]
[2, 2, 1]
[2, 3, 2]
[3, 3, 1]
[5, 6, 1]
[7, 2, 2]
[8, 6, 1]

(3) Recover the chessboard by sparse array

// define an empty two-dimensional array
        int[][] chessArr2 = new int[sparseArray[0][0]][sparseArray[0][1]];
        // 2D data is populated from sparse array records
        for(int i = 1 ;i < sparseArray.length ; i++){
            chessArr2[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }
        System.out.println();
        System.out.println();
        System.out.println();
        for(int[] a : chessArr2){
            System.out.println(Arrays.toString(a));
        }

// The printing effect is as follows
[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, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 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, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

3. Pay attention to the use of sparse data

In the actual development process, we must keep in mind that we use sparse data to better save system space and improve performance.

Therefore, before use, it is necessary to estimate the amount of data in the container to prevent abuse.

For example, if a 10*10 two-dimensional array normally occupies 100 elements of space, it has nothing to do with whether the value of the array elements is meaningful.

When 33 elements are meaningful, use sparse array to save, then the occupied space is 33*3+3 = 102. At this time, it is not suitable to use sparse prime group.

  

 

Tags: data structure

Posted by RaythMistwalker on Sun, 22 May 2022 07:53:07 +0300