0

因此，我平均能够在 22 毫秒内解决一个 200x200 的迷宫（就像没有任何图形的 pacman）。我使用了四个邻居（上、右、左和下）的节点链表。我使用了 FileWriter、文件读取器、缓冲区方法，并使用 BFS 算法从起点到目标进行搜索。如前所述，所有这些任务在 200x200 的迷宫中总共花费了 22 毫秒。我想知道专门使用 Queue 接口是否有助于加快进程。我知道LinkedList实现了Queue，所以我只是使用了LinkedList。关于让它更快的任何建议？

注意：我尽我最大的努力使每种方法都没有太多的 for 循环。仅在编写文件时才使用两个 for 循环。

4

3 回答 3

1

If you use a grid and recursion, you can avoid actually using a loop at all.

Something like

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

prints (in reverse order to avoid creating a list of co-ordinates)

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 更容易预测内存访问。链表倾向于将对象分散在内存中，使 cpus 在需要数据之前更难预取数据。这往往会导致 CPU 在等待从主内存加载数据时停止。

2) 优化文件 io 并确保它没有停止。预先分配文件的大小有助于防止在操作系统调整文件大小时停止。内存映射文件也可能有很大帮助，但里程确实有所不同。

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 回答