The sparse array

1 Application Scenario

In a game of backgammon

If you want to save the progress of the game, you can use a two-dimensional array to save the positions of the pieces, as shown below:

Where, 0 represents no chess pieces, 1 represents black, 2 represents white.

Such a 15 x 15 board would store 225 elements in total, but there would be a lot of repeated data, like zeros,

This creates a waste of space.

We can use a sparse array to store the checkerboard.

2 ideas

A sparse array has three columns of data.

In the first row of a sparse array, the first column stores the total number of rows in the original array, the second column stores the total number of columns in the original array, and the third column stores the total number of values.

Each row after the first row of the sparse array stores the location and value of a valid element of the original data: the first column stores the row number of the original data, the second column stores the column number of the original data, and the third column stores the value of the original data.

The result of converting the checkerboard into a sparse array is shown below:

Using the sparse array shown above in this example only requires 9 elements to be stored, and the compression ratio is obvious.

3 implementation

1. Calculate the total number of rows, columns and valid elements of a given original two-dimensional data;
2. Create a sparse array of 3 columns (essentially a normal two-dimensional array);
3. Initialize the first row of the sparse array. The first column in the first row is the total number of rows in the original array, the second column in the first row is the total number of columns in the original array, and the third column in the first row is the number of valid elements in the original array.
4. The original two-dimensional array is traversed, and the valid data is stored in the sparse array. No valid element occupies a row in the sparse array. The first column stores the row number of the element, the second column stores the column number of the element, and the third column stores the value of the element.

code

public class SparseArray {

    public static void main(String[] args) {
        // Initialize a checkerboard array
        int[][] chessArray = initArray();
        System.out.println("Initialize the original array ---------------");
        print(chessArray);
        // Convert to sparse array
        int[][] sparseArray = toSparseArray(chessArray);
        System.out.println("Sparse array ---------------");
        print(sparseArray);
        // Return the original array
        int[][] newChessArray = toChessArray(sparseArray);
        System.out.println("Restored original array ---------------");
        print(newChessArray);
    }

    /** * Initializes a raw 2d data */
    public static int[][] initArray() {
        int[][] chessArray = new int[15] [15];
        chessArray[1] [3] = 1;// Spot location
        chessArray[2] [4] = 2;// The whitespace position
        return chessArray;
    }

    /** * Convert normal 2d data into a sparse array *@param chessArray
     * @return* /
    public static int[][] toSparseArray(int[][] chessArray) {

        // Iterate over the total number of data in the two-dimensional array
        int sum = 0;
        for (int[] row : chessArray) {
            for (int val : row) {
                if (0! = val) { sum++; }}}// Create a sparse array with three elements per row. The first is the row number, the second is the column number, and the third is the value
        int[][] sparesArray = new int[sum+1] [3];
        // Initialize the first row of the sparse array
        int rowNum = chessArray.length;
        int colNum = chessArray[0].length;
        // The number of rows in the first column of the original two-dimensional array
        sparesArray[0] [0] = rowNum;
        // The first line, the second column, is the number of columns in the original two-dimensional array
        sparesArray[0] [1] = colNum;
        // The total number of valid elements in the original two-dimensional array
        sparesArray[0] [2] = sum;
        // Switch to sparse array
        // Record the number of rows in the sparse array
        int sparesRowNum = 0;
        for (int i = 0; i < rowNum; i++) {
            for (int j = 0; j < colNum; j++) {
                if(chessArray[i][j] ! =0) {
                    sparesRowNum++;
                    sparesArray[sparesRowNum][0] = i;
                    sparesArray[sparesRowNum][1] = j;
                    sparesArray[sparesRowNum][2] = chessArray[i][j]; }}}return sparesArray;
    }

    /** * Restore the sparse array to normal two-dimensional data *@param sparseArray
     * @return* /
    public static int[][] toChessArray(int[][] sparseArray) {
        // Restore the total number of rows and columns
        int[] initData = sparseArray[0];
        int[][] chessArray = new int[initData[0]][initData[1]].// Populate the raw data
        for (int i = 1; i < sparseArray.length; i++) {
            int[] rowData = sparseArray[i];
            chessArray[i][rowData[1]] = rowData[2];
        }
        return chessArray;
    }

    /** * Prints the data content */
    public static void print(int[][] chessArray) {
        for (int[] row : chessArray) {
            for (int val : row) {
                System.out.printf("%d ", val); } System.out.println(); }}}Copy the code

The code Github links here