How to improve performance of this code?

by

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.

More Related Contents:

  1. How do I profile a Python script?
  2. Efficient way to take the minimum/maximum n values and indices from a matrix using NumPy
  3. Finding the most frequent character in a string
  4. First items in inner list efficiently as possible [duplicate]
  5. Looking for a fast way to find the polygon a point belongs to using Shapely
  6. Fastest way to list all primes below N
  7. Python Sets vs Lists
  8. What is the most efficient way of finding all the factors of a number in Python?
  9. Find common substring between two strings
  10. Performance of Pandas apply vs np.vectorize to create new column from existing columns
  11. Flatten an irregular list of lists
  12. Most efficient way of making an if-elif-elif-else statement when the else is done the most?
  13. How to load existing db file to memory in Python sqlite3?
  14. Python readlines() usage and efficient practice for reading
  15. Python decompression relative performance?
  16. Pandas pd.Series.isin performance with set versus array
  17. Efficiently detect sign-changes in python
  18. Performance Advantages to Iterators?
  19. Create random list of integers in Python
  20. numpy float: 10x slower than builtin in arithmetic operations?
  21. Fastest way to write huge data in file
  22. No speedup when summing uint16 vs uint64 arrays with NumPy?
  23. Why shouldn’t I use PyPy over CPython if PyPy is 6.3 times faster?
  24. Why is any (True for … if cond) much faster than any (cond for …)?
  25. Fast way to copy dictionary in Python
  26. What is the most efficient way to check if a value exists in a NumPy array?
  27. Is MATLAB faster than Python?
  28. Efficient dot products of large memory-mapped arrays
  29. Can I perform dynamic cumsum of rows in pandas?
  30. deque.popleft() and list.pop(0). Is there performance difference?

Leave a Comment