三維稀疏矩陣實現？

我發現了一個相當不錯的稀疏矩陣實施C＃http://www.blackbeltcoder.com/Articles/algorithms/creating-a-sparse-matrix-in-net。三維稀疏矩陣實現？

但是，因爲我在三維座標系統工作，我需要一個稀疏矩陣實現，我可以用它來映射三維座標系統。

細節：我在內存中存儲了大量的原始形狀數據，如立方體。我確實有大量的（大約3000萬），並且我有大量空（零）條目。考慮到我的每個條目都需要1個字節的條目，我想實現一個稀疏矩陣，這樣我才能公平地節省內存空間。

注意：快速訪問矩陣單元對我來說是一個相當重要的因素，所以我會交易超過內存消耗的速度。

我只是做

來源

2011-03-31 HuseyinUslu

你的用例是什麼？ 3D圖形的變換矩陣？ – Alnitak 2011-03-31 12:07:39

nop，只是在問題中添加了詳細信息。 – HuseyinUslu 2011-03-31 13:15:38

對，所以它是一個稀疏的體素矩陣。 30M是細胞總數還是填充細胞數量？ – Alnitak 2011-03-31 13:24:12

一個非常簡單的解決辦法是這樣的：

public class Sparse3DMatrix<T> 
{ 
    Dictionary<Tuple<int,int,int>, T> values = new Dictionary<Tuple<int, int, int>, T>(); 

    public T this[int x, int y, int z] 
    { 
     get { return values[new Tuple<int, int, int>(x, y, z)]; } 
     set { values[new Tuple<int, int, int>(x, y, z)] = value; } 
    } 

    public bool ContainsKey(int x, int y, int z) 
    { 
     return values.ContainsKey(new Tuple<int, int, int>(x, y, z)); 
    } 
}

用法：

var test = new Sparse3DMatrix<float>(); 
test[1, 1, 1] = 1f; 
Console.WriteLine(test[1, 1, 1]);

這可能與像他的那些版本的方法來擴展擁有，並與檢查x, y, z值等。

我確定有人有話要說它的表現。除非你真的需要高性能的東西，否則它將是一個體面的實現。它取決於Tuple的散列碼實現和您的具體用法。如果我們假設哈希值是好的，我們將有O(1)查找時間。如果您知道自己有很多元素，則可以使用new Dictionary<...>(initial capacity)以避免在添加項目時進行不必要的調整大小。

不像他的，它只有一個Dictionary與所有項目。他的版本有詞典的字典。他的好處是，如果你必須掃描整行，你可以迭代二級字典（這不會幫助你，你想掃描列），這比單獨查找項目更快。但使用單個詞典意味着更小的內存使用量 - 尤其是當您每行只有很少的項目時。

來源

2011-03-31 11:08:06

無論您是否可以使用此數據結構，您在3D座標系中工作的事實都不會改變。可以使用與2D矩陣相同的稀疏矩陣來包含用於3D空間的矩陣;這只是改變的條目。

您將使用一個稀疏矩陣用於包含大量零條目的大型項目。這在物理問題的離散表示中是典型的，這些問題來自有限差分和有限元方法。它們具有聚集在對角線周圍的非零條目的帶;對角帶外的條目通常爲零。稀疏矩陣不會存儲這些;像LU和QR這樣的分解必須被寫出來以知道如何處理稀疏性。

這些矩陣可以描述2D或3D空間中的問題。

如果你認爲你需要另一個數據結構，我相信你不正確。

來源

2011-03-31 11:20:25 duffymo

稀疏矩陣是我去的方式，因爲正如你提到我的矩陣將包含很多零（空）條目。 – HuseyinUslu 2011-03-31 13:16:13

但在這種情況下，2D或3D並不重要。 – duffymo 2011-03-31 14:11:35

爲什麼不使用KD-Tree或類似的數據結構（如Octtree）？有很好的C++實現，例如：FLANN

來源

2013-12-28 13:37:04 B0rk4

Lasse Espeholt的解決方案是實用的，但它可以通過刪除元素時「零」或零。如果你不這樣做矩陣或數組可以失去稀疏。這是一種替代解決方案，假設某種類型的元素沒有被插入，它是該類型的默認值。例如，對於double表示0.0，對於string表示null。

public class Sparse3DArray<T> 
{ 
    private Dictionary<Tuple<int, int, int>, T> data = new Dictionary<Tuple<int, int, int>, T>(); 

    public int Nnz { get { return data.Count; } } 

    public T this[int x, int y, int z] 
    { 
    get 
    { 
     var key = new Tuple<int, int, int>(x, y, z); 
     T value; 
     data.TryGetValue(key, out value); 
     return value; 
    } 

    set 
    { 
     var key = new Tuple<int, int, int>(x, y, z); 
     if (null == value) 
     data.Remove(key); 
     else if (value.Equals(default(T))) 
     data.Remove(key); 
     else 
     data[key] = value; 
    } 
    } 
}

來源

2016-08-19 09:41:53

三維稀疏矩陣實現？

回答

相關問題