Эффективное выполнение диффузии на 2d карте в Python

Question

Я довольно новичок в Python, поэтому я делаю проект в нем.Часть этого включает в себя распространение по карте.Я реализую это, пройдя и сделав текущий тайл равным .2 * сумме его соседей n, w, s, e.Если бы я делал это в C, я бы просто сделал двойной цикл for, который перебирает массив, делая arr [i * width + j] = arr из j + 1, j-1, i + i, i-1соседей) и имеют несколько разных массивов, для которых я бы делал одно и то же (разные качества карты я бы изменял).Тем не менее, я не уверен, что это действительно самый быстрый способ в Python.Некоторые люди, которых я спрашивал, предлагают что-то вроде numPy, но ширина, вероятно, не будет превышать ~ 200 (максимум 40-50k элементов), и я не был уверен, стоит ли это накладных расходов.Я действительно не знаю встроенных функций, чтобы делать то, что я хочу.Любой совет?

edit: Это будет очень плотно, т. Е. Каждое место будет иметь нетривиальный расчет

Answer 1

Это довольно просто организовать с NumPy .Функция np.roll возвращает копию массива, «свернутого» в указанном направлении.

Например, учитывая массив x,

x=np.arange(9).reshape(3,3)
# array([[0, 1, 2],
#        [3, 4, 5],
#        [6, 7, 8]])

, вы можете свернуть столбцы вправо с помощью

np.roll(x,shift=1,axis=1)
# array([[2, 0, 1],
#        [5, 3, 4],
#        [8, 6, 7]])

Используя np.roll, границы будутзавернутый как на торе.Если вам не нужны обернутые границы, вы можете заполнить массив ребром нулей и обнулять ребро перед каждой итерацией.

import numpy as np

def diffusion(arr):
    while True:
        arr+=0.2*np.roll(arr,shift=1,axis=1) # right
        arr+=0.2*np.roll(arr,shift=-1,axis=1) # left
        arr+=0.2*np.roll(arr,shift=1,axis=0) # down
        arr+=0.2*np.roll(arr,shift=-1,axis=0) # up
        yield arr

N=5
initial=np.random.random((N,N))
for state in diffusion(initial):
    print(state)
    raw_input()

Answer 2

Используйте свертку.

from numpy import *
from scipy.signal import convolve2d

mapArr=array(map)
kernel=array([[0  , 0.2,   0],
              [0.2,   0, 0.2],
              [0  , 0.2,   0]])
diffused=convolve2d(mapArr,kernel,boundary='wrap')

Это для муравьев?Если так, то в контексте муравьев в моей реализации convolve2d работал в ~ 20 раз быстрее, чем цикл.

Answer 3

Эта модификация кода unutbu поддерживает постоянную глобальную сумму массива, в то время как его значения рассеиваются:

        import numpy as np

        def diffuse(arr, d):
            contrib = (arr * d)
            w = contrib / 8.0
            r = arr - contrib
            N = np.roll(w, shift=-1, axis=0)
            S = np.roll(w, shift=1, axis=0)
            E = np.roll(w, shift=1, axis=1)
            W = np.roll(w, shift=-1, axis=1)
            NW = np.roll(N, shift=-1, axis=1)
            NE = np.roll(N, shift=1, axis=1)
            SW = np.roll(S, shift=-1, axis=1)
            SE = np.roll(S, shift=1, axis=1)
            diffused = r + N + S + E + W + NW + NE + SW + SE
            return diffused