试图解决15个难题，OutOfMemoryError [英] Trying to solve 15 Puzzle, OutOfMemoryError
问题描述
有什么方法可以优化此代码以免耗尽内存?
Is there any way that I can optimize this code as to not run out of memory?
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.Stack;
public class TilePuzzle {
private final static byte ROWS = 4;
private final static byte COLUMNS = 4;
private static String SOLUTION = "123456789ABCDEF0";
private static byte RADIX = 16;
private char[][] board = new char[ROWS][COLUMNS];
private byte x; // row of the space ('0')
private byte y; // column of the space ('0') private String representation;
private boolean change = false; // Has the board changed after the last call to toString?
private TilePuzzle() {
this(SOLUTION);
int times = 1000;
Random rnd = new Random();
while(times-- > 0) {
try {
move((byte)rnd.nextInt(4));
} catch(RuntimeException e) {
}
}
this.representation = asString();
}
public TilePuzzle(String representation) {
this.representation = representation;
final byte SIZE = (byte)SOLUTION.length();
if (representation.length() != SIZE) {
throw new IllegalArgumentException("The board must have " + SIZE + "numbers.");
}
boolean[] used = new boolean[SIZE];
byte idx = 0;
for (byte i = 0; i < ROWS; ++i) {
for (byte j = 0; j < COLUMNS; ++j) {
char digit = representation.charAt(idx++);
byte number = (byte)Character.digit(digit, RADIX);
if (number < 0 || number >= SIZE) {
throw new IllegalArgumentException("The character " + digit + " is not valid.");
} else if(used[number]) {
throw new IllegalArgumentException("The character " + digit + " is repeated.");
}
used[number] = true;
board[i][j] = digit;
if (digit == '0') {
x = i;
y = j;
}
}
}
}
/**
* Swap position of the space ('0') with the number that's up to it.
*/
public void moveUp() {
try {
move((byte)(x - 1), y);
} catch(IllegalArgumentException e) {
throw new RuntimeException("Move prohibited " + e.getMessage());
}
}
/**
* Swap position of the space ('0') with the number that's down to it.
*/
public void moveDown() {
try {
move((byte)(x + 1), y);
} catch(IllegalArgumentException e) {
throw new RuntimeException("Move prohibited " + e.getMessage());
}
}
/**
* Swap position of the space ('0') with the number that's left to it.
*/
public void moveLeft() {
try {
move(x, (byte)(y - 1));
} catch(IllegalArgumentException e) {
throw new RuntimeException("Move prohibited " + e.getMessage());
}
}
/**
* Swap position of the space ('0') with the number that's right to it.
*/
public void moveRight() {
try {
move(x, (byte)(y + 1));
} catch(IllegalArgumentException e) {
throw new RuntimeException("Move prohibited " + e.getMessage());
}
}
private void move(byte movement) {
switch(movement) {
case 0: moveUp(); break;
case 1: moveRight(); break;
case 2: moveDown(); break;
case 3: moveLeft(); break;
}
}
private boolean areValidCoordinates(byte x, byte y) {
return (x >= 0 && x < ROWS && y >= 0 && y < COLUMNS);
}
private void move(byte nx, byte ny) {
if (!areValidCoordinates(nx, ny)) {
throw new IllegalArgumentException("(" + nx + ", " + ny + ")");
}
board[x][y] = board[nx][ny];
board[nx][ny] = '0';
x = nx;
y = ny;
change = true;
}
public String printableString() {
StringBuilder sb = new StringBuilder();
for (byte i = 0; i < ROWS; ++i) {
for (byte j = 0; j < COLUMNS; ++j) {
sb.append(board[i][j] + " ");
}
sb.append("\r\n");
}
return sb.toString();
}
private String asString() {
StringBuilder sb = new StringBuilder();
for (byte i = 0; i < ROWS; ++i) {
for (byte j = 0; j < COLUMNS; ++j) {
sb.append(board[i][j]);
}
}
return sb.toString();
}
public String toString() {
if (change) {
representation = asString();
}
return representation;
}
private static byte[] whereShouldItBe(char digit) {
byte idx = (byte)SOLUTION.indexOf(digit);
return new byte[] { (byte)(idx / ROWS), (byte)(idx % ROWS) };
}
private static byte manhattanDistance(byte x, byte y, byte x2, byte y2) {
byte dx = (byte)Math.abs(x - x2);
byte dy = (byte)Math.abs(y - y2);
return (byte)(dx + dy);
}
private byte heuristic() {
byte total = 0;
for (byte i = 0; i < ROWS; ++i) {
for (byte j = 0; j < COLUMNS; ++j) {
char digit = board[i][j];
byte[] coordenates = whereShouldItBe(digit);
byte distance = manhattanDistance(i, j, coordenates[0], coordenates[1]);
total += distance;
}
}
return total;
}
private class Node implements Comparable<Node> {
private String puzzle;
private byte moves; // number of moves from original configuration
private byte value; // The value of the heuristic for this configuration.
public Node(String puzzle, byte moves, byte value) {
this.puzzle = puzzle;
this.moves = moves;
this.value = value;
}
@Override
public int compareTo(Node o) {
return (value + moves) - (o.value + o.moves);
}
}
private void print(Map<String,String> antecessor) {
Stack toPrint = new Stack();
toPrint.add(SOLUTION);
String before = antecessor.get(SOLUTION);
while (!before.equals("")) {
toPrint.add(before);
before = antecessor.get(before);
}
while (!toPrint.isEmpty()) {
System.out.println(new TilePuzzle(toPrint.pop()).printableString());
}
}
private byte solve() {
if(toString().equals(SOLUTION)) {
return 0;
}
PriorityQueue<Node> toProcess = new PriorityQueue();
Node initial = new Node(toString(), (byte)0, heuristic());
toProcess.add(initial);
Map<String,String> antecessor = new HashMap<String,String>();
antecessor.put(toString(), "");
while(!toProcess.isEmpty()) {
Node actual = toProcess.poll();
for (byte i = 0; i < 4; ++i) {
TilePuzzle t = new TilePuzzle(actual.puzzle);
try {
t.move(i);
} catch(RuntimeException e) {
continue;
}
if (t.toString().equals(SOLUTION)) {
antecessor.put(SOLUTION, actual.puzzle);
print(antecessor);
return (byte)(actual.moves + 1);
} else if (!antecessor.containsKey(t.toString())) {
byte v = t.heuristic();
Node neighbor = new Node(t.toString(), (byte)(actual.moves + 1), v);
toProcess.add(neighbor);
antecessor.put(t.toString(), actual.puzzle);
}
}
}
return -1;
}
public static void main(String... args) {
TilePuzzle puzzle = new TilePuzzle();
System.out.println(puzzle.solve());
}
}
推荐答案
问题
根本原因是正在创建并存储在toProcess队列和antecessor映射中的大量String对象.你为什么要这么做?
The problem
The root cause is the tons of String objects you are creating and storing in the toProcess Queue and the antecessor Map. Why are you doing that?
查看您的算法.查看您是否真的需要在每个节点中存储200万个以上的节点和500万个字符串.
Look at your algorithm. See if you really need to store >2 million nodes and 5 million strings in each.
这很难发现，因为程序很复杂.实际上，我什至没有尝试理解所有代码.相反，我使用了 VisualVM – Java分析器，采样器和CPU/内存使用情况监视器.
This was hard to spot because the program is complex. Actually, I didn't even try to understand all of the code. Instead, I used VisualVM – a Java profiler, sampler, and CPU/memory usage monitor.
我启动了它:
并查看了内存使用情况.我注意到的第一件事是(显而易见的)事实，即您正在创建吨个对象.
And took a look at the memory usage. The first thing I noticed was the (obvious) fact that you're creating tons of objects.
这是该应用程序的屏幕截图:
This is an screenshot of the app:
如您所见，使用的内存量非常大.在短短40秒内，消耗了2 GB的内存并填满了整个堆.
As you can see, the amount of memory used is tremendous. In as few as 40 seconds, 2 GB were consumed and the entire heap was filled.
我最初认为问题与Node类有关，因为即使实现了Comparable，也没有实现equals.所以我提供了方法:
I initially thought the problem had something to do with the Node class, because even though it implements Comparable, it doesn't implement equals. So I provided the method:
public boolean equals( Object o ) {
if( o instanceof Node ) {
Node other = ( Node ) o;
return this.value == other.value && this.moves == other.moves;
}
return false;
}
但这不是问题.
实际问题出在最上面.
如前所述，真正的解决方案是重新考虑您的算法.同时，无论采取什么其他措施，只会拖延问题的发生.
As previously stated, the real solution is to rethink your algorithm. Whatever else can be done, in the meantime, will only delay the problem.
但是解决方法可能会很有用.一种是重复使用您生成的字符串.您正在非常密集地使用TilePuzzle.toString()方法.最终会经常创建重复的字符串.
But workarounds can be useful. One is to reuse the strings you're generating. You're very intensively using the TilePuzzle.toString() method; this ends up creating duplicate strings quite often.
由于要生成字符串排列，因此可以在几秒钟内创建许多12345ABCD字符串.如果它们是相同的字符串，则没有必要创建具有相同值的数百万个实例.
Since you're generating string permutations, you may create many 12345ABCD strings in matter of seconds. If they are the same string, there is no point in creating millions of instances with the same value.
The String.intern() method allows strings to be reused. The doc says:
返回字符串对象的规范表示形式.
Returns a canonical representation for the string object.
最初为空的字符串池由String类私有维护.
A pool of strings, initially empty, is maintained privately by the class String.
调用intern方法时，如果池已经包含等于equals()方法确定的与此String对象相等的字符串，则返回池中的字符串.否则，将此String对象添加到池中，并返回对此String对象的引用.
When the intern method is invoked, if the pool already contains a string equal to this String object as determined by the equals() method, then the string from the pool is returned. Otherwise, this String object is added to the pool and a reference to this String object is returned.
对于常规应用程序，使用String.intern()可能不是一个好主意，因为它不会让GC回收实例.但是在这种情况下，由于无论如何您都将引用保存在Map和Queue中，因此很有意义.
For a regular application, using String.intern() could be a bad idea because it doesn't let instances be reclaimed by the GC. But in this case, since you're holding the references in your Map and Queue anyway, it makes sense.
因此进行此更改:
public String toString() {
if (change) {
representation = asString();
}
return representation.intern(); // <-- Use intern
}
几乎可以解决内存问题.
Pretty much solves the memory problem.
这是更改后的屏幕截图:
This is a screenshot after the change:
现在，即使几分钟后，堆的使用量也不会达到100 MB.
Now, the heap usage doesn't reach 100 MB even after a couple of minutes.
您正在使用异常来验证移动是否有效，这没关系；但是当您抓住它们时，您只是在忽略它们:
You're using an exception to validate if the movement is valid or not, which is okay; but when you catch them, you're just ignoring them:
try {
t.move(i);
} catch(RuntimeException e) {
continue;
}
如果仍然不使用它们，则可以通过不首先创建异常来节省大量计算量.否则，您将创建数百万个未使用的异常.
If you're not using them anyway, you can save a lot of computation by not creating the exceptions in the first place. Otherwise you're creating millions of unused exceptions.
进行此更改:
if (!areValidCoordinates(nx, ny)) {
// REMOVE THIS LINE:
// throw new IllegalArgumentException("(" + nx + ", " + ny + ")");
// ADD THIS LINE:
return;
}
并改用验证:
// REMOVE THESE LINES:
// try {
// t.move(i);
// } catch(RuntimeException e) {
// continue;
// }
// ADD THESE LINES:
if(t.isValidMovement(i)){
t.move(i);
} else {
continue;
}
备注#2
您正在为每个新的TilePuzzle实例创建一个新的Random对象.如果整个程序只使用一个，那会更好.毕竟，您只使用一个线程.
Remark #2
You're creating a new Random object for every new TilePuzzle instance. It would be better if you used just one for the whole program. After all, you are only using a single thread.
该解决方法解决了堆内存问题，但是又创建了一个涉及PermGen的问题.我只是增加了PermGen的大小，就像这样:
The workaround solved the heap memory problem, but created another one involving PermGen. I simply increased the PermGen size, like this:
java -Xmx1g -Xms1g -XX:MaxPermSize=1g TilePuzzle
备注#4
输出有时是49，有时是50.矩阵的打印方式如下:
Remark #4
The output was sometimes 49 and sometimes 50. The matrices were printed like:
1 2 3 4
5 6 7 8
9 A B C
D E 0 F
1 2 3 4
5 6 7 8
9 A B C
D E F 0
... 50次
这篇关于试图解决15个难题，OutOfMemoryError的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
