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.

详细信息:我在内存中存储了大量原始形状数据，如立方体.我确实有大量(大约 3000 万个)并且我周围有很多空(零)条目.鉴于我的每个条目花费 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<...>(initial capacity) 来避免在添加项目时不必要的调整大小.

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屋！