Is there a way to speed up this list comprehension?

user_14145185 0
Viewed 134

I've implemented "Langtons Loops" using Python/Pygame, and the larger the array of "Cells", the slower my program runs. Basic profiling shows that this line is taking up the most time:

matchSet = [r for r in ruleSet if r[:5] == buff]

Code Context:

surrBuff = []

surrBuff.append(str(self.dispBuff[y][x]) + str(self.dispBuff[y-1][x]) + 
                    str(self.dispBuff[y][x+1]) + str(self.dispBuff[y+1][x]) + 
                    str(self.dispBuff[y][x-1]))
surrBuff.append(str(self.dispBuff[y][x]) + str(self.dispBuff[y][x+1]) + 
                    str(self.dispBuff[y+1][x]) + str(self.dispBuff[y][x-1]) + 
                    str(self.dispBuff[y-1][x]))
surrBuff.append(str(self.dispBuff[y][x]) + str(self.dispBuff[y+1][x]) + 
                    str(self.dispBuff[y][x-1]) + str(self.dispBuff[y-1][x]) + 
                    str(self.dispBuff[y][x+1]))
surrBuff.append(str(self.dispBuff[y][x]) + str(self.dispBuff[y][x-1]) + 
                    str(self.dispBuff[y-1][x]) + str(self.dispBuff[y][x+1]) + 
                    str(self.dispBuff[y+1][x]))`

matchSet = []
for buff in surrBuff:
    #matchSet = [r for r in ruleSet if r.startswith(buff)]
    matchSet = [r for r in ruleSet if r[:5] == buff]

    if len(matchSet) > 0:
        break

ruleSet is an array of rules - 105 in total.
surrBuff is the set of surrounding cells of the current cell.

The idea is to find a matching rule in the ruleSet given the current cell value and the possible combinations of surrounding cells.

Max array size is about 40 * 50 cells and I notice slowdown once the display array hits about 20*50 cells.

Is there a better way to find the matching rule given the setup I've described or is this just a limitation of what I'm trying to do here?

Profiling:

ncalls          tottime  percall  cumtime  percall filename:lineno(function)

  1    0.000    0.000   47.707   47.707 <string>:1(<module>)
2072040/465    2.531    0.000    5.054    0.011 copy.py:128(deepcopy)
  2046000    0.288    0.000    0.288    0.000 copy.py:182(_deepcopy_atomic)
26040/465    0.928    0.000    5.051    0.011 copy.py:200(_deepcopy_list)
    26040    0.021    0.000    0.030    0.000 copy.py:242(_keep_alive)
        1    0.063    0.063   47.707   47.707 langLoops2.py:100(mainLoop)
   509601    6.273    0.000   37.883    0.000 langLoops2.py:36(calcNewCellValue)
   835660   29.295    0.000   29.295    0.000 langLoops2.py:59(<listcomp>)
      465    0.338    0.001   38.222    0.082 langLoops2.py:85(updateCalcBuff)
      464    0.377    0.001    0.876    0.002 langLoops2.py:93(draw)
'''
pygame python
2 Answers

You don't actually need the entire list if you only want to know if there is at least one match.

    for buff in surrBuff:  
        if any(r[:5] == buff for r in ruleSet):
            break

any will return as soon as it finds an element you would have added to the list.

user_11268410

If you always compare to the first five elements of the rules, it might make sense to create a dictionary from those rules and then look up the matching rules from that dictionary.

# create rule dict (just once, not within the loop)
ruleDict = collections.defaultdict(list)
for r in ruleSet:
    ruleDict[r[:5]].append(r)

...

    # get matchSet from dictionary
    matchSet = ruleDict[buff]

Also, unrelated to this, there is quite a bit of deepcopying going on in your profile output. It is generally considerably faster to create your own specialized copy logic, e.g. list(map(list, original)) for a list of lists, than using deepcopy.

user_16396250
Related