包含許多零的矩陣的數據結構？

在C++中，我必須在RAM中保存一個非常大的矩形矩陣，它由大約90％（零的真實頻率取決於用戶輸入）組成。爲所有這些零分配內存將浪費內存。包含許多零的矩陣的數據結構？

如何製作一個使用小內存的類，並且便於將類似instance.getElement(row,column)的元素放入此大矩陣中？

2016-10-16 Remi.b

你正在尋找的術語是「稀疏矩陣」。有許多數據結構可供選擇。對於簡單的用例，從（行，列）到值的映射不是一個不好的表示。 –

當您使用[]訪問未知映射鍵時，您應該查看Armadillo C++庫及其稀疏矩陣類（http://arma.sourceforge.net/） – Snps

有很多方法可以去。但首先要考慮的是，在訪問元素變得更加複雜的情況下，你會因此獲得良好的性能。其次，你將無法使用像LAPACK這樣的着名的庫，因爲據我所知，它們沒有爲這種複雜的數據結構提供任何接口。所以，每次你想要做一些數學運算時，你都必須解壓縮矩陣並壓扁它，否則你將不得不重新開發那些做你想做的操作的代碼，這並不是一件容易的事情去做。做LAPACK的人多年來一直在研究。

我在說的是：在做這件事之前考慮後果。

現在提到後果後，我可以提到一種方法，我的頭頂。

想象你的矩陣是一個平面陣列，在column major（因此列在存儲器中的列之後）中排序，在內存中是連續的。
現在這個矩陣是一個有許多零的列表。你的問題是：我們如何消除這些零？

那麼有很多方式可以去，並且每個方法將具有取決於你的應用程序不同的計算複雜性，讓我提一些方法：

你可以使用一個linked list，其中每個元素可以是std::pair，包含當前矩陣元素的值以及下一個可用元素的索引。
您可以使用鏈接列表，並且可以使用某些壓縮軟件的工作方式，並計算每個元素之前有多少個零，並將其存儲在每個元素的容器中。

你看，真的有很多方法可以去......我可以思考和猜測另外幾個。但問問自己：你在尋找什麼樣的計算複雜性？

希望這會有所幫助。

來源

2016-10-16 22:14:52

-3

猜猜你可以做一個類，保存在地圖上的一切。所以，如果你請求一個不存在的元素，它返回0，否則返回元素

#include <map> 

using namespace std; 

#define ROW_LENGTH 10; 

map<int, int> entries = map<int, int>(); 

int getElement(int row, int column) { 
    int key = column * ROW_LENGTH + row; 

    if (entries.find(key) == entries.end()) { 
    return 0; 
    } else { 
    return entries[key]; 
    } 
} 
void setElement(int row, int column, int value) { 
    int key = column * ROW_LENGTH + row; 

    entries[key] = value; 
}

來源

2016-10-16 21:33:13 MadddinTribleD

，映射將創建並默認初始化該鍵的條目。因此，當您訪問備件矩陣時，地圖會增長，最終會比您使用標準數組時大得多。 – user4581301

因此，我檢查一個鍵是否已經存在'if（entries.find（key）== entries.end（））'。所以如果你真的插入新的元素，地圖只會增長。否則，我明白一些完全錯誤的：/ – MadddinTribleD

你讓我在那裏。兩個調整：'map ，int>'去2D並緩存'entries.find（）'的結果並使用它，而不是用'entries []'再次執行相同的查找。 – user4581301

可以使用本徵庫做稀疏矩陣操作。以下是鏈接：https://eigen.tuxfamily.org/dox/group__TutorialSparse.html

Eigen是一個高性能的線性代數庫。稀疏矩陣存儲爲一個二維鏈表（或者我應該說網絡）。每個非零項都有兩個指針，一個指向同一行的下一個非零項，另一個指向同一列的下一個非零項。基於將稀疏矩陣迭代乘積到矢量上的矩陣乘積和許多其他線性albegra操作可以在2D鏈表列表中高效地完成。

來源

2016-10-16 21:52:43

如果您不需要動態修改矩陣，那麼您可以使用CRS格式（壓縮行存儲），請參見[1]。它比其他答案中建議的鏈表更緊湊，需要額外的空間來存儲指針。它在許多軟件庫中實現，例如在另一個答案中引用的SuiteSparse [2]和Eigen [3]以及我自己的OpenNL庫[4]中。如果你需要在矩陣中動態插入元素，那麼它更復雜。我經常使用一組動態分配的行（每個行一個）。每行存儲J值對。這個結構也在OpenNL中實現[4]。

[1] https://en.wikipedia.org/wiki/Sparse_matrix

[2] http://faculty.cse.tamu.edu/davis/suitesparse.html

[3] http://eigen.tuxfamily.org/

[4] http://alice.loria.fr/software/geogram/doc/html/nl_8h.html

來源

2016-10-17 10:03:39 BrunoLevy