如何縮短首次搜索範圍？

因此，我能夠在22毫秒內平均解決200x200的迷宮（就像沒有任何圖形的pacman）。我使用了四個鄰居節點的鏈表（向上，向右，向左和向下）。我使用了FileWriter，文件閱讀器，緩衝區方法，並使用BFS算法從起點到目標進行搜索。如前所述，所有這些任務在200x200迷宮中總共花費了22毫秒。我想知道是否專門使用隊列接口將有助於加快進程。我知道LinkedList實現了Queue，所以我只使用LinkedList。有關使其更快的任何建議？如何縮短首次搜索範圍？

注意：我盡最大努力讓每個方法免於太多for循環。只有在寫入文件時，我才使用兩個for循環。

來源

2013-03-17 user1999309

22ms是相當不錯，給你一些I/O你使用。首先，你有沒有你用來完成任務的代碼？其次，你有更大的比例 - 2000x2000,20000x20000等嗎？ – Makoto 2013-03-17 03:18:14

也許你應該發佈代碼？ – 2013-03-17 03:18:49

這實際上取決於您使用的訪問模式。你不會在Queue和LinkedList之間看到很大的區別。如果你正在通過它們的位置訪問元素，ArrayList實際上可能會更快。

此外，如果您正在查看整體效果的整體表現，請細分每個主要部分需要多長時間？例如，將FileReader包裝在BufferedReader中可能會顯着加速文件讀取部分。

來源

2013-03-17 03:24:57 user1695202

如果使用網格和遞歸，可以避免實際使用循環。

喜歡的東西

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-17 04:01:37

是直接跳到腦海中如下的一些想法，一定要衡量隨你去：

1）將所有數據存儲在一個數組中，並確保以標準「步長」大小遍歷數組。這將使CPU更容易預測內存訪問。鏈接列表傾向於在內存周圍分散對象，這使得cpus在需要它之前預取數據更加困難。這往往會導致CPU停滯不前，因爲它們會等待數據從主內存中加載。

2）優化文件io並確保它不會停滯。預先分配文件的大小有助於防止在OS調整文件大小時出現停頓。內存映射文件也可能有所幫助，但里程確實有所不同。 3）將執行工作的線程固定到CPU上的單個內核上。這將最大限度地提高CPU緩存命中率，而且我經常從這一點看到5倍的提升。 4）如果你發現你自己經常修改一個數組並檢查它的長度，那麼這個數組就會變成一個數組。請注意，java將數組長度緊靠數組內容存儲，因此寫入數組元素可以使包含array.lengt值的同一緩存行無效。如果發生這種情況，那麼CPU將會停止，所以將長度存儲在絕望變量或常量中。

5）複製你的算法複製工作和流線

來源

2013-03-17 13:58:12

如何縮短首次搜索範圍？

回答

相關問題