我刚刚抛出了所有关于Java优化的知识.我有以下任务:
给定表示比赛场地和场地位置的2D数组,填充另一个数组,其中包含玩家可以进入该区域中每个其他位置的步数.玩家可以向上,向下,向左和向右移动.例如,第一个邻居将全部为1,对角线全部为2.
对于第一次尝试,我尝试了一种简单的4向Floodfill算法.它的速度非常慢.
其次,我决定摆脱递归并使用一个简单的队列.它工作得很好,速度很快(非常大约20倍).这是代码:
private void fillCounterArray(int[] counters,int position) {
Queue
现在,“常识”告诉我,使用静态数组和int-pointer的队列操作会更快.所以我删除了Queue并使用标准的int []数组.代码是相同的,除了类似队列的操作.它现在看起来像这样(你可以看到,我用来生活在C方:) :):
private void fillCounterArray(int[] counters,int position) {
// Array and its pointer.
int[] queue = new int[900]; // max size of field
int head = 0;
// Obtain the possible destinations from position,check the valid ones
// and add it the stack.
int[] destination = board.getPossibleDestinations(position);
for (int i = 0; i < destination.length; i++) {
if (board.getBoard()[destination[i]] == Board.CLEAR) {
counters[destination[i]] = 1;
queue[head++] = dest[i];
}
}
// Now fill up the space.
while (head > 0) {
int pos = queue[--head];
int steps = counters[pos];
destination = board.getPossibleDestinations(pos);
for (int i = 0; i < destination.length; i++) {
int dest = destination[i];
if (board.getBoard()[dest] == Board.CLEAR && (counters[dest] > steps + 1 || counters[dest] == 0)) {
counters[dest] = steps + 1;
queue[head++] = dest;
}
}
}
}
当我运行这个“优化代码”时,它明显慢于使用Queue,速度只有递归技术的两倍.当我将数组声明为实例变量时,几乎没有任何区别.这怎么可能?
最佳答案
你在优化的同时颠倒了我的想法;
The queue is fifo,first in first out
The array is lifo,last in first out,as you walk it downwards
这通常会给你不同的表现;-)