0

そのため、200x200 の迷路 (グラフィックなしの pacman と同じように) を平均 22 ミリ秒で解くことができました。4 つの隣接ノード (上、右、左、および下) のリンクリストを使用しました。FileWriter、ファイル リーダー、バッファ メソッドを使用し、BFS アルゴリズムを使用して、開始点から目標までの検索を行いました。前述のように、これらすべてのタスクは 200x200 の迷路で合計 22 ミリ秒かかりました。特に Queue インターフェースを使用すると、プロセスがスピードアップするのに役立つかどうか疑問に思っていました。LinkedList が Queue を実装していることはわかっているので、LinkedList を使用しました。高速化に関する提案はありますか？

注: 各メソッドで for ループが多すぎないように最善を尽くしました。ファイルを書き込むときだけ、2 つの for ループを使用しました。

4

3 に答える 3

1

グリッドと再帰を使用すると、実際にループを使用することをまったく回避できます。

何かのようなもの

public static void main(String... ignored) {
    search(2, 2, "..........\n" +
            ".########.\n" +
            "...#......\n" +
            "#####.####\n" +
            "X.........\n");
}

public static boolean search(int x, int y, String grid) {
    String[] rows = grid.split("\n");
    char[][] grid2 = new char[rows.length][];
    for (int i = 0; i < rows.length; i++) {
        String row = rows[i];
        grid2[i] = row.toCharArray();
    }
    return search(x, y, grid2);
}

public static boolean search(int x, int y, char[][] grid) {
    if (x < 0 || x >= grid.length || y < 0 || y > grid[0].length)
        return false;
    char ch = grid[x][y];
    if (ch == 'X') {
        System.out.println("End " + x + ", " + y);
        return true;
    }
    // - is been here before
    // # is a wall.
    if (ch == '-' || ch == '#') {
        return false;
    }
    grid[x][y] = '-'; // been here before.
    boolean found = search(x - 1, y, grid) || search(x + 1, y, grid)
            || search(x, y - 1, grid) || search(x, y + 1, grid);
    grid[x][y] = ch;
    if (found)
        System.out.println("... " + x + ", " + y);
    return found;
}

印刷 (座標のリストの作成を避けるために逆順)

End 4, 0
... 4, 1
... 4, 2
... 4, 3
... 4, 4
... 4, 5
... 3, 5
... 2, 5
... 2, 6
... 2, 7
... 2, 8
... 2, 9
... 1, 9
... 0, 9
... 0, 8
... 0, 7
... 0, 6
... 0, 5
... 0, 4
... 0, 3
... 0, 2
... 0, 1
... 0, 0
... 1, 0
... 2, 0
... 2, 1
... 2, 2
于 2013-03-17T04:01:37.297 に答える
0

すぐに頭に浮かぶいくつかのアイデアは次のとおりです。実行するときに必ず測定してください。

1) すべてのデータを配列に格納し、標準の「ステップ」サイズで配列を反復処理するようにします。これにより、CPU がメモリ アクセスを予測しやすくなります。リンクされたリストは、メモリの周りにオブジェクトを分散させる傾向があるため、CPU が必要になる前にデータをプリフェッチすることが難しくなります。これにより、CPU がメイン メモリからデータがロードされるのを待つため、CPU が停止する傾向があります。

2) ファイル io を最適化し、ストールしていないことを確認します。ファイルのサイズを事前に割り当てると、OS がファイルのサイズを変更する際の停止を防ぐのに役立ちます。ファイルのメモリ マッピングもかなり役立つ場合がありますが、マイレージは異なります。

3) 作業を行っているスレッドを CPU 上の単一のコアに固定します。これにより、CPU キャッシュ ヒットが最大化され、これだけで 5 倍のブーストが得られることがよくあります。

4) 配列を定期的に変更し、その長さをチェックしている場合。java は配列の内容のすぐ隣に配列の長さを格納することに注意してください。したがって、配列要素に書き込むと、array.lengt の値を保持する同じキャッシュ ラインが無効になる可能性があります。これが発生すると、CPU が停止するため、長さを必死の変数または定数に格納します。

5) 重複作業のアルゴリズムを見直して合理化する

于 2013-03-17T13:58:12.647 に答える
0

使用しているアクセスパターンに大きく依存します。Queue と LinkedList の間に大きな違いはありません。位置によって要素にアクセスしている場合、ArrayList の方が実際には高速である可能性があります。

さらに、全体の全体的なパフォーマンスを見ている場合、各主要セクションにかかる時間を内訳していますか? たとえば、FileReader を BufferedReader でラップすると、ファイルの読み取り部分が大幅に高速化される場合があります。

于 2013-03-17T03:24:57.177 に答える