Эффективный алгоритм вычисления матрицы

Question

В дополнение к этому efficient algorithm for list edits Я ищу более эффективный алгоритм для другого «вычисления цикла». На этот раз у меня есть матрица типа:

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

и пользователь может ввести несколько параметров: Цель состоит в том, чтобы изменить значение внутри матрицы в параметре-значение, которое является следующим самым высоким (и если матричным значение больше, чем max (параметр), чем изменение его на nan), например, когда пользователь вводил «4» и «7», тогда значение матрицы «5» должно изменяться на «7» (= следующая самая высокая из введенные значения). пример:

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 

В дополнение я хочу, чтобы подсчитать количество значений, которые изменились в заданных значений. в моем примере это должно быть [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 

Но опять-таки это очень медленно. К сожалению, я не понимаю метод zip, чтобы использовать его для этого более сложного алгоритма.

Answer 1

Использование bisect модуля:

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])) 

Выход:

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

Answer 2

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]