Finding surrounding tiles for all tiles

Question

What can I do to improve performance of this function? So far I've changed stuff as local as possible and made a break if all possible surrounding tiles have been found. Also I use a separate variable to track the length of a list instead of len().

The usage of this is to find surrounding tiles for all tiles.

def getsurroundings(tiles):
    for t in tiles:
        currentrect = Rect(t.rect[0] - t.rect[2] / 2, t.rect[1] - t.rect[3] / 2, t.rect[2] * 2, t.rect[3] * 2)
        check = currentrect.colliderect
        surroundings = t.surroundings
        append = t.surroundings.append
        surroundingscount = t.surroundingscount
        for t2 in tiles:
            if check(t2.rect) and not t == t2 and not t2 in surroundings:
                append(t2)
                t2.surroundings.append(t)
                surroundingscount+=1
                t2.surroundingscount+=1
            if surroundingscount == 8:
                break
    return tiles

Here's the code without localisations which might be easier to read:

def getsurroundings(tiles):
    for t in tiles:
        currentrect = Rect(t.rect[0] - t.rect[2] / 2, t.rect[1] - t.rect[3] / 2, t.rect[2] * 2, t.rect[3] * 2)
        for t2 in tiles:
            if currentrect.colliderect(t2.rect) and not t == t2 and not t2 in t.surroundings:
                t.surroundings.append(t2)
                t2.surroundings.append(t)
                t.surroundingscount+=1
                t2.surroundingscount+=1
            if t.surroundingscount == 8:
                break
    return tiles

Answer 1

I don't know exactly what you are doing, but it seems like something similar to Minesweeper counts for bombs surrounding a tile.

I would to do this by iterating through the tiles once, and increment their neighbour's count by one if they have some feature you're interested in (like a bomb) to get the result. That way you only need k * 8 iterations (minus the ones over the edges) with k being the number of tiles having the feature you're interested in. For a board of 8x8 having 28 bombs that would be 224 iterations, instead of the 4096 when using a n^2 algorithm.

With Numpy this is relatively easy to do. And about ten times faster.

Answer 2

The problem here isn't in the details of the code, but in the algorithm. For every tile, you check all tiles, so for n tiles, your code has to perform n^2 checks, which is a lot. The only way to significantly reduce the running time of your code, is to make the search smarter. If you can make your use case a bit more visual, we might be able to come up with something.

Answer 3

def getsurroundings(tiles):
    # skip the last rect in the outer loop, as it can't possibly have any subsequent neighbors
    for index, t in enumerate(tiles[:-2]):
        # if you've already found the maximum neighbors for t, skip the whole process
        if len(t.surroundings) < 8:
            currentrect = Rect(t.rect[0] - t.rect[2] / 2, t.rect[1] - t.rect[3] / 2, t.rect[2] * 2, t.rect[3] * 2)
            # only iterate over the part of the tile list that hasn't already been run through in the outer loop
            for t2 in tiles[index + 1:]:
                if currentrect.colliderect(t2.rect):
                    t.surroundings.append(t2)
                    t2.surroundings.append(t)
                if len(t.surroundings) == 8:
                    break

I could be wrong, but I seem to recall that slicing does a shallow copy, so you could conceivably get even better performance if you swap the loops to iterating over indeces instead of slices.

