Return to Answer

Python doesn't cache the tuple hash

Source Link

edited Nov 7, 2013 at 22:31

Gareth Rees

edited Nov 7, 2013 at 22:31

Gareth Rees

50.1k
3
130
210

Use the more understandable name Position instead of Desk.
Write docstrings for the class and its methods.
Represent the matrix as a single tuple instead of a list-of-lists. This means that a cell can be fetched in a single lookup instead of two lookups.
Remove the get_element method (just look up cells directly, saving a method call) and remove the set_element method (it's not needed now that the class is immutable).
Represent the blank item as 15 rather than 0, to avoid the special case in heuristic_cost.
Remember where the blank element is, so that neighbours can be generated without having to search the matrix to find the blank.
Generate the neighbours instead of returning them as a list.
Speed up the __hash__ by using tuple.__hash__ (which is cached internally by Python) instead of carrying out an expensive conversion to a string each time we want to compute the hash.
Rename swap and shuffle to swapped and shuffled since they now return new objects instead of modifying the old object in place.
Pass the number of swaps as a parameter to the shuffled method.
Avoid calling self.neighbors twice in the shuffle method, by using random.choice.
Use divmod instead of separately computing / and %.
Divide the heuristic cost by 2 (because one swap changes the sum of distances by 2).

Use the more understandable name Position instead of Desk.
Write docstrings for the class and its methods.
Represent the matrix as a single tuple instead of a list-of-lists. This means that a cell can be fetched in a single lookup instead of two lookups.
Remove the get_element method (just look up cells directly, saving a method call) and remove the set_element method (it's not needed now that the class is immutable).
Represent the blank item as 15 rather than 0, to avoid the special case in heuristic_cost.
Remember where the blank element is, so that neighbours can be generated without having to search the matrix to find the blank.
Generate the neighbours instead of returning them as a list.
Speed up the __hash__ by using tuple.__hash__ (which is cached internally by Python) instead of carrying out an expensive conversion to a string each time we want to compute the hash.
Rename swap and shuffle to swapped and shuffled since they now return new objects instead of modifying the old object in place.
Pass the number of swaps as a parameter to the shuffled method.
Avoid calling self.neighbors twice in the shuffle method, by using random.choice.
Use divmod instead of separately computing / and %.
Divide the heuristic cost by 2 (because one swap changes the sum of distances by 2).

Use the more understandable name Position instead of Desk.
Write docstrings for the class and its methods.
Represent the matrix as a single tuple instead of a list-of-lists. This means that a cell can be fetched in a single lookup instead of two lookups.
Remove the get_element method (just look up cells directly, saving a method call) and remove the set_element method (it's not needed now that the class is immutable).
Represent the blank item as 15 rather than 0, to avoid the special case in heuristic_cost.
Remember where the blank element is, so that neighbours can be generated without having to search the matrix to find the blank.
Generate the neighbours instead of returning them as a list.
Speed up the __hash__ by using tuple.__hash__ instead of carrying out an expensive conversion to a string each time we want to compute the hash.
Rename swap and shuffle to swapped and shuffled since they now return new objects instead of modifying the old object in place.
Pass the number of swaps as a parameter to the shuffled method.
Avoid calling self.neighbors twice in the shuffle method, by using random.choice.
Use divmod instead of separately computing / and %.
Divide the heuristic cost by 2 (because one swap changes the sum of distances by 2).

added 184 characters in body

Source Link

edited Oct 30, 2013 at 22:51

Gareth Rees

edited Oct 30, 2013 at 22:51

Gareth Rees

50.1k
3
130
210

Use the more understandable name Position instead of Desk.
Write docstrings for the class and its methods.
Represent the matrix as a single tuple instead of a list-of-lists. This means that a cell can be fetched in a single lookup instead of two lookups.
Remove the get_element method (just look up cells directly, saving a method call) and remove the set_element method (it's not needed now that the class is immutable).
Represent the blank item as 15 rather than 0, to avoid the special case in heuristic_cost.
Remember where the blank element is, so that neighbours can be generated without having to search the matrix to find the blank.
Generate the neighbours instead of returning them as a list.
Speed up the __hash__ by using tuple.__hash__ (which is cached internally by Python) instead of carrying out an expensive conversion to a string each time we want to compute the hash.
Rename swap and shuffle to swapped and shuffled since they now return new objects instead of modifying the old object in place.
Pass the number of swaps as a parameter to the shuffled method.
Avoid calling self.neighbors twice in the shuffle method, by using random.choice.
Use divmod instead of separately computing / and %.
Divide the heuristic cost by 2 (because one swap changes the sum of distances by 2).

class Position(object):
 """A position in the 15 puzzle (or a variant thereof)."""
 def __init__(self, width, height, matrix=None, blank=None):
 assert(width > 1 and height > 1)
 self.width = width
 self.height = height
 self.cells = width * height
 if matrix is None:
 matrix = tuple(range(self.cells))
 blank = self.cells - 1
 assert(len(matrix) == self.cells)
 assert(0 <= blank < self.cells)
 self.matrix = matrix
 self.blank = blank
 def __repr__(self):
 return 'Position({0.width}, {0.height}, {0.matrix}, {0.blank})'.format(self)
 def __eq__(self, other):
 return self.matrix == other.matrix
 def __ne__(self, other):
 return self.matrix != other.matrix
 def __hash__(self):
 return hash(self.matrix)
 def shuffled(self, swaps=20):
 """Return a new position after making 'swaps' swaps."""
 result = self
 for _ in range(swaps):
 result = random.choice(list(result.neighbors()))
 return result
 def heuristic_cost(self):
 """Return an admissible estimate of the number of swaps needed to
 solve the puzzle from this position.
 """
 total = 0
 for m, n in enumerate(self.matrix[:self.cells]matrix):
 mx, my = divmod(m, self.width)
 nx, ny = divmod(n, self.width)
 total += abs(mx - nx) + abs(my - ny)
 return total // 2
 def swapped(self, c):
 """Return a new position with cell 'c' swapped with the blank."""
 assert(c != self.blank)
 i, j = sorted([c, self.blank])
 return Position(self.width, self.height,
 self.matrix[:i] + (self.matrix[j],)
 + self.matrix[i+1:j] + (self.matrix[i],)
 + self.matrix[j+1:], c)
 def neighbors(self):
 """Generate the neighbors to this position, namely the positions
 reachable from this position via a single swap.
 """
 zy, zx = divmod(self.blank, self.width)
 if zx > 0:
 yield self.swapped(self.blank - 1)
 if zx < self.width - 1:
 yield self.swapped(self.blank + 1)
 if zy > 0:
 yield self.swapped(self.blank - self.width)
 if zy < self.height - 1:
 yield self.swapped(self.blank + self.width)

(We also have to make a couple of minor changes to Puzzle15 and puzzle15_time for this to work, but it should be clear how to do thatwhat's required.)

But we can do better than this. Python's min function still has to look at every element in the open set, taking O(n) time if there are n elements in the open set. If we kept a copy of the open set in a heap data structure, then we'd be able to find the minimum element in O(log n).

That's(Note that there's no persistent data here, so there's no need to make this function into a class.)

That yields another factor of two×ばつ speedup or so:

I've managed to make your code about 700 times faster (on this particular set of 20-shuffle test cases), but you'll find that if you shuffle the start position many times, the search often still does not complete in a reasonable amount of time.

This change turns A* into a form of best-first search.

Use the more understandable name Position instead of Desk.
Write docstrings for the class and its methods.
Represent the matrix as a single tuple instead of a list-of-lists. This means that a cell can be fetched in a single lookup instead of two lookups.
Remove the get_element method (just look up cells directly, saving a method call) and remove the set_element method (it's not needed now that the class is immutable).
Represent the blank item as 15 rather than 0, to avoid the special case in heuristic_cost.
Remember where the blank element is, so that neighbours can be generated without having to search the matrix to find the blank.
Generate the neighbours instead of returning them as a list.
Speed up the __hash__ by using tuple.__hash__ (which is cached internally by Python) instead of carrying out an expensive conversion to a string each time we want to compute the hash.
Rename swap and shuffle to swapped and shuffled since they now return new objects instead of modifying the old object in place.
Pass the number of swaps as a parameter to the shuffled method.
Avoid calling self.neighbors twice in the shuffle method, by using random.choice.
Use divmod instead of separately computing / and %.

class Position(object):
 """A position in the 15 puzzle (or a variant thereof)."""
 def __init__(self, width, height, matrix=None, blank=None):
 assert(width > 1 and height > 1)
 self.width = width
 self.height = height
 self.cells = width * height
 if matrix is None:
 matrix = tuple(range(self.cells))
 blank = self.cells - 1
 assert(len(matrix) == self.cells)
 assert(0 <= blank < self.cells)
 self.matrix = matrix
 self.blank = blank
 def __repr__(self):
 return 'Position({0.width}, {0.height}, {0.matrix}, {0.blank})'.format(self)
 def __eq__(self, other):
 return self.matrix == other.matrix
 def __ne__(self, other):
 return self.matrix != other.matrix
 def __hash__(self):
 return hash(self.matrix)
 def shuffled(self, swaps=20):
 """Return a new position after making 'swaps' swaps."""
 result = self
 for _ in range(swaps):
 result = random.choice(list(result.neighbors()))
 return result
 def heuristic_cost(self):
 """Return an admissible estimate of the number of swaps needed to
 solve the puzzle from this position.
 """
 total = 0
 for m, n in enumerate(self.matrix[:self.cells]):
 mx, my = divmod(m, self.width)
 nx, ny = divmod(n, self.width)
 total += abs(mx - nx) + abs(my - ny)
 return total
 def swapped(self, c):
 """Return a new position with cell 'c' swapped with the blank."""
 assert(c != self.blank)
 i, j = sorted([c, self.blank])
 return Position(self.width, self.height,
 self.matrix[:i] + (self.matrix[j],)
 + self.matrix[i+1:j] + (self.matrix[i],)
 + self.matrix[j+1:], c)
 def neighbors(self):
 """Generate the neighbors to this position, namely the positions
 reachable from this position via a single swap.
 """
 zy, zx = divmod(self.blank, self.width)
 if zx > 0:
 yield self.swapped(self.blank - 1)
 if zx < self.width - 1:
 yield self.swapped(self.blank + 1)
 if zy > 0:
 yield self.swapped(self.blank - self.width)
 if zy < self.height - 1:
 yield self.swapped(self.blank + self.width)

(We also have to make a couple of minor changes to Puzzle15 for this to work, but it should be clear how to do that.)

That's another factor of two or so:

I've managed to make your code about 700 times faster (on this set of 20-shuffle test cases), but you'll find that if you shuffle the start position many times, the search often still does not complete in a reasonable amount of time.

This turns A* into a form of best-first search.

Use the more understandable name Position instead of Desk.
Write docstrings for the class and its methods.
Represent the matrix as a single tuple instead of a list-of-lists. This means that a cell can be fetched in a single lookup instead of two lookups.
Remove the get_element method (just look up cells directly, saving a method call) and remove the set_element method (it's not needed now that the class is immutable).
Represent the blank item as 15 rather than 0, to avoid the special case in heuristic_cost.
Remember where the blank element is, so that neighbours can be generated without having to search the matrix to find the blank.
Generate the neighbours instead of returning them as a list.
Speed up the __hash__ by using tuple.__hash__ (which is cached internally by Python) instead of carrying out an expensive conversion to a string each time we want to compute the hash.
Rename swap and shuffle to swapped and shuffled since they now return new objects instead of modifying the old object in place.
Pass the number of swaps as a parameter to the shuffled method.
Avoid calling self.neighbors twice in the shuffle method, by using random.choice.
Use divmod instead of separately computing / and %.
Divide the heuristic cost by 2 (because one swap changes the sum of distances by 2).

class Position(object):
 """A position in the 15 puzzle (or a variant thereof)."""
 def __init__(self, width, height, matrix=None, blank=None):
 assert(width > 1 and height > 1)
 self.width = width
 self.height = height
 self.cells = width * height
 if matrix is None:
 matrix = tuple(range(self.cells))
 blank = self.cells - 1
 assert(len(matrix) == self.cells)
 assert(0 <= blank < self.cells)
 self.matrix = matrix
 self.blank = blank
 def __repr__(self):
 return 'Position({0.width}, {0.height}, {0.matrix})'.format(self)
 def __eq__(self, other):
 return self.matrix == other.matrix
 def __ne__(self, other):
 return self.matrix != other.matrix
 def __hash__(self):
 return hash(self.matrix)
 def shuffled(self, swaps=20):
 """Return a new position after making 'swaps' swaps."""
 result = self
 for _ in range(swaps):
 result = random.choice(list(result.neighbors()))
 return result
 def heuristic_cost(self):
 """Return an admissible estimate of the number of swaps needed to
 solve the puzzle from this position.
 """
 total = 0
 for m, n in enumerate(self.matrix):
 mx, my = divmod(m, self.width)
 nx, ny = divmod(n, self.width)
 total += abs(mx - nx) + abs(my - ny)
 return total // 2
 def swapped(self, c):
 """Return a new position with cell 'c' swapped with the blank."""
 assert(c != self.blank)
 i, j = sorted([c, self.blank])
 return Position(self.width, self.height,
 self.matrix[:i] + (self.matrix[j],)
 + self.matrix[i+1:j] + (self.matrix[i],)
 + self.matrix[j+1:], c)
 def neighbors(self):
 """Generate the neighbors to this position, namely the positions
 reachable from this position via a single swap.
 """
 zy, zx = divmod(self.blank, self.width)
 if zx > 0:
 yield self.swapped(self.blank - 1)
 if zx < self.width - 1:
 yield self.swapped(self.blank + 1)
 if zy > 0:
 yield self.swapped(self.blank - self.width)
 if zy < self.height - 1:
 yield self.swapped(self.blank + self.width)

(We also have to make a couple of minor changes to Puzzle15 and puzzle15_time for this to work, but it should be clear what's required.)

Python's min function still has to look at every element in the open set, taking O(n) time if there are n elements in the open set. If we kept a copy of the open set in a heap data structure, then we'd be able to find the minimum element in O(log n).

(Note that there's no persistent data here, so there's no need to make this function into a class.)

That yields another ×ばつ speedup or so:

This change turns A* into a form of best-first search.

Source Link

answered Oct 30, 2013 at 22:27

Gareth Rees

answered Oct 30, 2013 at 22:27

Gareth Rees

50.1k
3
130
210

1. You can't fix what you can't measure

In order to improve the performance of your code, we need to be able to measure its performance, and that's hard to do, because your Puzzle15 class randomly shuffles the Desk associated with each instance, so it is not easy to set up and carry out a systematic test.

Let's fix that, by changing Puzzle15.__init__ so that it takes a Desk instance of our choosing:

def __init__(self, desk):
 self.desk = desk
 self.steps = 0

Now we can create some test cases:

def puzzle15_test_cases(n, width=4, height=4):
 """Generate 'n' pseudo-random (but repeatable) test cases."""
 random.seed(1252481602)
 for _ in range(n):
 desk = Desk(width, height)
 desk.shuffle()
 yield desk
TEST_CASES = list(puzzle15_test_cases(100))

And a function that times the solution of all the cases, using the timeit module:

from timeit import timeit
def puzzle15_time():
 """Return the time taken to solve the puzzles in the TEST_CASES list."""
 return timeit('[Puzzle15(desk).get_solution() for desk in TEST_CASES]',
 'from __main__ import TEST_CASES, Puzzle15; gc.enable()',
 number = 1)

(See here for an explanation of gc.enable().) It takes more than three minutes on my machine to solve all 100 test cases:

>>> puzzle15_time()
184.2024281024933

2. Use sets for fast lookup

The first obvious time sink is the open and closed sets. You implement these using lists, but Python's list does not have an efficient membership test: to implement neighbor in closed_set Python has to scan all the way along the list, comparing neighbor with each item in turn until it finds one that matches. By using set objects instead, we get a constant-time membership test. So change:

closed_set = []
openset = [start]

to:

closed_set = set()
openset = set([start])

and use the set.add() method instead of list.append(). This change gives us an immediate 28% speedup:

>>> puzzle15_time()
132.80268001556396

3. Use the power of the dictionary

The next obvious problem is lowest_score_element. You have a double loop:

for elem in openset:
 if (elem in score.keys()):

So for each position in openset, you construct a fresh list containing the keys of the dictionary score, and then you look up the position in the list (which, as explained above, might require comparing the position to every item in the list). You could just write:

for elem in openset:
 if elem in score:

so that the membership test uses the fast dictionary lookup.

But you don't even need to do this, because Python already has a function min for finding the smallest element in a collection. So I would implement the method like this:

def lowest_score_element(self, openset, score):
 return min(openset, key=score.get)

And that yields a very dramatic improvement:

>>> puzzle15_time()
3.443160057067871

4. Make positions immutable

Instances of the Desk class represent positions in the 15 puzzle. You need to look up these positions in sets and dictionaries, and that means they need to be hashable. But if you read the documentation for the special __hash__ method, you'll see that it says:

If a class defines mutable objects and implements a __cmp__() or __eq__() method, it should not implement __hash__(), since hashable collection implementations require that a object’s hash value is immutable (if the object’s hash value changes, it will be in the wrong hash bucket).

Your Desk objects are currently mutable — they can be changed by the swap and set_element and shuffle methods. This makes them unsuitable for storing in sets or using as dictionary keys. So let's make them immutable instead. And at the same time, make the following improvements:

Use the more understandable name Position instead of Desk.
Write docstrings for the class and its methods.
Represent the matrix as a single tuple instead of a list-of-lists. This means that a cell can be fetched in a single lookup instead of two lookups.
Remove the get_element method (just look up cells directly, saving a method call) and remove the set_element method (it's not needed now that the class is immutable).
Represent the blank item as 15 rather than 0, to avoid the special case in heuristic_cost.
Remember where the blank element is, so that neighbours can be generated without having to search the matrix to find the blank.
Generate the neighbours instead of returning them as a list.
Speed up the __hash__ by using tuple.__hash__ (which is cached internally by Python) instead of carrying out an expensive conversion to a string each time we want to compute the hash.
Rename swap and shuffle to swapped and shuffled since they now return new objects instead of modifying the old object in place.
Pass the number of swaps as a parameter to the shuffled method.
Avoid calling self.neighbors twice in the shuffle method, by using random.choice.
Use divmod instead of separately computing / and %.

That results in the following code:

class Position(object):
 """A position in the 15 puzzle (or a variant thereof)."""
 def __init__(self, width, height, matrix=None, blank=None):
 assert(width > 1 and height > 1)
 self.width = width
 self.height = height
 self.cells = width * height
 if matrix is None:
 matrix = tuple(range(self.cells))
 blank = self.cells - 1
 assert(len(matrix) == self.cells)
 assert(0 <= blank < self.cells)
 self.matrix = matrix
 self.blank = blank
 def __repr__(self):
 return 'Position({0.width}, {0.height}, {0.matrix}, {0.blank})'.format(self)
 def __eq__(self, other):
 return self.matrix == other.matrix
 def __ne__(self, other):
 return self.matrix != other.matrix
 def __hash__(self):
 return hash(self.matrix)
 def shuffled(self, swaps=20):
 """Return a new position after making 'swaps' swaps."""
 result = self
 for _ in range(swaps):
 result = random.choice(list(result.neighbors()))
 return result
 def heuristic_cost(self):
 """Return an admissible estimate of the number of swaps needed to
 solve the puzzle from this position.
 """
 total = 0
 for m, n in enumerate(self.matrix[:self.cells]):
 mx, my = divmod(m, self.width)
 nx, ny = divmod(n, self.width)
 total += abs(mx - nx) + abs(my - ny)
 return total
 def swapped(self, c):
 """Return a new position with cell 'c' swapped with the blank."""
 assert(c != self.blank)
 i, j = sorted([c, self.blank])
 return Position(self.width, self.height,
 self.matrix[:i] + (self.matrix[j],)
 + self.matrix[i+1:j] + (self.matrix[i],)
 + self.matrix[j+1:], c)
 def neighbors(self):
 """Generate the neighbors to this position, namely the positions
 reachable from this position via a single swap.
 """
 zy, zx = divmod(self.blank, self.width)
 if zx > 0:
 yield self.swapped(self.blank - 1)
 if zx < self.width - 1:
 yield self.swapped(self.blank + 1)
 if zy > 0:
 yield self.swapped(self.blank - self.width)
 if zy < self.height - 1:
 yield self.swapped(self.blank + self.width)

(We also have to make a couple of minor changes to Puzzle15 for this to work, but it should be clear how to do that.)

This yields another ×ばつ speedup:

>>> puzzle15_time()
0.42876315116882324

5. Find the minimum using a heap

Python's built-in heapq module provides a way to do this, and moreover, by storing the f-score, g-score and parent position in the heap, we can get rid of the dictionaries in which you currently store these values.

This answer is getting rather long, so I'll just give you the revised code and you can figure out how it works for yourself!

import heapq
class NotFoundError(Exception): pass
def puzzle15_solve(start):
 goal = Position(start.width, start.height)
 closed_set = set()
 # Heap items are lists [F-score, G-score, position, parent data]
 start_data = [start.heuristic_cost(), 0, start, None]
 # open_set and open_heap always contain the same positions.
 # open_set maps each position to the corresponding heap item.
 open_set = {start: start_data}
 open_heap = [start_data]
 while open_heap:
 current_data = heapq.heappop(open_heap)
 f_current, g_current, current, parent_data = current_data
 if current == goal:
 def path(data):
 while data:
 yield data[2]
 data = data[3]
 return list(path(current_data))[::-1]
 del open_set[current]
 closed_set.add(current)
 for neighbor in current.neighbors():
 if neighbor in closed_set:
 continue
 g_neighbor = g_current + 1
 f_neighbor = g_neighbor + neighbor.heuristic_cost()
 neighbor_data = [f_neighbor, g_neighbor, neighbor, current_data]
 if neighbor not in open_set:
 open_set[neighbor] = neighbor_data
 heapq.heappush(open_heap, neighbor_data)
 else:
 old_neighbor_data = open_set[neighbor]
 if neighbor_data < old_neighbor_data:
 old_neighbor_data[:] = neighbor_data
 heapq.heapify(open_heap)
 raise NotFoundError("No solution for {}".format(start))

That's another factor of two or so:

>>> puzzle15_time()
0.2613048553466797

6. A different algorithm

This is due to a combination of (i) the size of the search space (10,461,394,944,000 positions); and (ii) the A* algorithm, which keeps searching until it has found the best (shortest) solution.

But if you don't care about getting the best solution, but are willing to accept any solution, then you could change the algorithm to ignore the g-score. Replace:

f_neighbor = g_neighbor + neighbor.heuristic_cost()

with:

f_neighbor = neighbor.heuristic_cost()

and now you can solve arbitrarily shuffled positions in a couple of seconds:

>>> timeit(lambda:puzzle15_solve(Position(4, 4).shuffled(1000)), number=1)
2.0673770904541016

This turns A* into a form of best-first search.

lang-py