Как я могу рассчитать формулу повторения, включая минимизацию с NumPy?

Question

Я хочу рассчитать формулу повторения, подробности которой приведены ниже, включая минимизацию с использованием numpy Кроме того, я не хочу использовать ссылку numpy, если смогу из-за времени расчета.

Вот формула повторения, которую я хочу вычислить: (DTW) (*)

g[i,j] = d[i,j] + min(g[i-1,j],g[i-1,j-1],g[i-1,j-2])

Я пытался вычислить (*) с помощью «для цикла», тогда время расчета составляет около 2 минут! несмотря на g.shape = (2000, 2000) ... Код как ниже:

indexes = [[-1,0],[-1,-1],[-1,-2]] # for genelize

for i in range(1, g_rows):
    for j in range(g_cols):
        tmp = np.zeros(len(indexes))
        for k in range(len(indexes)):
            i_ = i + indexes[k][0]
            j_ = j + indexes[k][1]
            if i_ >= 0 and i_ < g_rows and j_ >= 0 and j_ < g_cols:
                tmp[k] = d[i,j] + g[i_,j_]
            else:
                tmp[k] = np.nan 

        g[i,j] = np.nanmin(tmp)

        for ~ # back tracking for DTW 

Поэтому я хотел бы сделать быстрее, чем приведенный выше код. Я думаю, что этот код слишком избыточен ...

Если это простая формула повторения:

a[i,j] = u[i+1,j] - u[i,j] + u[i,j+1] - u[i,j]

А затем с помощью среза (a):

a =  u[1:,0:-1] - u[0:-1,0:-1] + u[0:-1,1:] -u[0:-1,0:-1]

Я бы хотел вычислить (*) как (a). Есть ли какие-то решения?

Answer 1

Похоже, что это по сути итеративный алгоритм, так что вы, вероятно, не можете сделать все это как один вектор операции. Но поскольку каждый элемент в каждом столбце вычисляется независимо, вы могли бы сделать это намного быстрее, векторизовав вычисления для каждой строки:

g = np.zeros(d.shape) 
g[0, :] = d[0, :]
for i in range(1, d.shape[0]):
    g[i, 0] = d[i, 0] + g[i-1, 0]  # Edge condition for column 0
    g[i, 1] = d[i, 1] + np.minimum(g[i-1, 0], g[i-1, 1])  # Edge condition for column 1
    g[i, 2:] = d[i, 2:] + np.minimum.reduce([g[i-1,2:], g[i-1,1:-1], g[i-1,:-2]])  # Do remaining columns in single operation

Я не тестировал этот код, но считаю, что он должен делать то, что нужно.