CODEWITHSUNDEEP
java
user1999309
user1999309

Reputation: 1

How to make a faster breadth first search?

So, I was able to solve a 200x200 maze (just like pacman without any graphics) in 22 ms, on average. I used a linkedlist of nodes that four neighbours (up, right, left, and down). I have used a FileWriter, file reader, buffer methods, and used BFS algorithm to make a search from a start point to a goal. All these tasks took a total of 22 ms on a 200x200 maze, like mentioned earlier. I was wondering if specifically using the Queue interface would help speed up the process. I know that LinkedList implements Queue, so I just used LinkedList. Any suggestions on making it faster?

NOTE: I tried my best to keep each method free from too many for loops. I have use two for loops only when I write a file.

Upvotes: 0

Views: 2148

Answers (3)

Chris K
Chris K

Reputation: 11907

Some ideas that jump straight to mind are as follows, be sure to measure as you go:

1) store all data in an array and make sure to iterate over the array in a standard 'step' size. This will make it easier for the CPU to predict memory access. Linked lists tend to scatter objects around memory, making it harder for cpus to prefetch data before needing it. Which tends to lead to stalled CPUs as they wait for data to be loaded from main memory.

2) optimise file io and make sure that it is not stalling. Pre allocating the size of the file helps prevent stalls while the os resizes files. Memory mapping a file may also help quite a bit, but mileage does vary.

3) pin the thread doing the work to a single core on a CPU. This will maximise CPU cache hits and I have often seen a boost of 5x from this alone.

4) if you find yourself regularly modifying an array and checking its length. Be aware that java stores array lengths right next to the arrays contents, thus writing to an array element can invalidate the same cache line that holds the value of array.lengt. If this happens then the CPU will stall,, so store the length in a desperate variable or a constant.

5) review your algorithm for duplicated work and stream line

Upvotes: 0

Peter Lawrey
Peter Lawrey

Reputation: 533482

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

Upvotes: 1

user1695202
user1695202

Reputation: 11

It really depends on the access pattern you are using. You won't see a big difference between a Queue and a LinkedList. If you are accessing elements by their position an ArrayList may actually be faster.

Additionally if you are looking at the overall performance of the whole thing have you broken down how long each major section takes? For example, wrapping the FileReader in a BufferedReader may significantly speed up the file reading portion.

Upvotes: 0

Related Questions