以快速方式從矩陣中刪除列C++

假設我們有存儲在打包表單中的矩陣A (m*n)（大小爲m*n的一維數組 - 帶有前導維 - 列）。我需要縮小矩陣A(S) - 這是從A刪除1列或更多列的結果。我可以很容易地在循環中手工處理，但還有另外一種方法 - 使用選擇矩陣I(S)，它們是除去1個或多個列的恆等矩陣（全0或對角線1）。然後，例如，如果我需要從A中刪除第三排，我需要形成I(3) - 身份沒有第三欄，然後是A(3)=A*I(S)。由於我需要A的許多變體，我需要刪除不同列的所有不同的身份矩陣I(S)。以快速方式從矩陣中刪除列C++

我在想這種方式，因爲我使用了英特爾數學核心庫 - 這對於矩陣乘法非常有效。

所以，問題是你怎麼想形成新的矩陣A(S)的最快方法：用手，用A直接工作或先形成I(S) - 而問題是如何迅速形成這些矩陣 - 再乘以A*I(S)或你可以提出任何其他快速解決方案

爲了說明假設我們有基質A：

它存儲在陣列A=[1,4,7,2,5,8,3,6,9]. Suppose I need to form A（2）`即去除第二列。我需要輸出：

這是存儲在C + + A_S=[1,4,7,3,6,9]。這可以直接在矩陣A上完成，這將花費O(n^2)時間並且對於大矩陣不是有效的。或者，我們可以形成I(2)：

保存在C++作爲I_S = [1,0,0,0,1,0]。然後A(2) = A*I(2)

來源

2013-04-23 Oleg Shirokikh

你真的需要一個特定的數據類型矩陣的結果（或其他需要修改的矩陣）？因爲否則我看來，像最有效的方式做到這一點，可以寫'matrix_view'類，它的作用就像一個正常的矩陣，但在修改爲了省去列訪問索引，因爲這將釋放你真正執行復制。 – Grizzly 2013-04-23 17:35:29

我想你應該小心使用I如果你的意思是identity matrix。 Identity matrix通常是方形矩陣，而您使用的矩陣通常不是方矩陣，因爲您從原始矩陣中刪除了列。讓我把這個變換矩陣叫做T，而不是I。

現在我想回答你的問題：

的問題是如何迅速形成這些矩陣

因此基於以上假設，T(2)應該是：

1 0 
0 0 
0 1

自

1 2 3  1 0  1 3 
4 5 6 * 0 0 = 4 6 
7 8 9  0 1  7 9

根據您要刪除第二列的情況，您可以比較T(2)與原始I(3)（這裏是身份矩陣）。

 1 0 0 
I(3) 0 1 0 
     0 0 1

自從你知道要刪除的列，你就知道你用來存儲I(3)，在這種情況下，一維數組的索引範圍，它是：A_I(3) = [1 0 0 0 1 0 0 0 1];你知道，指數[3,5]是第二列，您只需要刪除那些3倍的值，你會得到T(2)在上面的例子中，這是A_T(2) = [ 1 0 0 0 0 1]。所以我們的想法是，如果您知道要移除原始矩陣的哪一列，您只需從存儲原始列映射到的索引範圍內的單位矩陣的一維數組中移除值。在此示例中，您從[3,5]中刪除原始矩陣映射到的2nd列的值。

現在你可以使用你的矩陣庫繁殖A和A_T(2)並得到結果矩陣。

來源

2013-04-23 17:50:04 taocp

是的，你寫的所有內容都很清晰，我沒有理解問題背後的數學問題。問題是如何使用C++快速從'a = [1,0,0,0,0,1]'中取出一個數組'b = [1,4,7,3,6,9]'。 2個主要問題是：時間和空間的複雜性。我的目標矩陣與可能數十億元素 – 2013-04-23 19:00:12

@ user2028058的，如果你只需要刪除第2列時，得到B，我覺得你可以直接做在陣列上，因爲你知道第二列刪除，那麼你需要刪除索引值的條目在[3,5]中，在這種情況下是2,5,8。我猜你甚至不需要了。 – taocp 2013-04-23 19:03:12

這是明顯的蠻力方式..運行循環m * n次並將需要的元素複製到b。試想一下，這樣做m * n個操作的.. – 2013-04-23 19:19:57

以快速方式從矩陣中刪除列C++

回答

相關問題