Flood fill algorithm

I am implementing a flood fill algorithm using Python and NumPy. I have written the following fill function which works fine:

def fill(self, data, xsize, ysize, x_start, y_start):

    stack = [(x_start, y_start)]

    while stack:
        x, y, stack = stack[0][0], stack[0][1], stack[1:]

        if data[x, y] == 1:
            data[x, y] = 2
            if x > 0:
                stack.append((x - 1, y))
            if x  0:
                stack.append((x, y - 1))
            if y < (ysize - 1):
                stack.append((x, y + 1))

I wanted to implement a way that would eliminate the need to re-check a point if it had already been checked. By creating a new list of checked points and then comparing to see if the current point is already in that list, but this ended up making it slower and I wanted to understand if there is a more efficient way to improve upon my existing implementation.

Instead of using a list to store your points (which has an \$O(n)\$ look-up time), you can use a set object which has an \$O(1)\$ look-up time. For more information regarding Pythonic time complexity, you can look here.

I have a couple comments on your style:

• Instead of x and y, I would use column/col and row. Even though x and y are mathematical coordinate names, I still prefer to be more explicit.

-
Group declarations are OK in the right circumstances, like unpacking an iterator or defining groups of like variables. The way you do this doesn't quite fit into the 'right circumstances' category: you are assigning and then slicing.

To get a better implementation, there are a couple of options:

• Split the statement into its components (assigning x, y and slicing the list)

-
Calling list.pop() to do both at the same time

These two options, in terms of efficiency, are probably identical. So, its up to you to choose which one you want to use. Here is their syntax:

# 2 statements.
col, row = stack[0]
stack = stack[1:]

# Using `pop`.
col, row = stack.pop(0)

-
In Python 3, use the * operator to unpack the list

This option is the least applicable (due to your comments below). However, for reference here is that syntax:

(col, row), *stack = stack

This assigns the first element of the stack to (col, row) and the rest to itself, effectively popping off the first element.

P.S. Congratulations. This is probably my shortest review on this site.

StackExchange Code Review Q#54534, answer score: 2