矩陣計算的高效算法

Question

除此之外efficient algorithm for list edits我正在尋找另一種「循環計算」的更高效的算法。 這一次，我有這樣一個矩陣：

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

，用戶可以輸入幾個參數：目標是，改變矩陣內的值到參數值是下一個最高的（如果一個矩陣定例如，當用戶輸入「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]