java - 在java中存储二维数组的最小方法

Question

我正在尝试生成一组 2D int应该(至少)为 6x6 的数组。每个数组存储 0-6 的值。我尝试使用简单的 HashSet<int[][]>存储它们(使用 512MB 内存)，我很快就得到了错误

Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded

只有很短的路要进入程序。

我想到的用于存储数组的选项:

1. 将它们存储为 long在基数 7 中。这只适用于最多 24 (24.3717) 位数字，因为 long不能超过 2^63位。

2. 将它们存储为 String (例如 {{0, 0, 0, 1}, {3, 6, 2, 0}} 将变为 "00013620" )。这只会占用少 4 倍的空间(我认为)，因为 char 仍然是 1 个字节。

3. 使用像 BitSet 这样的东西或 BigInteger ？我不知道每个是什么或它们是如何工作的。

所以我的问题是:存储 0 - 6 值的 6 x 6 数组的最小方法是什么？上面的选项是否有效，或者是否存在更简单的方法？

---

注意:如果有必要，我可以使用 8GB 内存。

我的代码(它与国际象棋有关，如果你必须知道的话): n是数组的大小(宽度和高度)，应该能够达到(或超过)6。

public static HashSet<int[][]> getBoards(int[][] data, int zero, int num) {
    HashSet<int[][]> ret = new HashSet<int[][]>(0);

    if (zero == num) {
        ret.add(data);
    } else if (zero == 0) {
        for (int y = 0; y < n; y++) {
            for (int x = 0; x < n; x++) {
                for (int i = 1; i < 7; i++) {
                    int[][] d0 = new int[n][n];
                    d0[y][x] = i;
                    ret.addAll(getBoards(d0, 1, num));
                }
            }
        }
    } else {
        for (int y = 0; y < n; y++) {
            for (int x = 0; x < n; x++) {
                if (data[y][x] == 0) continue;

                HashSet<int[]> moves = getMoves(data[y][x], x, y);

                while (moves.iterator().hasNext()) {
                    int[] m = moves.iterator().next();

                    for (int i = 0; i < 6; i++) {
                        int[][] d0 = arrayCopy(data);
                        d0[m[0]][m[1]] = i;

                        ret.addAll(getBoards(d0, zero + 1, num));
                    }
                }
            }
        }
    }

    return ret;
}

public static HashSet<int[]> getMoves(int piece, int xPos, int yPos) {
    HashSet<int[]> ret = new HashSet<int[]>(0);

    for (int y = 0; y < n; y++) {
        for (int x = 0; x < n; x++) {
            if (x == xPos && y == yPos) continue;

            switch (piece) {
            case 1:
                if (y - yPos == 1 && Math.abs(x - xPos) == 1) ret.add(new int[] {y, x});
                break;
            case 2:
                if (Math.abs(y - yPos) + Math.abs(x - xPos) == 3 && x != xPos && y != yPos) ret.add(new int[] {y, x});
                break;
            case 3:
                if (Math.abs(y - yPos) == Math.abs(x - xPos)) ret.add(new int[] {y, x});
                break;
            case 4:
                if (y == yPos || x == xPos) ret.add(new int[] {y, x});
                break;
            case 5:
                if (Math.abs(y - yPos) == Math.abs(x - xPos) || y == yPos || x == xPos) ret.add(new int[] {y, x});
                break;
            case 6:
                if (Math.abs(y - yPos) <= 1 && Math.abs(x - xPos) <= 1) ret.add(new int[] {y, x});
                break;
            default:
                throw new IllegalArgumentException("Unknown Piece Number (" + piece + ")");
            }
        }
    }

    return ret;
}

完整错误:

Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded
at ChessGenerator.arrayCopy(ChessGenerator.java:120)
at ChessGenerator.getBoards(ChessGenerator.java:71)
at ChessGenerator.getBoards(ChessGenerator.java:74)
at ChessGenerator.getBoards(ChessGenerator.java:74)
at ChessGenerator.getBoards(ChessGenerator.java:74)
at ChessGenerator.getBoards(ChessGenerator.java:74)
at ChessGenerator.getBoards(ChessGenerator.java:74)
at ChessGenerator.getBoards(ChessGenerator.java:74)
at ChessGenerator.getBoards(ChessGenerator.java:56)
at ChessGenerator.main(ChessGenerator.java:23)

编辑: 正如@Louis 所指出的，我对 HashSet 的使用s 导致了上述错误，但是，我的内存仍然不足

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at ChessGenerator.arrayCopy(ChessGenerator.java:119)
at ChessGenerator.getBoards(ChessGenerator.java:70)
at ChessGenerator.getBoards(ChessGenerator.java:73)
at ChessGenerator.getBoards(ChessGenerator.java:73)
at ChessGenerator.getBoards(ChessGenerator.java:73)
at ChessGenerator.getBoards(ChessGenerator.java:73)
at ChessGenerator.getBoards(ChessGenerator.java:73)
at ChessGenerator.getBoards(ChessGenerator.java:73)
at ChessGenerator.getBoards(ChessGenerator.java:58)
at ChessGenerator.main(ChessGenerator.java:23)

Answer 1

如果您期望 HashSet 只保留唯一的 int[][]，并消除重复项，那是行不通的——等于int[][](以及所有数组)的 和 hashCode 实现是基于身份的。如果您一直依赖唯一性来保持不同数组的数量较少，那是行不通的；您将不得不将它们包装在实现正确的 hashCode 和 equals 的类型中。