How to improve performance of this code?

Question

Thanks to some help from people here, I was able to get my code for Tasmanian camels puzzle working. However, it is horribly slow (I think. I'm not sure because this is my first program in Python). The example run in the bottom of the code takes a long time to be solved in my machine:

dumrat@dumrat:~/programming/python$ time python camels.py
[['F', 'F', 'F', 'G', 'B', 'B', 'B'], ['F', 'F', 'G', 'F', 'B', 'B', 'B'],
 ['F', 'F', 'B', 'F', 'G', 'B', 'B'], ['F', 'F', 'B', 'F', 'B', 'G', 'B'],
 ['F', 'F', 'B', 'G', 'B', 'F', 'B'], ['F', 'G', 'B', 'F', 'B', 'F', 'B'],
 ['G', 'F', 'B', 'F', 'B', 'F', 'B'], ['B', 'F', 'G', 'F', 'B', 'F', 'B'],
 ['B', 'F', 'B', 'F', 'G', 'F', 'B'], ['B', 'F', 'B', 'F', 'B', 'F', 'G'],
 ['B', 'F', 'B', 'F', 'B', 'G', 'F'], ['B', 'F', 'B', 'G', 'B', 'F', 'F'],
 ['B', 'G', 'B', 'F', 'B', 'F', 'F'], ['B', 'B', 'G', 'F', 'B', 'F', 'F'],
 ['B', 'B', 'B', 'F', 'G', 'F', 'F']]

real    0m20.883s
user    0m20.549s
sys    0m0.020s

Here's the code:

import Queue

fCamel = 'F'
bCamel = 'B'
gap = 'G'

def solution(formation):
    return len([i for i in formation[formation.index(fCamel) + 1:]
                if i == bCamel]) == 0

def heuristic(formation):
    fCamels, score = 0, 0
    for i in formation:
        if i == fCamel:
            fCamels += 1;
        elif i == bCamel:
            score += fCamels;
        else:
            pass
    return score

def getneighbors (formation):
    igap = formation.index(gap)
    res = []
    # AB_CD --> A_BCD | ABC_D | B_ACD | ABD_C
    def genn(i,j):
        temp = list(formation)
        temp[i], temp[j] = temp[j], temp[i]
        res.append(temp)

    if(igap > 0):
        genn(igap, igap-1)
    if(igap > 1):
        genn(igap, igap-2)
    if igap < len(formation) - 1:
        genn(igap, igap+1)
    if igap < len(formation) - 2:
        genn(igap, igap+2)

    return res

class node:
    def __init__(self, a, g, p):
        self.arrangement = a
        self.g = g
        self.parent = p

def astar (formation, heuristicf, solutionf, genneighbors):

    openlist = Queue.PriorityQueue()
    openlist.put((heuristicf(formation), node(formation, 0, None)))
    closedlist = []

    while 1:
        try:
            f, current = openlist.get()
        except IndexError:
            current = None

        if current is None:
            print "No solution found"
            return None;

        if solutionf(current.arrangement):
            path = []
            cp = current
            while cp != None:
                path.append(cp.arrangement)
                cp = cp.parent
            path.reverse()
            return path

        #arr = current.arrangement
        closedlist.append(current)
        neighbors = genneighbors(current.arrangement)

        for neighbor in neighbors:
            if neighbor in closedlist:
                pass
            else:
                openlist.put((current.g + heuristicf(neighbor),
                             node(neighbor, current.g + 1, current)))

        #sorted(openlist, cmp = lambda x, y : x.f > y.f)

def solve(formation):
    return astar(formation, heuristic, solution, getneighbors)

print solve([fCamel, fCamel, fCamel, gap, bCamel, bCamel, bCamel])
#print solve([fCamel, fCamel, fCamel, fCamel, gap, bCamel, bCamel, bCamel, bCamel])

That is just for 3 camels each. I wanted to do this for 4 at least. That test case is still running (It's been about 5 minutes now :(). I'll update this if and when it finishes.

What should I do to improve this code? (Mostly performance-wise, but any other suggestions are welcome also).

Answer 1

First let me tell you how to find the problem. Then I'll tell you where it is:

I haven't even bothered to try to figure out your code. I just ran it and took 3 random-time stack samples. I did that by typing control-C and looking at the resulting stacktrace.

One way to look at it is: if a statement appears on X% of random stack traces, then it is on the stack for about X% of the time, so that is what it's responsible for. If you could avoid executing it, that is how much you would save.

OK, I took 3 stack samples. Here they are:

File "camels.py", line 87, in <module>
  print solve([fCamel, fCamel, fCamel, gap, bCamel, bCamel, bCamel])
File "camels.py", line 85, in solve
  return astar(formation, heuristic, solution, getneighbors)
File "camels.py", line 80, in astar
  openlist.put((current.g + heuristicf(neighbor), node(neighbor, current.g + 1, current)))

File "camels.py", line 87, in <module>
  print solve([fCamel, fCamel, fCamel, gap, bCamel, bCamel, bCamel])
File "camels.py", line 85, in solve
  return astar(formation, heuristic, solution, getneighbors)
File "camels.py", line 80, in astar
  openlist.put((current.g + heuristicf(neighbor), node(neighbor, current.g + 1, current)))

File "camels.py", line 87, in <module>
  print solve([fCamel, fCamel, fCamel, gap, bCamel, bCamel, bCamel])
File "camels.py", line 85, in solve
  return astar(formation, heuristic, solution, getneighbors)
File "camels.py", line 80, in astar
  openlist.put((current.g + heuristicf(neighbor), node(neighbor, current.g + 1, current)))

Notice, in this case the stack samples are all identical. In other words, each one of these three lines is individually responsible for nearly all of the time. So look at them:

line        87: print solve([fCamel, fCamel, fCamel, gap, bCamel, bCamel, bCamel])
line solve: 85: return astar(formation, heuristic, solution, getneighbors)
line astar: 80: openlist.put((current.g + heuristicf(neighbor), node(neighbor, current.g + 1, current)))

Clearly line 87 is not one you can avoid executing, and probably not 85 either. That leaves 80, the openlist.put call. Now, you can't tell if the problem is in the + operator, the heuristicf call, the node call, or in the put call. You could find out if you could split those out onto separate lines.

So I hope you pick up from this a quick and easy way to find out where your performance problems are.