Python：分而治之遞歸矩陣乘法

我試圖實施分而治之矩陣乘法（8遞歸版本不是Strassen）。我想我已經想通了，但是它產生了太多嵌套列表和錯誤值的奇怪輸出。我懷疑問題是我如何總結8次遞歸，但林不知道。Python：分而治之遞歸矩陣乘法

def multiMatrix(x,y): 
    n = len(x) 
    if n == 1: 
     return x[0][0] * y[0][0] 
    else: 
     a = [[col for col in row[:len(row)/2]] for row in x[:len(x)/2]] 
     b = [[col for col in row[len(row)/2:]] for row in x[:len(x)/2]] 
     c = [[col for col in row[:len(row)/2]] for row in x[len(x)/2:]] 
     d = [[col for col in row[len(row)/2:]] for row in x[len(x)/2:]] 
     e = [[col for col in row[:len(row)/2]] for row in y[:len(y)/2]] 
     f = [[col for col in row[len(row)/2:]] for row in y[:len(y)/2]] 
     g = [[col for col in row[:len(row)/2]] for row in y[len(y)/2:]] 
     h = [[col for col in row[len(row)/2:]] for row in y[len(y)/2:]] 
     ae = multiMatrix(a,e) 
     bg = multiMatrix(b,g) 
     af = multiMatrix(a,f) 
     bh = multiMatrix(b,h) 
     ce = multiMatrix(c,e) 
     dg = multiMatrix(d,g) 
     cf = multiMatrix(c,f) 
     dh = multiMatrix(d,h) 

     c = [[ae+bg,af+bh],[ce+dg,cf+dh]] 

     return c 


a = [ 
    [1,2,3,4], 
    [5,6,7,8], 
    [9,10,11,12], 
    [13,14,15,16] 
    ] 
b = [ 
    [1,2,3,4], 
    [5,6,7,8], 
    [9,10,11,12], 
    [13,14,15,16] 
    ] 

print multiMatrix(a,b)

來源

2017-02-25 Solomon Bothwell

'x [0] [0] * y [0] [0]'不是矩陣。 – user2357112

考慮ae = bg = ... = [[1]]。然後c = [[[1] + [1]，[1] + [1]]，[[1] + [1]，[1] + [1]]] [[[1,1]，[ 1,1]]，[[1,1]，[1,1]]] - 而不是矩陣。 –

類似地，'ae + bg'不是矩陣加法，而'[[ae + bg，af + bh]，[ce + dg，cf + dh]]'不會構建塊的矩陣。 – user2357112

您的懷疑是正確的，您的矩陣仍然是列表，因此添加它們只會產生更長的列表。

嘗試使用這樣的事情

def matrix_add(a, b): 
    return [[ea+eb for ea, eb in zip(*rowpair)] for rowpair in zip(a, b)]

在你的代碼

。

要加入塊：

def join_horiz(a, b): 
    return [rowa + rowb for rowa, rowb in zip(a,b)] 

def join_vert(a, b): 
    return a+b

最後，爲了使大家共同努力，我認爲你必須改變你的特殊情況，1至

return [[x[0][0] * y[0][0]]]

編輯：剛剛

我意識到這隻適用於兩維度的權力。否則，你將不得不處理非方形矩陣，它會發生，x是1件事，你的特殊情況將無法正常工作。所以你還必須檢查len（x [0]）（如果n> 0）。

來源

2017-02-25 08:10:05

Python：分而治之遞歸矩陣乘法

回答

相關問題