The sparse array

Why a sparse array?

Arrays are a common way to store data, but sometimes they waste space; For example, in a 5*5 game of backgammon, a black spot represents a 1, a white spot represents a 2, and a blank area represents a 0. To represent the data in the checkerboard, we might solve this problem with a two-dimensional array, resulting in the following

0 1 0 2 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
Copy the code

Now, in this array, we’re going to waste some space, because these are all zeros; To solve this problem and avoid wasting too much space, we need to use sparse arrays.

introduce

A sparse array can be used to store an array when most of its elements are zero, or when the array has the same value

handling

  • How many rows, how many columns, how many different values are in the array
  • Reduce the size of your program by recording elements and columns and values with different values in a small array

Implementation method

It’s just recording the coordinates and values of the elements in the array

  1. The sparse array has 3 columns, which are row, column and value respectively. The number of rows is the number of different values of the original array plus 1.
  2. The first linearray[0]Record the number of rows and columns in an array, and the number of different values;
  3. Each row then records the index of a value to the column and column of the original array and its own value.
0 1 0 2 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
Copy the code

We use a sparse array to represent the original array

5 5 3
0 1 1
0 3 2
1 0 1
Copy the code

The sparse array is much smaller than the original array: the original array has 25 elements, while the sparse array has only 12.

role

Can compress data, reduce memory space usage

implementation

public static void main(String[] args) {
    // Create a primitive two-dimensional array
    //0: no pieces, 1: black, 2: white
    int chessArr1[][] = new int[11] [11];
    // Set the elements of the two-dimensional array
    chessArr1[1] [2] = 1;
    chessArr1[2] [3] = 2;
    chessArr1[4] [5] = 2;
    // Output the original two-dimensional array:
    System.out.println("Original two-dimensional array:");
    printArray(chessArr1);

    // Convert the two-dimensional array to a sparse array
    //1. Iterate through the two-dimensional array to get the number of non-zero data
    int sum = 0;

    for (int i = 0; i < 11; i++) {
        for (int j = 0; j < 11; j++) {
            if(chessArr1[i][j] ! =0) { sum++; }}}//2. Create a sparse array
    int sparesArr[][] = new int[sum + 1] [3];
    // Assign to the sparse array
    sparesArr[0] [0] = 11;
    sparesArr[0] [1] = 11;
    sparesArr[0] [2] = sum;

    // Iterate over the two-dimensional array, storing non-zero values in sparesArr
    int count = 0;//count is used to record the number of non-zero data points
    for (int i = 0; i < 11; i++) {
        for (int j = 0; j < 11; j++) {
            if(chessArr1[i][j] ! =0) {
                count++;
                sparesArr[count][0] = i;
                sparesArr[count][1] = j;
                sparesArr[count][2] = chessArr1[i][j]; }}}// Outputs a sparse array
    System.out.println();
    System.out.println("The resulting sparse array is:");
    printArray(sparesArr);
    System.out.println();

    // Restore the sparse array to a two-dimensional array
    // First read the first row of the sparse array and create the original two-dimensional array based on its data
    int chessArr2[][] = new int[sparesArr[0] [0]][sparesArr[0] [1]].// Read the elements in the last few lines of the sparse array (starting with the second line) and assign them to the original two-dimensional array

    for (int i = 1; i < sparesArr.length; i++) {
        chessArr2[sparesArr[i][0]][sparesArr[i][1]] = sparesArr[i][2];
    }

    // Output the restored two-dimensional array
    System.out.println();
    System.out.println("Restored two-dimensional array");
    printArray(chessArr2);
}

// Prints the array
public static void printArray(int[][] array) {
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array[0].length; j++) {
            System.out.printf("%d\t", array[i][j]); } System.out.println(); }}Copy the code
The original two-dimensional array: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	2	0	0	0	0	0	0	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	0The sparse array obtained is:11	11	3	
1	2	1	
2	3	2	
4	5	2The restored two-dimensional array0	0	0	0	0	0	0	0	0	0	0	
0	0	1	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	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	
Copy the code

Pay attention to

  • Not all arrays are good for sparse arrays
  • Must be satisfied when most elements in an array are 0 or the same value