I am working on state space search (8 Puzzle) in Python and when I run my program with python3 -m profile
, I find out that most of time program performs a few functions. I would like to optimize functions bellow (if it's possible).
I am using dictionary node
, whose structure is:
{
'id': string, # Unique ID of node, e. g. '123456708'.
'state': array, # Numpy array 3x3 with unique numbers 1-8 and 0, e. g. [[1 2 3] [4 5 6] [7 0 8]].
'pos': tuple, # Current position of 0 in node's state, e. g. (2, 1).
}
swap
Function accepts 2D array
, pos1
and pos2
and returns new array with swapped elements on positions.
# [1 2 3] [0 2 3]
# [4 5 6] -> swap((2, 1), (0, 0)) -> [4 5 6]
# [7 0 8] [7 1 8]
def swap(array, pos1, pos2):
result = numpy.copy(array)
result[pos1], result[pos2] = result[pos2], result[pos1]
return result
create
Function that accepts state
and pos
of 0
in state and returns node with this state.
def create(state, pos):
return { 'id': hash(state.tostring()), 'state': state, 'pos': pos }
move
Function, that accepts node
and vector change
and returns new node with changed state. New state is created when 0
in state is moved by vector (changeY, changeX) change
. If new state has invalid index, return None
instead.
# [1 2 3] [1 2 3]
# [4 5 6] -> move(-1, 0) -> [4 0 6]
# [7 0 8] [7 5 8]
def move(node, change):
newPos = (node['pos'][0] + change[0], node['pos'][1] + change[1]) # numpy.add(node['pos'], change) is slower.
if 0 <= newPos[0] <= 2 and 0 <= newPos[1] <= 2: # Valid index
newState = swap(node['state'], node['pos'], newPos)
return create(newState, newPos)
return None # Invalid index.
getSuccessors
Function that accepts node
in state and returns all nodes which state is about -1 or 1 different vertically or horizontally (not both):
# [1 2 3] [1 2 3] [1 2 3] [1 2 3]
# [4 5 6] -> getSuccessors() -> [4 0 6] [4 5 6] [4 5 6]
# [7 0 8] [7 5 8] [0 7 8] [7 8 0]
def getSuccessors(node):
moves = [
move(node, (-1, 0)),
move(node, (1, 0)),
move(node, (0, -1)),
move(node, (0, 1)),
]
return list(filter(lambda node: node is not None, moves))
findPath
Function accepts numpy 3x3 arrays init
and goal
and search successors of init
until one of successors will be goal
.
def findPath(init, goal):
explored = {} # Already explored nodes.
pos = numpy.where(init == 0)
unexplored = [create(init, (pos[0][0], pos[1][0]))] # Unexplored nodes.
while True:
if not unexplored: # If there is no node to explore, puzzle has no solution.
return None
node = unexplored.pop(0) # Bfs algorithm is slow, but for testing purposes.
if numpy.array_equal(node['state'], goal):
return 'Success' # Should be path, but for now is not important.
explored[node['id']] = node
for successor in getSuccessors(node): # Add successors to unexplored nodes.
if successor['id'] not in explored:
unexplored.append(successor)
When I run this program python3 puzzle.py
, it takes 13.36 seconds:
import time
import numpy
start = time.time()
init = numpy.array([[7, 2, 4], [5, 0, 6], [8, 3, 1]])
goal = numpy.array([[1, 3, 0], [5, 2, 6], [4, 7, 8]])
print(findPath(init, goal)) # 'Success'
end = time.time()
print(end - start) # 13.36 s
With python3 -m profile puzzle.py | grep "puzzle.py"
:
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 52.771 52.771 profile:0(<code object <module> at 0x7fa52c125300, file "puzzle.py", line 1>)
1 0.131 0.131 52.752 52.752 puzzle.py:1(<module>)
1638628 6.305 0.000 25.991 0.000 puzzle.py:12(move)
409657 4.410 0.000 31.730 0.000 puzzle.py:21(getSuccessors)
1638628 1.330 0.000 1.330 0.000 puzzle.py:29(<lambda>)
1 3.066 3.066 52.195 52.195 puzzle.py:31(findPath)
1106988 3.519 0.000 14.525 0.000 puzzle.py:4(swap)
1106989 3.049 0.000 5.161 0.000 puzzle.py:9(create)
Most of the time was move
executed (6.3 s), then getSuccessors
(4.4 s), swap
, findPath
and create
. Is there any way to optimize these functions? Here is the whole program (even slower than on my PC).