Python (Numpy) array equal function is slow...is there a faster way?

Question

I'm a visual artist who is learning Python in order to create a specify set of artworks. In one, I'm coding Conway's classic Game of Life using a 2160x3840 grid.

However, the program is running slower than I'd hoped: It's been running on my three-year old iMac now for 24 hours and I only have two and a half "frames" processed. It will take weeks to make the run, and I have several runs to do.

I ran SnakeViz and 93% of my program's time is spent in a single function, where the primary activity is a series of comparisons. All of the "finch" colors and flashOfLifeColor are considered "live" cells in terms of Conway's rules.

def isLive (theColor):

    isCellLive = False
    finchColor_1 = numpy.array([247, 238, 214])
    finchColor_2 = numpy.array([202, 184, 88])
    finchColor_3 = numpy.array([103, 81, 68])
    flashOfLifeColor = numpy.array([249, 192, 0])

    if (numpy.array_equal(theColor, finchColor_1)) or
       (numpy.array_equal(theColor, finchColor_2)) or
       (numpy.array_equal(theColor,     finchColor_3)) or 
       (numpy.array_equal(theColor, flashOfLifeColor)):

        isCellLive = True

    return isCellLive

Is there a better (faster) way to write the if statement? Is there anything else I can do outside of optimization to speed things up?

Thanks,

--Darin

Edit:

Here is the function that is calling isLive to help understand what I am doing. I also want to mention again that I'm very new at Python programming, and do not yet know object programming at all, not any advanced techniques--thsu having a hard time deciphering some of the implementations of Conway's Rules that I am seeing on the web.

def countNeighborsNine(theArray, row, column):

    numberOfNeighbors = 0
    maxRow, maxColumn, depth = theArray.shape
    for rowModifier in range (-1,2):
        for columnModifier in range (-1, 2):

            rowNeighborPointer = (row + rowModifier) % maxRow
            columnNeighborPointer = (column + columnModifier) % maxColumn

            thePixel = theArray[rowNeighborPointer, columnNeighborPointer]

            if isLive(thePixel):
                numberOfNeighbors = numberOfNeighbors + 1

    return numberOfNeighbors

As soon as I posted this I see an obvious improvement--use the "dead" color instead of the live colors for the comparison. There are three dead colors--I still need significant improvement beyond that. — Darin Boville
– Darin Boville, Commented Feb 5, 2017 at 9:16
As far as I understood, you store the color of cell and then reconstruct is state from that color. Why you are doing that? Why not just store the state of the cell as some boolean or integer value and completely avoid this isLive function? — Ilya V. Schurov
– Ilya V. Schurov, Commented Feb 5, 2017 at 9:22
btw, you can try this implementations rosettacode.org/wiki/Conway%27s_Game_of_Life#Python — Ilya V. Schurov
– Ilya V. Schurov, Commented Feb 5, 2017 at 9:26
I presume you have some large 2160x3840 image, and you want to get a list of all live cells? And is theColor is always a 3-element array? — VBB
– VBB, Commented Feb 5, 2017 at 9:26
The fact that you're calling this function, presumably in a giant loop, means that this is running in Python time rather than numpy. Function calls are expensive, array creation (which you do every single time the function is called) is expensive and it will add up. It might be helpful to show a small snippet of the larger array and the way you are applying this function. Then someone might be able to help vectorize it. — roganjosh
– roganjosh, Commented Feb 5, 2017 at 9:31

VBB · Accepted Answer · 2017-02-05 10:06:13Z

2

Here's a possible solution. Your image colours are probably in the range of 0..255 for R,G, and B each. I would first convert that into a single unique "colour ID " for the entire image (easy to process).

cid = grid_r * 256 * 256 + grid_g * 256 + grid_b

Do the same for your live/dead list:

def get_id(a):
     return a[0] * 256 * 256 + a[1] * 256 + a[2]
live_colours = np.array([get_id(finchColor_1), get_id(finchColor_2), get_id(finchColor_3), get_id(flashOfLifeColor)])

Now you can get all the 'live' cells in a single command:

alive = np.in1d(cid, live_colours).reshape(cid.shape)

Here, alive will be a 2160x3840 array of True and False elements. np.in1d takes each element in cid and returns True if it is in live_colours. The returned array is 1-d, so you need to reshape it to the same shape as your original image.

Edit - now to use this to count number of live neighbours for each cell. First I define a 2-d roll function.

def shifter(x, a, b):
   return np.roll(np.roll(x, a, axis=0), b, axis=1)

I take the alive array and pad it with "dead" cells on all 4 sides:

width = 2160
height = 3840
biglive = np.zeros((width + 2, height + 2))
biglive[1:-1, 1:-1] = alive.astype(int)
live_count = shifter(biglive, -1, -1) + shifter(biglive, -1, 0) + shifter(biglive, -1, 1) + shifter(biglive, 0, -1) + shifter(biglive, 0, 1) + shifter(biglive, 1, -1) + shifter(biglive, 1, 0) + shifter(biglive, 1, 1)

We ignore the padded zero cells at the end.

live_count = live_count[1:-1, 1:-1]

This is a 2160x3840 grid, where each cell contains the number of live neighbours. I generated a random image, and the entire process took a couple of seconds to calculate the number of alive neighbours for the complete 2160x3840 set.

edited Feb 5, 2017 at 10:06

answered Feb 5, 2017 at 9:39

VBB

1,3357 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Darin Boville Over a year ago

Hi VBB, Thanks for the detailed answer. I semi-get where you are coming from reading through the code--tomorrow when I'm more clear-headed(!) I'll put it into the interpreter so I can really understand what is happening and why. Thanks again. Your code seem so much more compact than mine! :)

Paul Panzer Over a year ago

Nice solution. One quibble: the OP's neighbour code actually does wrap around, so you can do away with the padding. Also, but you'd have to check whether that's intentional, they seem to count the centre pixel as a neighbour.

VBB Over a year ago

Thanks @PaulPanzer. I assumed the no-wrap and 8-neighbours-only as per usual game of life rules.

Darin Boville Over a year ago

@VBB I won't be able to get back to this until later today. But I will check in and report success (or express further bewilderment). :) Thanks for all the excellent advice from you and all the others.

B. M. · Accepted Answer · 2017-02-05 13:59:58Z

1

Just some advise to find by yourself the best way.

Begin with a pure python project, then a numpy one.
Separate the game logic and visualization.

For exemple one array to distinguish alive/dead, an other to count neighbors. Use imshow(neighbours, cmap=my_conway_map) for visualization.
Never use for loops on numpy arrays, it's slow.

A minimal exemple :

world=randint(0,2,(5,5))
mask=ones((3,3))
mask[1,1]=0
neighb=scipy.signal.convolve2d(world,mask,'same')
subplot(121)
a=imshow(world,interpolation='none',cmap=cm.Greys)
subplot(122) 
colorbar()
b=imshow(neighb,interpolation='none')
show()

answered Feb 5, 2017 at 13:59

B. M.

18.7k2 gold badges40 silver badges56 bronze badges

Collectives™ on Stack Overflow

Python (Numpy) array equal function is slow...is there a faster way?

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related