5

Javaの最適化について知っていることはすべて窓の外に投げ出しました。私には次のタスクがあります。

競技場とフィールド上の位置を表す2D配列が与えられた場合、別の配列に、プレーヤーがフィールド内の他のすべての位置に到達するために実行できるステップ数を入力します。プレイヤーは上下左右に移動できます。たとえば、最初の隣接線はすべて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ポインターを使用したキュー操作の方が高速であると私に言いました。そこで、キューを削除して、標準の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;
            }
        }
    }
}

この「最適化されたコード」を実行したとき、キューを使用するよりも大幅に遅く、再帰的手法の約2倍の速さしかありませんでした。配列をインスタンス変数として宣言する場合も、ほとんど違いはありません。これはどのように可能ですか？

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

各ループに2つのカウンターを挿入します。1つはforループに、もう1つはwhileループに両方のバージョンで挿入し、最後に取得した数値を比較します。各バージョンで何ラウンドを実行しますか。別のループがある場合は、変数getPossibleDestinationをログに記録します。posそれも。それを理解するための良い出発点になると思います。

もう1つの方法は、プログラムのさまざまな行に時差を印刷することです。たとえば、最初のループの前、両方の間、および最後に、結果を比較して、2番目のバージョンで時間がかかる場所がわかったら、タイムスタンプを印刷できます。異なる行のループ内。

于 2012-09-05T06:08:58.793 に答える