3D稀疏矩阵实现？ [英] 3D sparse matrix implementation?

问题描述

我在 http://www.blackbeltcoder.com/Articles/algorithms/creating-a-sparse-matrix-in-net 。

我在3D坐标系中工作，我需要一个稀疏矩阵实现，可以用来映射3D坐标系。

But as i work in 3d coordinate-system, i need a sparse-matrix implementation that i can use to map the 3d-coordinate system.

详细信息：我存储了大量像立方体一样的内存中的原始形状数据集。我确实有很多（大约三千万），并且周围有很多空（零）条目。鉴于我的每个条目都花了1个字节的条目，我想实现一个稀疏矩阵，以便我可以公平地节省内存空间。

Details: I'm storing large amounts of primitive shapes data in memory like cubes. I do have large amounts of them (around 30 million) and i've lots of null (zero) entries around. Given that my each entry costs 1-bytes of entry, i'd like to implement a sparse-matrix so that i can fairly save memory space.

注意：快速访问矩阵单元对我来说是一个非常重要的因素，因此我要以速度来代替内存消耗。

Note: Fast access to matrix cells is a fairly important factor for me, so i'd be trading speed over memory consumption.

推荐答案

一个非常简单的方法我刚刚提出的解决方案是：

A very simple solution which I just made is this:

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 值等。

It could be extended with methods like those his version have, and with checks for x, y, z values etc.

我敢肯定有人会对它的性能有话要说。除非您确实需要一些高性能的东西，否则它将是一个不错的实现。这取决于 Tuple 的哈希码实现和您的特定用法。如果我们假设哈希值很好，我们将有 O（1）查找时间。如果您知道会有很多元素，可以使用 new Dictionary< ...>（初始容量）来避免在添加项目时不必要地调整大小。

I'm sure someone have something to say about its performance. It will be a decent implementation unless you really need something it for high-performance. It depends on the hash-code implementation of Tuple and your specific usage. If we assume the hashes are good, we will have O(1) lookup time. If you know you will have a lot of elements, you could use new Dictionary<...>(initial capacity) to avoid unnecessary resizing when added items.

与他的不同，它只有一个 Dictionary 和所有项。他的版本有字典。他的好处是，如果您必须扫描整行，则可以仅迭代第二级字典（这对您要扫描列无济于事），这比逐项查找要快。但是只有一个字典意味着内存使用量更少-特别是当您每行只有很少的项目时。

Unlike his, this only have a single Dictionary with all the items. His version have dictionaries of dictionaries. The benefit of his, is if you have to scan over an entire row, you can just iterate the second-level dictionary (this will not help you is you want to scan over columns) which is faster than individual lookup of the items. But having a single dictionary means smaller memory usage - especially when you have few items per row.

这篇关于3D稀疏矩阵实现？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！