Speed up for loop in numpy

Question

I am looking for accelerating this loop in numpy but I find no obvious pattern to do so:

for index1 in range(1, len_route):
        time_diff_matrix[index1, (index1+1):len_route] = \
            M[(index1-1):(len_route-2)] - \
            M[index1-1] + \
            N[index1-1, index1:(len_route-1)] + \
            N[index1, (index1+1):len_route] - \
            P[index1:(len_route-1)]

The rest of the time_diff_matrix is populated with zeros. It was a double-loop first. I got rid of one loop but I don't know how to get rid of the other loop. len_route is a large number.

Regards.

What's the typical value for len_route? Shape of M?

hpaulj
– hpaulj

2016-12-27 13:46:14 +00:00
Commented Dec 27, 2016 at 13:46 — hpaulj
– hpaulj, Commented Dec 27, 2016 at 13:46
can you provide a working minimal example ?

Moritz
– Moritz

2016-12-27 13:55:34 +00:00
Commented Dec 27, 2016 at 13:55 — Moritz
– Moritz, Commented Dec 27, 2016 at 13:55
len_route is between 300 and 1200.

daguix
– daguix

2016-12-27 21:53:01 +00:00
Commented Dec 27, 2016 at 21:53 — daguix
– daguix, Commented Dec 27, 2016 at 21:53
M is a 1-d array with length len_route-1

daguix
– daguix

2016-12-27 21:55:37 +00:00
Commented Dec 27, 2016 at 21:55 — daguix
– daguix, Commented Dec 27, 2016 at 21:55

Divakar · Accepted Answer · 2016-12-27 14:28:14Z

3

Here's an approach using slicing rows/columns -

n = len_route
vals = M[:n-2] - M[:n-2,None] + N[:n-2,1:n-1] + N[1:n-1,2:n] - P[1:n-1]
r,c = np.triu_indices(len_route-1,1)
time_diff_matrix[r+1,c+1] = vals[r,c-1]

Another approach to avoid using np.triu_indices and using np.triu instead -

time_diff_matrix[1:n-1,2:n] = np.triu(vals)

Verify results -

In [265]: # Setup inputs
     ...: S = 10
     ...: M = np.random.randint(11,99,(S))
     ...: N = np.random.randint(11,99,(S,S))
     ...: P = np.random.randint(11,99,(S))
     ...: time_diff_matrix = np.zeros((S,S), dtype=int)
     ...: len_route = N.shape[0]
     ...: 

In [266]: # Original approach
     ...: for index1 in range(1, len_route):
     ...:     time_diff_matrix[index1, (index1+1):len_route] = \
     ...:         M[(index1-1):(len_route-2)] - \
     ...:         M[index1-1] + \
     ...:         N[index1-1, index1:(len_route-1)] + \
     ...:         N[index1, (index1+1):len_route] - \
     ...:         P[index1:(len_route-1)]
     ...:     

In [267]: # Proposed approach
     ...: time_diff_matrix_out = np.zeros_like(time_diff_matrix)
     ...: n = len_route
     ...: vals = M[:n-2] - M[:n-2,None] + N[:n-2,1:n-1] + N[1:n-1,2:n] - P[1:n-1]
     ...: time_diff_matrix_out[1:n-1,2:n] = np.triu(vals)
     ...: 

In [268]: np.allclose(time_diff_matrix, time_diff_matrix_out)
Out[268]: True

edited Dec 27, 2016 at 14:28

answered Dec 27, 2016 at 14:23

Divakar

222k19 gold badges273 silver badges374 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

daguix Over a year ago

Thanks, it makes a 40% speed improvement. There are twice more calculations but the numpy optimisation overcomes this.

Divakar Over a year ago

@daguix Consider accepting it if this solved your problem?

Collectives™ on Stack Overflow

Speed up for loop in numpy

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related