在 java 中存储 2D 数组的最小方法

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

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

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

我想出的用于存储数组的选项：

将它们作为long存储在基数 7 中。这最多仅适用于 24 (24.3717) 位，因为long不能超过2^63位。
将它们存储为String(例如{{0, 0, 0, 1}, {3, 6, 2, 0}}会变成"00013620")。这只会占用更少的空间(我认为)，因为一个字符仍然是 1 个字节。
使用类似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指出的那样，我对HashSets的使用导致了上述错误，但是，我仍然内存不足

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)

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

您似乎正在创建很多板，很难遵循，但似乎您基本上正在生成大小为 6X6 的所有数组的很大一部分，其中每个单元格可以具有 1,2,..,6 的任何值。

这种数组的数量是 6^36 ~= 10^28。

这意味着，即使每个数组只有一个字节(不可能)，您仍然需要 10^16 TB 来容纳所有数组。

我建议您寻找一种不包括显式生成所有可能数组的替代方案。

作为旁注，表示对象的最小位数是ceil(log_2(6^36)) = 94，但要获得最佳结果需要做很多工作，我不会建议这样做。

最直接但仍然节省内存的方法是将每个数组存储为两个long，每个字段占用 3 位(总共 3*36=108 个有用位，开销为 20 个未使用的位)。虽然理论极限小于这个限制，但你几乎肯定希望你的结构与单词边界对齐，因此你并没有真正失去任何东西。不过，您赢得的是访问单个字段既简单又快速，只需要位屏蔽和移位操作。

我还会看一下堆外存储选项，以消除所有对象开销。

相关内容

最新更新

热门标签：