5

我刚刚把我所知道的关于 Java 优化的一切都抛到了窗外。我有以下任务：

给定一个表示比赛场地和场地位置的 2D 数组，用玩家到达场地中其他每个位置所需的步数填充另一个数组。玩家可以上下左右移动。例如，第一个邻居全为 1，对角线全为 2。

第一次尝试，我尝试了一个简单的 4-way floodfill 算法。它慢得可怕。

其次，我决定摆脱递归并使用简单的队列。它工作得很好，并提供了巨大的加速（非常大约 20 倍）。这是代码：

private void fillCounterArray(int[] counters, int position) {
    Queue<Integer> queue = new ArrayDeque<Integer>(900);

    // 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.add(destination[i]);
        }
    }

    // Now fill up the space.
    while (!queue.isEmpty()) {
        int pos = queue.remove();
        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.add(dest);
            }
        }
    }
}

现在，“常识”告诉我，使用静态数组和 int 指针的队列操作会更快。所以我删除了队列并使用标准的 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;
            }
        }
    }
}

当我运行这个“优化代码”时，它比使用队列慢得多，并且只比递归技术快两倍。当我将数组声明为实例变量时也几乎没有任何区别。这怎么可能？

4

2 回答 2

3

我认为您在优化时颠倒了顺序；

The queue is fifo, first in first out
The array is lifo, last in first out, as you walk it downwards

这通常会给你不同的表现;-)

于 2012-09-05T09:30:00.193 回答
1

在每个循环中插入两个计数器，一个在 for 循环中，一个在 while 循环中，在两个版本中，比较你最后得到的数字，你在每个版本中做了多少轮，如果你有另一个循环getPossibleDestination然后记录pos变量也。我想这将是一个很好的起点。

另一种方法是在程序的不同行上打印时间差，比如说在第一个循环之前，在两个和最后之间，一旦你比较结果并知道在第二个版本中需要很长时间的地方，你可以打印时间戳在不同行的循环中。

于 2012-09-05T06:08:58.793 回答