How can I improve the efficiency of my algorithm, while I use two loops inside?

user_9044666 0
Viewed 54

Dear experienced friends, I proposed a method to solve an algorithm problem. However, I found my method becomes very time-consuming when the data size grows. May I ask is there any better way to solve this problem? Is it possible to use matrix manipulation?

The question:

  • Suppose we have 1 score-matrix and 3 value-matrix.
  • Each of them is a square matrix with the same size (N*N).
  • The element in score-matrix means the weights between two entities. For example, S12 means the score between entity 1 and entity 2. (Weights are only meaningful when greater than 0.)
  • The element in value-matrix means the values between two entities. For example, V12 means the value between entity 1 and entity 2. Since we have 3 value-matrix, we have 3 different V12.

The target is: I want to multiply the values with the corresponding weights, so that I can finally output a (Nx3) matrix.

My solutions: I solved this problem as follows. However, I use two for-loops here, which makes my program become very time-consuming. (e.g. When N is big or 3 becomes 100) May I ask is there any way to improve this code? Any suggestions or hints would be very appreciated. Thank you in advance!

# generate sample data
import numpy as np
score_mat = np.random.randint(low=0, high=4, size=(2,2))
value_mat = np.random.randn(3,2,2)

# solve problem
# init the output info
output = np.zeros((2, 3))

# update the output info
for entity_1 in range(2):

    # consider meaningful score
    entity_others_list = np.where(score_mat[entity_1,:]>0)[0].tolist()

    # iterate every other entity
    for entity_2 in entity_others_list:

        vec = value_mat[:,entity_1,entity_2].copy()

        vec *= score_mat[entity_1,entity_2]

        output[entity_1] += vec
python-3.x matrix numpy algorithm python
1 Answers

You don't need to iterate them manually, just multiply score_mat by value_mat, then call sum on axis=2, again call sum on axis=1.

As you have mentioned that the score will make sense only if it is greater than zero, if that's the case, you can first replace non-positive values by 1, since multiplying something by 1 remains intact:

>>> score_mat[score_mat<=0] = 1
>>> (score_mat*value_mat).sum(axis=2).sum(axis=1)
array([-0.58826032, -3.08093186, 10.47858256])

Break-down:

# This is what the randomly generated numpy arrays look like:
>>> score_mat
array([[3, 3],
       [1, 3]])
>>> value_mat
array([[[ 0.81935985,  0.92228075],
        [ 1.07754964, -2.29691059]],
       [[ 0.12355602, -0.36182607],
        [ 0.49918847, -0.95510339]],
       [[ 2.43514089,  1.17296263],
        [-0.81233976,  0.15553725]]])

# When you multiply the matcrices, each inner matrices in value_mat will be multiplied
# element-wise by score_mat
>>> score_mat*value_mat
array([[[ 2.45807955,  2.76684225],
        [ 1.07754964, -6.89073177]],
       [[ 0.37066806, -1.08547821],
        [ 0.49918847, -2.86531018]],
       [[ 7.30542266,  3.51888789],
        [-0.81233976,  0.46661176]]])

# Now calling sum on axis=2, will give the sum of each rows in the inner-most matrices
>>> (score_mat*value_mat).sum(axis=2)
array([[ 5.22492181, -5.81318213],
       [-0.71481015, -2.36612171],
       [10.82431055, -0.34572799]])

# Finally calling sum on axis=1, will again sum the row values
>>> (score_mat*value_mat).sum(axis=2).sum(axis=1)
array([-0.58826032, -3.08093186, 10.47858256])
user_91363480
Related