java - 使用编码算法在 RAM 中存储 4x4 2D 矩阵，以实现最小的 RAM 空间使用

Question

有 16 个单元格(4x4 矩阵)的棋盘存在从 1 到 15 的数字(有这样一个游戏)。一个单元格是空的。

如何使用尽可能小的空间将矩阵数据存储在RAM中？

我制作了一个 Board 类的示例，它可以作为一个对象存储在 RAM 中，仅由一个表示矩阵编码版本的 long 属性组成。

这是我的Board类:

import java.io.Serializable;

public class Board implements Serializable {

    private static final long serialVersionUID = 1L;

    private long board; // the only property which is stored in RAM

    public Board() {
        board = 0x123456789abcdef0L; // 0 represents the empty-cell
    }

    public int[][] getBoardMatrix() { // decoding algorithm
        int[][] boardMatrix = new int[BoardController.ROWS][BoardController.COLUMNS];
        String boardString = getBoardString();
        for (int rowIndex = 0; rowIndex < BoardController.ROWS; rowIndex++) {
            for (int colIndex = 0; colIndex < BoardController.COLUMNS; colIndex++) {
                boardMatrix[rowIndex][colIndex] = Integer.valueOf(
                        String.valueOf(boardString.charAt(rowIndex * BoardController.COLUMNS + colIndex)), 16);
            }
        }
        return boardMatrix;
    }

    public void setBoardByMatrix(int[][] boardMatrix) { // encoding algorithm
        StringBuilder sb = new StringBuilder();
        for (int[] row : boardMatrix) {
            for (int cell : row) {
                sb.append(cell);
            }
        }
        board = Integer.valueOf(sb.toString(), 16);
    }

    private String getBoardString() {
        return String.format("%x", board);
    }
}

我还使用一个类，代表一种具有一些静态属性的模块或 Controller :

public class BoardController {
    public static final int ROWS = 4;
    public static final int COLUMNS = 4;
}

我的具体问题: 是否有更好的方法来存储该矩阵以实现最小 RAM 使用？

Answer 1

最大的内存浪费:引用。

不要存储 Board 数组 - 数组中的每个条目都不是 Board，而是指向 Board 的指针。这意味着您立即浪费了几乎一半的可用空间。保存板子时，不要将其保存为类，而是保存为 long。当您需要使用板时，请将其从长板转换回板。这样，您可以创建一个 long 数组，但在需要时仍将它们视为对象。

class Board
{
    public static Board fromLong(long value) {
        int[] positions = new int[16];
        List<Integer> possibilities = new ArrayList<Integer>(16);
        for (int i = 15; i >= 0; i--)
            possibilities.add(i);

        long ignore = 0;
        for (int i = 15; i > 0; i--) {
            // Rounds towards zero
            long index = (value - ignore) / factorial(i);
            ignore += index * factorial(i);
            positions[i] = possibilities.remove(index);
        }
        positions[0] = possibilities.get(0);

        return new Board(positions);
    }

    /* Note that while this returns a long, only the lowest 45 bits contain data */
    public long toLong() {
        List<Integer> possibilities = new ArrayList<Integer>(16);
        for (int i = 15; i >= 0; i--)
            possibilities.add(i);

        long value = 0;
        for (int i = 15; i > 0; i--) {
            int position = positions[i];
            int index = possibilities.indexOf(position);
            value += index * factorial(i);
            possibilities.remove(index);
        }
        return value;
    }
}

免责声明:我还没有运行此代码，我仍在工作(只是在等待编译时运行)。

你可以算出这 block 板可以产生多少种不同的组合。我们将空白视为数字 0。

第一个图 block 有 16 个唯一值。一旦知道第一个图 block 的值，下一个图 block 就只有 15 个可能的值，而第三个图 block 则只有 14 个可能的值。一直跟踪到最后一个，您就会得到

16 * 15 * 14 * 13 ... * 3 * 2 * 1

这是 16 的阶乘(写为“16!”)。结果是一个巨大的数字:2.092279e+13

现在需要多少位来存储这么大的数字？

log2(2.092279e+13) = 44.2501404699

当然，您不能使用 0.25 位，因此我们必须四舍五入到 45。主板上最有效的存储占用 45 位。然而，这是java，所以你不能只分配45位。