极稀疏数组的实现

Question

我有一个非常稀疏的静态数组，每个数组有4个维数，每个维数为8192，我想从这个数组中进行查找(C#)。在这些4.5x10^15值中，只有68796是非零值。在速度和低内存使用率至关重要的情况下，最快的方法是什么？

谢谢

Answer 1

首先，我认为对于你的问题，普通数组显然是一种错误的数据结构。

在使用4-tuple作为索引的情况下使用dictionary如何？

var lookup = new Dictionary<Tuple<int,int,int,int>, int>();

我自己从来没有这样做过，但它应该可以很好地工作。如果您因为使用的是.NET 4之前的.NET框架版本而没有准备好Tuple，那么可以提供自己的索引类型：

struct LookupKey
{
    public readonly int First;
    public readonly int Second;
    public readonly int Third;
    public readonly int Fourth;
    …
}

var lookup = new Dictionary<LookupKey, int>();

Answer 2

您可以使用普通的Dictionary或创建一个适合您需要的类似映射(它将是一个数组，您可以根据您在4个值上计算的哈希值在其中放置元素)，但您需要注意冲突。

此外，如果您接受查找的对数复杂度，则二进制搜索树也可以实现此目的。

Answer 3

使用哈希表(泛型字典已经实现为哈希表)。作为键使用4维索引的向量。作为值存储您想要的内容。