Nsryjdtyk

I have this python code using numpy:

import numpy as np

table = np.array([[23, 54, 12], 

                 [17, 32, 25],

                 [43, 19, 11],

                 [31, 22, 10],

                 [21, 19, 35]])

r, c = table.shape

out = np.zeros((r,c)) 

out[0, :] = np.cumsum(table[0,:])

out[:, 0] = np.cumsum(table[:,0]) 



for j in range(1, c):

    for i in range(1, r):

        out[i,j] = max( out[i-1,j], out[i,j-1] ) + table[i,j]



out[-1,-1]

I first calculate the 1st row and the 1st column of the array 'out', while the rest of the values are calculated with the equation inside the for loops. I am interested only on the last value of the table ( out[-1,-1] ) and I want to make it as fast as possible. Could I remove the two 'for' loops somehow??

This is in effect finding the longest path from each coordinate to 0,0, where the cost is given by the table for each node on the path. The standard 'matrix way' to deal with such problem is Floy-Warshall algoritm, which makes n matrix multiplications, where n is the number of nodes, in your case r*c. Your algorithm is actually already optimized variant of Floyd-Warshall that uses the fact that every path that goes from (i,j) to (0,0) must pass either (i-1,j) or (i,j-1).

This is already a huge optimization!

I don't think there is a way to deal with this without an iteration over all the coordinates.

But maybe you could use some graph library to encode it as a graph problem, which would push the iteration part into the (efficient) graph library.

EVEN BETTER:

You could iterate over diagonals, using fill_diagonal for instance. This way ou would iterate only over the number of diagonals.

I'm not entirely sure what you're trying to accomplish.

You're making a new out array that copies the first(0th) row and column from the original table. (By the way, at out[:, 0] = np.cumsum(table[:,0]), you overwrite the element at [0, 0]).

You then proceed to filling the rest of the out array by taking the the maximum of either the element in the row before or that of the column before.

You're then adding the contents of the original array table at that spot to the maximum.

Since you're looking for previous rows and columns in the out array, you'll often find yourself in a situation where you've overwritten those values before you check them.
For instance, when you're at i=2, j=1, you've got the array

[[ 23.  77.  89.]

 [ 40. 109.   0.]

 [ 83.  *?*   0.]

 [114.   0.   0.]

 [135.   0.   0.]]

You're at the *?* and checking for 109 and 83. And you've just inserted 109 in the previous iteration.

Thus, you are unable to get the same result without the use of those for loops.