Avoid A Deepcopy When Doing A Bfs

I'm currently solving the second exercise in this assignment (this is not homework, I'm actually trying to solve this other problem). My solution uses a BFS to search for the minim

Solution 1:

There is a number of optimizations to be done.

First, avoid deepcopy, implement it your own copying (this by itself worked for me 5x faster):

classPuzzle(object):def__init__(self, matrix):
        self.matrix = [list(row) for row in matrix]
        self.dim = len(matrix)

    defcopy(self):
        return Puzzle(self.matrix)

Second, in BFS you don't need priority queue, use Queue or implement your own queuing. This gives some speedup. And third, check for being solved before putting it into the queue, not after taking things out. This should allow you to go one level deeper in comparable time:

defsolve(self):
    v = set()

    q = [(0, self)]
    i = 0whileTrue:
        c = q[i]
        i += 1for el in c[1].next():
            t = el.tuple()

            if t notin v:
                if el.solved():
                    return c[0] + 1
                v.add(t)
                q.append((c[0] + 1, el))

Further, using a list of list of bits is very memory-inefficient. You can pack all the bits into a single integer and get much faster solution. Additionally you can precompute masks for allowed moves:

defbits(iterable):
    bit = 1
    res = 0for elem in iterable:
        if elem:
            res |= bit
        bit <<= 1return res

defmask(dim, i, j):
    res = 0for idx inrange(dim * i, dim * (i + 1)):
        res |= 1 << idx
    for idx inrange(j, dim * dim, dim):
        res |= 1 << idx
    return res

defmasks(dim):
    return [mask(dim, i, j) for i inrange(dim) for j inrange(dim)]

classPuzzle(object):
    def__init__(self, matrix):
        ifisinstance(matrix, Puzzle):
            self.matrix = matrix.matrix
            self.dim = matrix.dim
            self.masks = matrix.masks
        else:
            self.matrix = bits(sum(matrix, []))
            self.dim = len(matrix)
            self.masks = masks(len(matrix))

    def__repr__(self):
        returnstr(self.matrix)

    defsolved(self):
        return self.matrix == 0defnext(self):
        for mask in self.masks:
            puzzle = Puzzle(self)
            puzzle.matrix ^= mask
            yield puzzle

    defsolve(self):
        v = set()

        q = [(0, self)]
        i = 0whileTrue:
            c = q[i]
            i += 1for el in c[1].next():
                t = el.matrix

                if t notin v:
                    if el.solved():
                        return c[0] + 1
                    v.add(t)
                    q.append((c[0] + 1, el))

And finally for another factor of 5 you can pass around just bit matrices, instead of whole Puzzle objects and additionally inline some most often used function.

defsolve(self):
    v = set()

    q = [(0, self.matrix)]
    i = 0whileTrue:
        dist, matrix = q[i]
        i += 1for mask in self.masks:
            t = matrix ^ mask

            if t notin v:
                if t == 0:
                    return dist + 1
                v.add(t)
                q.append((dist + 1, t))

For me these optimizations combined give speedup of about 250 times.

Solution 2:

I changed solve to

defsolve(self):
        q = PriorityQueue()
        v = set()

        q.put((0, self))
        whileTrue:
            c = q.get()

            if c[1].solved():
                return c[0]
            else:
                for i inrange(self.dim):
                    for j inrange(self.dim):
                        el = c[1].move(i, j) # do the move
                        t = el.tuple()

                        if t notin v:
                           v.add(t)
                           q.put((c[0] + 1, el.copy())) # copy only as needed

                        c[1].move(i, j) # undo the move

As .move(i, j) is its own inverse. Copies are made but only when the state has not been visited. This reduces the time from 7.405s to 5.671s. But this is not as big an improvement as expected.

Then replacing def tuple(self): with:

deftuple(self):
     returntuple(tuple(r) for r in self.matrix)

reduces the time from 5.671s to 0.531s. That should do it.

Full listing:

from copy import deepcopy
from Queue import PriorityQueue

# See: http://www.seas.upenn.edu/~cis391/Homework/Homework2.pdfclassPuzzle(object):
    def__init__(self, matrix):
        self.matrix = matrix
        self.dim = len(matrix)

    def__repr__(self):
        returnstr(self.matrix)

    defsolved(self):
        returnsum([sum(row) for row in self.matrix]) == 0defmove(self, i, j):
        for k inrange(self.dim):
            self.matrix[i][k] = (self.matrix[i][k] + 1) % 2
            self.matrix[k][j] = (self.matrix[k][j] + 1) % 2
        self.matrix[i][j] = (self.matrix[i][j] + 1) % 2return self

    defcopy(self):
        return deepcopy(self)

    defsolve(self):
        q = PriorityQueue()
        v = set()

        q.put((0, self))
        whileTrue:
            c = q.get()

            if c[1].solved():
                return c[0]
            else:
                for i inrange(self.dim):
                    for j inrange(self.dim):
                        el = c[1].move(i, j) # do the move
                        t = el.tuple()

                        if t notin v:
                           v.add(t)
                           q.put((c[0] + 1, el.copy())) # copy only as needed

                        c[1].move(i, j) # undo the movedeftuple(self):
         returntuple(tuple(r) for r in self.matrix)

print Puzzle([
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]).solve()