Efficient algorithm for matrix calculation

Question

In addition to this efficient algorithm for list edits I'm looking for a more efficient algorithmus for another "loop calculation". This time I have a matrix like:

grid_z1 = [[1,2,3],
           [4,5,6],
           [7,8,9]]

and the user can enter several parameters: goal is, to change the values inside the matrix into the parameter-value which is the next highest (and if a matrix-value is higher than max(paramter) than change it to nan) for example, when the user entered a "4" and a "7", then the matrix-value "5" shall change to "7" (=next highest of the entered values). example:

h = [2, 7, 4] # user entered this three values
grid_z1 = [[2, 2, 4],
           [4, 7, 7],
           [7, nan, nan]] # this should be my output

In addition I want to count the number of values which changed into the given values. in my example this should be [2,2,3] -> 2x2, 2x4, 3x7

h.sort()
h.reverse()

count = [0]*len(h)

for i in range(len(grid_z1)):
    for j in range(len(grid_z1[0])):
        if grid_z1[i][j] > max(h):
            grid_z1[i][j] = float('NaN')
        else:
            for k in range(len(h)-1):
                if grid_z1[i][j] <= h[k] and grid_z1[i][j] > h[k+1]:
                    grid_z1[i][j] = h[k]
                    count[k] += 1
            if grid_z1[i][j] <= min(h):
                grid_z1[i][j] = min(h)
                count[-1] += 1

print grid_z1
print count

But again it's very slow. Sadly I don't understand the zip-method enough to use it for this more complex algorithmus.

you should have a look at NumPy

Saullo G. P. Castro
– Saullo G. P. Castro

2013-11-23 11:41:10 +00:00
Commented Nov 23, 2013 at 11:41 — Saullo G. P. Castro
– Saullo G. P. Castro, Commented Nov 23, 2013 at 11:41

Ashwini Chaudhary · Accepted Answer · 2013-11-23 11:46:00Z

2

Using bisect module:

from bisect import bisect_left
def solve(matrix, param):
    param.sort()             #Sort the params passed by user
    maxx = param[-1]         #Find max
    for row in matrix:
        # If item in the row is greater than `maxx` then use Nan
        # else use bisect_right to get the next highest item from
        # params in O(log N) time.
        yield [float('nan') if item > maxx else
                                 param[bisect_left(param, item)] for item in row]

grid_z1 = [[1,2,3],
           [4,5,6],
           [7,8,9]]
print list(solve(grid_z1, [2, 7, 4]))

Output:

[[2, 2, 4], [4, 7, 7], [7, nan, nan]]

answered Nov 23, 2013 at 11:46

Ashwini Chaudhary

252k60 gold badges478 silver badges519 bronze badges

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

Comments

Jordonias · Accepted Answer · 2013-11-23 12:23:00Z

0

for i,row in enumerate(g):
        g[i] = [float('nan') if item > max(h) else min([x for x in h if x >= item]) for item in row]

answered Nov 23, 2013 at 12:23

Jordonias

5,8982 gold badges23 silver badges32 bronze badges

Collectives™ on Stack Overflow

Efficient algorithm for matrix calculation

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related