Есть ли способ ускорить понимание этого списка?

ProgramBox

Есть ли способ ускорить понимание этого списка?

Post author:admin
Запись опубликована:13 апреля, 2023
Post category:Вопросы по программированию

#python #pygame

Вопрос:

Я реализовал «Циклы Langtons», используя Python / Pygame, и чем больше массив «Ячеек», тем медленнее выполняется моя программа. Базовое профилирование показывает, что эта строка занимает больше всего времени:

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

Контекст кода:

 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 это массив правил — всего 105.
surrBuff это набор окружающих ячеек текущей ячейки.

Идея состоит в том, чтобы найти соответствующее правило в ruleSet с учетом текущего значения ячейки и возможных комбинаций окружающих ячеек.

Максимальный размер массива составляет около 40 * 50 ячеек, и я замечаю замедление, как только отображаемый массив достигает примерно 20 * 50 ячеек.

Есть ли лучший способ найти соответствующее правило с учетом описанной мной настройки или это просто ограничение того, что я пытаюсь здесь сделать?

Профилирование:

 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)
'''

1. каков тип данных buff ?

2. Я не знаком с алгоритмом, который вы реализуете, но, как правило, вы обнаружите, что numpy предоставит многомерные массивы с нулевым копированием, которые, вероятно, будут более производительными, чем встроенные списки — я не могу сказать из вашего профиля здесь и кода, являются ли вызовы copy результатом правил или просто вашим выводом для понимания списка

3. да, numpy это значительно ускорит ваш код. Вероятно, ~ 100x

4. Если тип данных buff не покрывается numpy, он может быть покрыт Cython, который увеличится где-то между 5 и 1000x: cython.readthedocs.io/en/latest/src/quickstart/cythonize.html

5. Небольшой комментарий к коду. Вам не обязательно этого делать if len(matchSet) > 0: «правдивость» коллекции определяется тем, есть ли в ней что-либо (возвращается пустая коллекция False ). Итак, вы можете просто использовать if matchSet: . Если вы запустите pylint в своем коде, он порекомендует это.

Ответ №1:

Если вы всегда проводите сравнение с первыми пятью элементами правил, возможно, имеет смысл создать словарь на основе этих правил, а затем посмотреть соответствующие правила из этого словаря.

 # 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]

Также, не имея отношения к этому, в выходных данных вашего профиля происходит довольно много глубокого копирования. Обычно значительно быстрее создать свою собственную специализированную логику копирования, например, list(map(list, original)) для списка списков, чем использовать deepcopy .

1. Да, я использую deepcopy, потому что у меня есть 2 буфера. Один для отображения текущих значений и один для вычисления следующих отображаемых значений. Я копирую буфер calc в буфер отображения, используя deepcopy self.updateCalcBuff() ——> обновить следующее состояние, используя текущее отображение self.dispBuff = deepcopy(self.calcBuff) ————> скопировать на дисплей для вывода

2. @granth1974 Отвечая на ваш комментарий под другим ответом: Да, это была опечатка, так и должно было быть ruleDict[r[:5]].append(r) . Исправлено.

Ответ №2:

На самом деле вам не нужен весь список, если вы только хотите знать, есть ли хотя бы одно совпадение.

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

any вернется, как только найдет элемент, который вы бы добавили в список.

1. Проблема в том, что мне нужно найти и вернуть правило сопоставления, потому что формат правил — «cnnnnx», где c — текущая ячейка, n — соседние ячейки, а x — новое значение для установки текущей ячейки в

2. @granth1974 Вы могли бы использовать next((r for ...), None) для получения только первого правила сопоставления (но использование dict все равно было бы быстрее)

3. @tobias_k — использование словаря для хранения фрагментов, похоже, улучшило производительность. Я не смог использовать ruleDict [r: 5].append (r) напрямую, поскольку я получил ошибку «фрагмент не хэшируется», но просто использовал for r in ruleSet: s = r[:5] self.ruleDict[s].append(r)