Frage Unerwartete Java-Leistung


Ich habe gerade alles, was ich über Java-Optimierung weiß, aus dem Fenster geworfen. Ich habe folgende Aufgabe:

Bei einem 2D-Array, das ein Spielfeld und eine Position auf dem Feld darstellt, füllen Sie ein anderes Array mit der Anzahl der Schritte, die ein Spieler ausführen kann, um zu jeder anderen Position im Feld zu gelangen. Der Spieler kann sich nach oben, unten, links und rechts bewegen. Zum Beispiel sind die ersten Nachbarn alle 1, wobei die Diagonalen alle 2 sind.

Für den ersten Versuch habe ich einen einfachen 4-Wege-Floodfill-Algorithmus ausprobiert. Es war schrecklich langsam.

Zweitens entschied ich mich, die Rekursion loszuwerden und eine einfache Queue zu verwenden. Es funktionierte schön und gab eine enorme Beschleunigung (sehr ungefähr 20x). Hier ist der Code:

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);
            }
        }
    }
}

Nun sagte mir "common sense", dass die Warteschlangenoperationen mit einem statischen Array und einem int-Zeiger schneller wären. Also habe ich die Queue entfernt und benutze ein Standard int [] Array. Der Code ist identisch mit Ausnahme der warteschlangenartigen Operationen. Es sieht jetzt so aus (Wie Sie sehen können, lebe ich nach der C-Seite :)):

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;
            }
        }
    }
}

Wenn ich diesen "optimierten Code" ausführte, war er deutlich langsamer als die Queue und nur etwa doppelt so schnell wie die rekursive Technik. Es gibt auch kaum einen Unterschied, wenn ich das Array als Instanzvariable deklariere. Wie ist das möglich?


5
2017-09-05 06:03


Ursprung


Antworten:


Sie haben die Reihenfolge umgekehrt, während ich optimistisch denke;

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

Das gibt dir normalerweise eine andere Leistung ;-)


3
2017-09-05 09:30



Fügen Sie zwei Zähler in jeder Schleife ein in der for-Schleife und eine in der while-Schleife in beiden Versionen ein, vergleichen Sie die Zahlen, die Sie am Ende erhalten, wie viele Runden machen Sie in jeder Version, wenn Sie eine andere Schleife haben getPossibleDestination dann melde dich an pos Variable auch. Ich denke, das wäre ein guter Ausgangspunkt, um es herauszufinden.

Ein anderer Weg wäre, den Zeitunterschied auf verschiedenen Zeilen in Ihrem Programm zu drucken, sagen wir vor der ersten Schleife, zwischen beiden und am Ende, wenn Sie Ergebnisse vergleichen und wissen, wo es in der zweiten Version lange dauert, können Sie Zeitstempel drucken in der Schleife auf verschiedenen Linien.


1
2017-09-05 06:08