GitHub source code sharing

Project homepage: github.com/gozhuyinglo…

Source: github.com/gozhuyinglo…

Access requirements for backgammon games

Before introducing sparse arrays, let’s first introduce a requirement. Here is a backgammon board (15 * 15) that wants to save and leave midway through the game, hoping to continue playing next time it is opened. How do we do that?

From our observation of the checkerboard, we can use a two-dimensional array of ints to store 0 where there are no pieces, 1 where there are white pieces, and 2 where there are spots. Then our array might look like this:

As you can see, using a two-dimensional array solves this requirement. However, we also found a problem that there are too many zeros storing the same value, which causes a waste of space. Is there another storage method? The answer is that you can use sparse arrays. Let’s see how sparse arrays work!

Sparse Array

Sparse arrays can be used to hold an array when most of its elements are zeros or have the same value.

Sparse arrays are handled as follows:

  1. The number of rows and columns in the array and the number of different values
  2. Reduce the size of the data by recording rows and columns of elements with different values and their values in a small array.

So let’s convert this two-dimensional array to a sparse array and see what it looks like.

Row stores the total number of rows, col stores the total number of columns, and value stores the number of non-zero (different values) elements. The other rows have the same structure. Each row stores information about a non-zero element. Row stores the element’s row, col stores the element’s column, and value stores the element’s value.

Code implementation

We use code to achieve two-dimensional array and sparse array mutual conversion, the following is the concrete implementation!

public class SparseArrayDemo {

    public static void main(String[] args) {
        System.out.println("----------------------- Plain array");
        int[][] initialArray = initArray();
        printArray(initialArray);
        System.out.println("----------------------- Common array --> Sparse array");
        int[][] sparseArray = arrayConvertSparseArray(initialArray);
        printArray(sparseArray);
        System.out.println("----------------------- Sparse array --> Normal array");
        int[][] array = sparseArrayConvertArray(sparseArray);
        printArray(array);
    }

    /** * Initializes the backgammon array **@return* /
    static int[][] initArray() {
        // 0 is empty, 1 is white, and 2 is black
        int[][] array = new int[15] [15];
        array[3] [11] = 1;
        array[4] [10] = 2;
        array[5] [9] = 2;
        array[6] [8] = 2;
        array[6] [7] = 1;
        array[7] [8] = 1;
        array[7] [7] = 2;
        array[8] [6] = 1;
        return array;
    }

    /** * Prints a two-dimensional array **@param array
     */
    static void printArray(int[][] array) {
        for (int[] row : array) {
            for (int data : row) {
                System.out.printf("%s\t", data); } System.out.println(); }}/** * Count the number of non-zero values **@param array
     * @return* /
    static int valueCount(int[][] array) {
        int count = 0;
        for (int[] row : array) {
            for (int data : row) {
                if(data ! =0) { count++; }}}return count;
    }

    /** * An ordinary array becomes a sparse array **@param array
     * @return* /
    static int[][] arrayConvertSparseArray(int[][] array) {
        int rowNum = array.length;
        int colNum = array[0].length;
        int valueNum = valueCount(array);

        int[][] sparseArray = new int[valueNum + 1] [3];
        sparseArray[0] [0] = rowNum;
        sparseArray[0] [1] = colNum;
        sparseArray[0] [2] = valueNum;

        int rowCount = 1;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                int value = array[i][j];
                if(value ! =0) {
                    sparseArray[rowCount][0] = i;
                    sparseArray[rowCount][1] = j;
                    sparseArray[rowCount][2] = value; rowCount++; }}}return sparseArray;
    }

    /** * Sparse array to normal array **@param sparseArray
     * @return* /
    static int[][] sparseArrayConvertArray(int[][] sparseArray) {
        int rowNum = sparseArray[0] [0];
        int colNum = sparseArray[0] [1];
        int valueNum = sparseArray[0] [2];

        int[][] array = new int[rowNum][colNum];

        for (int i = 1; i < valueNum + 1; i++) {
            int row = sparseArray[i][0];
            int col = sparseArray[i][1];
            int value = sparseArray[i][2];
            array[row][col] = value;
        }

        returnarray; }}Copy the code

Output result:

-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- general array 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 1 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 2 0 0 0 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 2 1 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 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 0 0 0 0 0 0 0 0 0 0 0 0 ----------------------- Plain array --> sparse array 15 15 8 3 11 1 4 10 2 5 9 2 6 7 1 6 8 2 7 7 2 7 8 1 8 6 1 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- > sparse array ordinary array 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 1 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 2 0 0 0 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 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 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 0 0 0 0 0 0 0 0 0 0 0 0Copy the code

Get more content

Wechat search: code nong StayUp

Personal homepage: GoZhuyinglong.github. IO