對於稀疏矩陣的存儲，每個行的矢量或向量的存儲性更好

對於存儲稀疏矩陣的數據結構如下所示。如果我有一個矩陣如下 enter image description here 對於稀疏矩陣的存儲，每個行的矢量或向量的存儲性更好

我正在使用一對向量來存儲數據。因此，它是更好地將這些值存儲在這樣一個載體： -

enter image description here

還是會更好地將它們存儲這樣的： -

enter image description here

我使用的是獨立的矢量來存儲關於每行的開始和結束索引的數據。

哪兩種方法會使用較少的內存?????

我不明白單個矢量如何工作。如果有完全由零組成的行呢？ – 2013-05-02 21:41:10

那麼分配將以第二行的值開始。這將在行向量中的值處理 – 2013-05-02 21:49:37

如果你的矩陣只有50％像你的例子那樣稀疏，我不會擔心它。 2d矩陣的性能非常好，所有替代品都會變得更慢。 – 2013-05-02 22:24:01

由於向量分配一個連續內存塊（與列表不同），所以單個向量將通過合併堆開銷來使用更少的內存。我假設客戶端界面是相同的（例如，重載操作符[]），所以你的問題只是關於內存效率。

2013-05-02 21:44:54

是的我只是擔心內存使用量，因爲稀疏矩陣的數據結構應該使用最小內存。差異會太大嗎？ – 2013-05-02 21:51:12

取決於行數，可直接轉換爲您的向量數。單個向量的另一個可能的優點是參考的局部性 - 緩存線效率以及所有這些。 – 2013-05-02 21:53:38

但是，如果我要在第一行中插入值，那麼在插入矢量向量的情況下插入值時，它不會非常有效如果在單個向量中，我將不得不移動所有具有較高索引的行的值 – 2013-05-02 21:58:04

回答