Assuming this is PyGame, and assuming (since your code says you can't have more then 8 neighbors) that rects are non-overlapping and can only have one other rect per side (such as on a chess board), here's a bit better solution, I think:

Tile(Rect):

    neighbors_map = ((('upper_center', 'mid_left'),
                      ('mid_left', 'upper_center')),
                     (('upper_left', 'mid_right'),
                      ('upper_right', 'mid_left'),
                      ('mid_left', 'upper_right'),
                      ('mid_right', 'upper_left')),
                     (('upper_center', 'mid_left'),
                      ('mid_right', 'upper_center')),
                     (('upper_left', 'lower_center'),
                      ('upper_center', 'lower_left'),
                      ('lower_left', 'upper_center'),
                      ('lower_center', 'upper_left')),
                     (('upper_center', 'lower_right'),
                      ('upper_right', 'lower_center'),
                      ('lower_center', 'upper_right'),
                      ('lower_right', 'upper_center')),
                     (('mid_left', 'lower_center'),
                      ('lower_center', 'mid_left')),
                     (('mid_left', 'lower_right'),
                      ('mid_right', 'lower_left'),
                      ('lower_left', 'mid_right'),
                      ('lower_right', 'mid_left')),
                     (('mid_right', 'lower_center'),
                      ('lower_center', 'mid_right')))

    def __init__(self, *args, **kwargs):
        self.clear_neighbors()
        Rect.__init__(self, *args, **kwargs)

    def clear_neighbors(self):
        self.neighbors = [None] * 8

    def __getattr__(self, name):
        try:
            index = self.resolve_name(name)
        except ValueError:
            raise AttributeError
        return self.neighbors(index)

    def __setattr__(self, name, value):
        try:
            super(Tile, self).__setattr__(name, value)
        except AttributeError:
            try:
                index = self.resolve_name(name)
            except ValueError:
                raise AttributeError
            if not self.neighbors[index]:
                self.neighbors[index] = value
                for neighbor_name, neighbor_neighbor_name in Tile.neighbors_map[index]:
                    neighbor = getattr(self, neighbor_name)
                    if neighbor:
                        setattr(neighbor, neighbor_neighbor_name, value)

    def resolve_name(self, name):
        parts = name.split('_')
        if parts[0] == 'upper':
            index = 0
        elif parts[0] == 'mid':
            if parts[1] == 'left':
                return 3
            elif parts[1] == 'right':
                return 4
            else:
                raise ValueError
        elif parts[0] == 'lower':
             index = 5
        else:
            raise ValueError
        if parts[1] == 'left':
            return index
        elif parts[1] == 'center':
            return index + 1
        elif parts[1] == 'right':
            return index + 2
        else:
            raise ValueError

Then:

def populate_neighbors(tile_list):
    tile_list_copy = copy.copy(tile_list)
    while tile_list_copy:
        current_tile = tile_list_copy.pop(0)
        if all current_tile.neighbors:
            continue
        full_tile_indeces = []
        for index, search_tile in enumerate(tile_list_copy):
            if all search_tile.neighbors:
                full_tile_indeces.append(index)
            else:
                if current_tile.right == search_tile.left + 1:
                    if current_tile.bottom == search_tile.top + 1:
                        current_tile.lower_right = search_tile
                    elif current_tile.top == search_tile.bottom - 1:
                        current_tile.upper_right = search_tile
                    elif (current_tile.top == search_tile.top
                          and current_tile.bottom == search_tile.bottom):
                        current_tile.mid_right = search_tile
                elif current_tile.left == search_tile.right - 1:
                    if current_tile.bottom == search_tile.top + 1:
                        current_tile.lower_left = search_tile
                    elif current_tile.top == search_tile.bottom - 1:
                        current_tile.upper_left = search_tile
                    elif (current_tile.top == search_tile.top
                          and current_tile.bottom == search_tile.bottom):
                        current_tile.mid_left = search_tile
                elif (current_tile.left == search_tile.left
                      and current_tile.right == search_tile.right):
                    if current_tile.bottom == search_tile.top + 1:
                        current_tile.lower_center = search_tile
                    elif current_tile.top == search_tile.bottom - 1:
                        current_tile.upper_center = search_tile
                for index in reversed(full_tile_indeces):
                    tile_list_copy.pop(index)

It would probably be a good idea to break the neighbor setting logic out of the Tile class, but that can be something to figure out. :)

Answer 4

What about this?
I added a second list, so you only iterate over combinations you didn't already check.

By the way, you should code with spaces, not with tabs.

def getsurroundings(tiles):
        tiles2 = tiles[:]
    for t in tiles:
        currentrect = Rect(t.rect[0] - t.rect[2] / 2, t.rect[1] - t.rect[3] / 2, t.rect[2] * 2, t.rect[3] * 2)
        check = currentrect.colliderect
        surroundings = t.surroundings
        append = t.surroundings.append
        surroundingscount = t.surroundingscount
        tiles2.pop(0)
        for t2 in tiles2:
            if check(t2.rect) and not t == t2 and not t2 in surroundings:
                append(t2)
                t2.surroundings.append(t)
                surroundingscount+=1
                t2.surroundingscount+=1
            if surroundingscount == 8:
                break
    return tiles