java - 意外的 Java 性能

Question

我刚刚抛出了我所知道的关于 Java 优化的一切。我有以下任务:

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

对于第一次尝试，我尝试了一种简单的 4 向填充算法。它慢得可怕。

其次，我决定摆脱递归并使用一个简单的队列。它工作得很好，并提供了巨大的加速(大约 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 指针的队列操作会更快。所以我删除了 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;
            }
        }
    }
}

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

Answer 1

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

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

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