c# - 极稀疏数组的实现

Question

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

谢谢

Answer 1

首先，我认为对于您的问题，纯数组显然是错误的数据结构。

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

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

我自己从来没有这样做过，但它应该可以正常工作。如果您因为使用 .NET 4 之前的 .NET Framework 版本而没有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 维索引的关键使用向量。作为价值存储你想要的。

Answer 4

我要做的是为此使用哈希列表而不是“普通”数组，然后（伪代码）：

// first, check bounds:
if(x < 0 || y < 0 || z < 0 || w < 0
|| x > xsize || y > ysize || z > zsize || w > wsize)
    throw new Whatever(...);

// now return value if != 0
if(x in arr && y in arr[x] && z in arr[x][y] && w in arr[x][y][z])
    return arr[x][y][z][w];
else
    return 0;

Answer 5

我认为最好的方法是使用哈希表 ( Dictionary<T, int>)，并使用struct包含 4 个索引的自定义索引。不要忘记覆盖object.Equals()and object.GetHashCode()。struct