使用编码算法将 4x4 二维矩阵存储在 RAM 中以实现最小 RAM-space 使用

Question

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

如何使用尽可能少的 space 将矩阵数据存储在 RAM 中？

我做了一个 class Board 的例子，它可以作为一个对象存储在 RAM 中，只包含一个 long 属性表示编码版本矩阵。

这是我的 Board class:

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);
    }
}

我还使用了一个 class，代表一种具有一些静态属性的模块或控制器：

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

我的具体问题：有没有更好的方法来存储此矩阵以实现最小 RAM 使用？

Answer 1

最大的内存浪费：引用。

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

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;
    }
}

免责声明：我还没有运行这个代码，我还在工作（就在我等待编译的时候）。

你可以算出这个棋盘可以产生多少种不同的组合。让我们将空 space 视为数字 0.

第一个图块有 16 个唯一值。一旦您知道了第一块瓷砖的价值，下一块瓷砖只有 15 个可能的值，而第三块瓷砖只有 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位。

使用编码算法将 4x4 二维矩阵存储在 RAM 中以实现最小 RAM-space 使用

Storing a 4x4 2D-matrix in RAM using encoding algorithm to achieve minimum RAM-space usage

java

performance

ram

session