How to improve performance of this code?

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.

I've been tripped up by this before too. The bottleneck here is actually if neighbor in closedlist.

The in statement is so easy to use, you forget that it's linear search, and when you're doing linear searches on lists, it can add up fast. What you can do is convert closedlist into a set object. This keeps hashes of its items so the in operator is much more efficient than for lists. However, lists aren't hashable items, so you will have to change your configurations into tuples instead of lists.

If the order of closedlist is crucial to the algorithm, you could use a set for the in operator and keep an parallel list around for your results.

I tried a simple implementation of this including aaronasterling's namedtuple trick and it performed in 0.2 sec for your first example and 2.1 sec for your second, but I haven't tried verifying the results for the second longer one.

tkerwin is correct that you should be using a set for closedlist, which speeds things up a lot, but it is still kind of slow for 4 camels on each side. The next problem is that you are allowing a lot of solutions that aren't possible because you are allowing fCamels to go backwards and bCamels to go forward. To fix this, replace the lines,

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)

with

if(igap > 0 and formation[igap-1] == fCamel):    genn(igap, igap-1)if(igap > 1 and formation[igap-2] == fCamel):    genn(igap, igap-2)if (igap < len(formation) - 1) and formation[igap+1] == bCamel:    genn(igap, igap+1)if (igap < len(formation) - 2) and formation[igap + 2] == bCamel:    genn(igap, igap+2)

then I get solution to the 4 camels on each side problem in like .05 seconds rather than 10 seconds. I also tried 5 camels on each side and it took 0.09 seconds. I also am using a set for closedlist and heapq rather than Queue.

Additional speed-up

You can get an additional speed-up by using your heuristic correctly. Currently, you are using the line

openlist.put((current.g + heuristicf(neighbor), node(neighbor, current.g + 1, current)))

(or the heapq version of that) but you should change it to

openlist.put((heuristicf(neighbor), node(neighbor, current.g + 1, current)))

This doesn't factor in the number of moves that has been needed, but that is okay. With this puzzle (and the screening out of moves that move camels in the wrong direction), you don't need to worry about the number of moves it takes - either a move advances you towards the solution or it will come to a dead end. In other words, all possible solutions require the same number of moves. This one change takes the time to find the solution of the 12 camels on each side case from over 13 seconds (even using the heapq, set for closedlist, and the changes to find the neighbors above) to 0.389 seconds. That's not bad.

By the way, a better way to find if you've found the solution is to check if the index of the first fCamel is equal to the length of the formation/2 + 1(using int division) and that the index before that is equal to the gap.