breadth first search optimisation in python

Question

I was solving a problem related to breadth first search. I solved the problem but my solution took the longest time to solve (0.12 as compared to 0.01 and 0.02 done by others). The question is a simple BFS on a graph.

Here is how I have implemented BFS:

def bfs1(g, s):
    parent = {s: None}
    level = {s: 0}
    frontier = [s]
    ctr = 1
    while frontier:
            next = []
            for i in frontier:
                for j in g[i]:
                    if j not in parent:
                        parent[j] = i
                        level[j] = ctr
                        next.append(j)
            frontier = next
            ctr += 1
    return level

Here g and s are adjacency list (dict in case of python) and starting Node respectively.

I learned this approach from MIT algorithms course.

Here is the problem which I was solving.

Below is the complete solution which I submitted

Here d is the graph which I pre-generated 


d={'f1': ['d2', 'e3', 'h2', 'g3'], 'f2': ['d1', 'd3', 'e4', 'h1', 'h3', 'g4'], 'f3': ['d2', 'd4', 'e1', 'e5', 'h2', 'h4', 'g1', 'g5'], 'f4': ['d3', 'd5', 'e2', 'e6', 'h3', 'h5', 'g2', 'g6'], 'd8': ['b7', 'c6', 'f7', 'e6'], 'f6': ['d5', 'd7', 'e4', 'e8', 'h5', 'h7', 'g4', 'g8'], 'f7': ['d6', 'd8', 'e5', 'h6', 'h8', 'g5'], 'f8': ['d7', 'e6', 'h7', 'g6'], 'h3': ['f2', 'f4', 'g1', 'g5'], 'h1': ['f2', 'g3'], 'h6': ['f5', 'f7', 'g4', 'g8'], 'h7': ['f6', 'f8', 'g5'], 'h4': ['f3', 'f5', 'g2', 'g6'], 'h5': ['f4', 'f6', 'g3', 'g7'], 'b4': ['a2', 'a6', 'd3', 'd5', 'c2', 'c6'], 'b5': ['a3', 'a7', 'd4', 'd6', 'c3', 'c7'], 'b6': ['a4', 'a8', 'd5', 'd7', 'c4', 'c8'], 'b7': ['a5', 'd6', 'd8', 'c5'], 'b1': ['a3', 'd2', 'c3'], 'b2': ['a4', 'd1', 'd3', 'c4'], 'b3': ['a1', 'a5', 'd2', 'd4', 'c1', 'c5'], 'd6': ['b5', 'b7', 'c4', 'c8', 'f5', 'f7', 'e4', 'e8'], 'd7': ['b6', 'b8', 'c5', 'f6', 'f8', 'e5'], 'd4': ['b3', 'b5', 'c2', 'c6', 'f3', 'f5', 'e2', 'e6'], 'd5': ['b4', 'b6', 'c3', 'c7', 'f4', 'f6', 'e3', 'e7'], 'b8': ['a6', 'd7', 'c6'], 'd3': ['b2', 'b4', 'c1', 'c5', 'f2', 'f4', 'e1', 'e5'], 'd1': ['b2', 'c3', 'f2', 'e3'], 'e1': ['c2', 'd3', 'g2', 'f3'], 'f5': ['d4', 'd6', 'e3', 'e7', 'h4', 'h6', 'g3', 'g7'], 'd2': ['b1', 'b3', 'c4', 'f1', 'f3', 'e4'], 'e5': ['c4', 'c6', 'd3', 'd7', 'g4', 'g6', 'f3', 'f7'], 'h2': ['f1', 'f3', 'g4'], 'e3': ['c2', 'c4', 'd1', 'd5', 'g2', 'g4', 'f1', 'f5'], 'h8': ['f7', 'g6'], 'e2': ['c1', 'c3', 'd4', 'g1', 'g3', 'f4'], 'g7': ['e6', 'e8', 'f5', 'h5'], 'g6': ['e5', 'e7', 'f4', 'f8', 'h4', 'h8'], 'g5': ['e4', 'e6', 'f3', 'f7', 'h3', 'h7'], 'g4': ['e3', 'e5', 'f2', 'f6', 'h2', 'h6'], 'g3': ['e2', 'e4', 'f1', 'f5', 'h1', 'h5'], 'g2': ['e1', 'e3', 'f4', 'h4'], 'g1': ['e2', 'f3', 'h3'], 'e4': ['c3', 'c5', 'd2', 'd6', 'g3', 'g5', 'f2', 'f6'], 'g8': ['e7', 'f6', 'h6'], 'a1': ['c2', 'b3'], 'a3': ['c2', 'c4', 'b1', 'b5'], 'a2': ['c1', 'c3', 'b4'], 'a5': ['c4', 'c6', 'b3', 'b7'], 'a4': ['c3', 'c5', 'b2', 'b6'], 'a7': ['c6', 'c8', 'b5'], 'a6': ['c5', 'c7', 'b4', 'b8'], 'c3': ['a2', 'a4', 'b1', 'b5', 'e2', 'e4', 'd1', 'd5'], 'c2': ['a1', 'a3', 'b4', 'e1', 'e3', 'd4'], 'c1': ['a2', 'b3', 'e2', 'd3'], 'e6': ['c5', 'c7', 'd4', 'd8', 'g5', 'g7', 'f4', 'f8'], 'c7': ['a6', 'a8', 'b5', 'e6', 'e8', 'd5'], 'c6': ['a5', 'a7', 'b4', 'b8', 'e5', 'e7', 'd4', 'd8'], 'c5': ['a4', 'a6', 'b3', 'b7', 'e4', 'e6', 'd3', 'd7'], 'c4': ['a3', 'a5', 'b2', 'b6', 'e3', 'e5', 'd2', 'd6'], 'e7': ['c6', 'c8', 'd5', 'g6', 'g8', 'f5'], 'a8': ['c7', 'b6'], 'c8': ['a7', 'b6', 'e7', 'd6'], 'e8': ['c7', 'd6', 'g7', 'f6']}


