极稀疏数组的实现

Question

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

谢谢

Answer 1

首先,我认为普通数组显然是你问题的错误数据结构.

使用一个使用4- 元组作为索引的字典怎么样？

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

我自己从未这样做过,但它应该可以正常工作.如果Tuple由于您使用的是.NET 4之前的.NET Framework版本而没有准备好,则可以提供自己的索引类型:

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

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