Python – Use NumPy to speed up nested loops

I’m trying to solve a dynamic programming problem and I came up with a simple loop-based algorithm that fills a two-dimensional array based on a series of if statements like this:

s = # some string of size n
opt = numpy.zeros(shape=(n, n))

for j in range(0, n):
    for i in range(j, -1, -1):
        if j - i == 0:
            opt[i, j] = 1
        elif j - i == 1:
            opt[i, j] = 2 if s[i] == s[j] else 1
        elif s[i] == s[j] and opt[i + 1, j - 1] == (j - 1) - (i + 1) + 1:
            opt[i, j] = 2 + opt[i + 1, j - 1]
        else:
            opt[i, j] = max(opt[i + 1, j], opt[i, j - 1], opt[i + 1, j - 1])

Unfortunately, this code is very slow for large N values. I’ve found it much better to use built-in functions like numpy.where and numpy.fill> to fill the values of arrays instead of for loops, but I’m struggling to find any examples of how to make these functions (or other optimized numpy methods) work with a series of if statements, just like my algorithm does. What is a suitable way to rewrite the above code with the built-in numpy library to make it better optimized for Python?

I don’t think np.where and np.fill will solve your problem. np.where is used to return the elements of a numpy array that satisfies a specific condition, but in your case, the condition is a numpy array of not on values, but not a value from the variables i and j.

For your specific problem, I recommend using Cython to optimize your code specifically for larger N values. Cython is basically an interface between Python and C. The advantage of Cython is that it allows you to keep the python syntax, but optimize it using C structures. It allows you to define variable types in a C-like manner to speed up calculations. For example, using Cython to define i and j as integers speeds things up greatly because the types of i and j are checked at each loop iteration.

In addition, Cython will allow you to define classic, fast two-dimensional arrays using C. You can then use pointers to quickly access the elements of this two-dimensional array instead of using numpy arrays. In your case, OPT will be a two-dimensional array.