How to improve time complexity without using two For loops in numpy array, optimize the structure?

Question

I have some results drew from a class defined previously. It could be assembled into a 2D (10,10) numpy matrix P, com is another corresponding 2D matrix.

I wish to improve the time complexity of this part of code, like using other ways instead of two for loops. Or some improvement could be made on the rest part of the code thus have better time complexity.

The point is P matrix will always be a symmetrical one, and r_nm also need to be symmetrical. So I guess something could be improved with math method in this part. Or using methods like vectorization to simplify the procedure.

Based on the value of element in P matrix, I need to select top tier1 elements for the r_nmmatrix, set the corresponding position in r_nm to r1 value.

Then select from tier+1 to top tier2, set the corresponding position in r_nm to r2 value.

The last step, set the rest of the position to r3 value. And tier 1 need to overwrite the value if it is set to r2 value or r3 previously. The same, r2 need to overwrite r3. And r_nm[:,case+gl-2:case+gl],r_nm[case+gl-2:case+gl,:] need to be set as zero.

Is there any advice on that?

Thanks in advance!!

import numpy as np

tier1 = 9
tier2 = 20
Gzone = 5
Lzone = 10
case = 5
gl = 5
r1 = 0     #Active
r2 = 20    #LessActive
r3 = 1000  #Rare

r_nm = np.zeros([case+gl,case+gl],dtype = np.int) 
p = np.zeros([case+gl,case+gl])

for k,i in enumerate(p):
    for y,j in enumerate(i):        
        for t in poolmarket.data.interval:
            p[k][y] = p[k][y] + com[k][y] * abs(poolmarket.variables.P_nm3[t,k,y].x)

p_save += p    
p[0:Gzone,0:Gzone ]=-np.inf
p[Gzone:Lzone,Gzone:Lzone ]= -np.inf

b = np.argpartition(p, -tier1)[:, -tier1:]              
d = np.argpartition(p, -tier2)[:, -tier2:]              

r_nm = np.ones([case+gl,case+gl],dtype = np.int) * r3     

r_nm[np.arange(r_nm.shape[0])[:,None],d] = r2    
r_nm[d,np.arange(r_nm.shape[0])[:,None]] = r2

r_nm[np.arange(r_nm.shape[0])[:,None],b] = r1
r_nm[b,np.arange(r_nm.shape[0])[:,None]] = r1

r_nm[:,case+gl-2:case+gl] =0
r_nm[case+gl-2:case+gl,:] =0

In numpy you gain most speed by doing the loops in compiled methods. Python level iteration is slow. Trying to take advantage of symmetry requires extra indexing work which can slow things down. — hpaulj
– hpaulj, Commented May 15, 2020 at 17:44
@hpaulj Thanks a lot! But I'm not so familiar with compiled methods. I go for some search, do you mean by doing loops via packages like Cython? — 赵天阳
– 赵天阳, Commented May 15, 2020 at 18:06
What I mean is use the whole-array methods that numpy provides. — hpaulj
– hpaulj, Commented May 15, 2020 at 18:10

pyOliv · Accepted Answer · 2020-05-15 19:35:17Z

1

Just a simple example to show the difference between manual iteration and builtin functions:

import numpy as np
import timeit

p = np.random.rand(1000)
q = np.random.rand(1000)

def manual_iterate(p, q):
    r = np.empty((1000,1000))
    for i in range(0, 1000):
        for j in range(0, 1000):
            r[i][j] = p[i] + 2*q[j]
    return r

def built_in_function(p, q):
    return p+2*q

print('manual iterate:')
%timeit manual_iterate(p, q)

print('built in iterate:')
%timeit built_in_function(p, q)

output:

manual iterate:
1.77 s ± 15.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
built in iterate:
9.39 µs ± 75.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

so you should write something like:

abs_val = abs(poolmarket.variables.P_nm3.x)
p = p + com * abs_val

answered May 15, 2020 at 19:35

pyOliv

1,3232 gold badges8 silver badges21 bronze badges

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

Collectives™ on Stack Overflow

How to improve time complexity without using two For loops in numpy array, optimize the structure?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related