def bfs1(g, s):
        # parent = {s: None}
        level = {s: 0}
        frontier = [s]
        ctr = 1
        while frontier:
                next = []
                for i in frontier:
                    for j in g[i]:
                        if j not in level:
                            # parent[j] = i
                            level[j] = ctr
                            next.append(j)
                frontier = next
                ctr += 1
        return level



    for i in range(int(raw_input())):
        x, y =  raw_input().split()
        print bfs1(d, x).get(y)

What is that supposed to do? What are the arguments (g and s)? What is the expexcted result? — zvone
– zvone, Commented Oct 1, 2016 at 8:39
parent seems useless - you only use it for if j not in parent, and level would work just as well there - but other than that, I don't see any obvious major inefficiencies. — user2357112
– user2357112, Commented Oct 1, 2016 at 8:45
@zvone The title pretty much says what it's supposed to do. Be a BFS, which is a well known algorithm. — amit
– amit, Commented Oct 1, 2016 at 8:48
Regarding parent, it's useful in some, but not this one, and if you're looking for more speed, dropping it will help. — senderle
– senderle, Commented Oct 1, 2016 at 9:15

zvone · Accepted Answer · 2016-10-01 15:02:08Z

The main problem performance-wise seem to be the fact that this is performing a full graph search and returning the distances of all nodes compared to the root node.

That is much more than is needed for the problem at hand.

In the specific chess problem you are trying to solve (find out how many jumps a knight has to make from A to B), this function will find out how many jumps a knigth needs to make from A to every other square.

So, it if input asks for the simplest A1-B3 (answer: 1), this function will also calculate A1-C8, A1-H7...

There are several options for solving that problem. I would get rid of the level variable entirely and replace writing to it with a yield. So instead of:

level[j] = ctr

do this:

yield j, ctr

Then the caller of this function can stop further execution as soon as the wanted result is reached.

Furthermore

I would also rename all the variables, so that it is clear what they are. There is no way you can make meaningful code analysis if it is all cryptic.

Then, replace parent = {} with seen = set(), because you only use it to skip nodes which were already seen.

With those little changes, you get:

def bfs1(adjacency, root):
    seen = {root}
    frontier = [root]
    yield root, 0
    next_distance = 1
    while frontier:
        next_frontier = []
        for node in frontier:
            for next_node in adjacency[node]:
                if next_node in seen:
                    continue
                seen.add(next_node)
                yield next_node, next_distance
                next_frontier.append(next_node)
        frontier = next_frontier
        next_distance += 1

And then you need:

def get_distance_from_a_to_b(a, b, adjacency):
    for node, distance in bfs1(adjacency, a):
        if node == b:
            return distance

stefan · Accepted Answer · 2016-10-02 12:41:57Z

1

There has been some advice to implement a nice bfs. In two dimensional problems you can save half the time by searching from both ends simultanously.

But when it comes to brute optimisation for timing you always go for lookup tables. In your case you have quite nice constraints: 64 positions to start and 64 positions to finish. that is a pretty small lookup table of 4096 integers. So use whatever inefficient algorithm in a helper program to fill that lookup table and print it out. paste that table into the source code of your competition code.

answered Oct 2, 2016 at 12:41

stefan

3,79118 silver badges29 bronze badges

2 Comments

sid597 Over a year ago

I can't do that due to memory limit

stefan Over a year ago

@johnsmith: what is the limit? you could use a char type for lookup. or even a half byte. that woud shrink the table to 4096/2048 chars. by rotation and mirroring you could also normalize the start position to 10 fields, again shrinking the table to 640/320 chars. on my system your adjacency table has a size of 3344.

Collectives™ on Stack Overflow

breadth first search optimisation in python

2 Answers 2

Furthermore

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Furthermore

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related