极其稀疏数组

实现我有4个维度每个我想从（C＃）做的查找8192极其稀疏静态数组。这些4.5 * 10^15值中只有68796个非零。要做到这一点，最快的方法是什么？速度和低内存使用率至关重要？极其稀疏数组

感谢

2010-10-24 Hassan

首先，我认为简单的数组是很清楚错误的数据结构，为您的问题。

如何使用dictionary，你用一个4 tuple为指标？

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>();

来源

2010-10-24 13:33:25 stakx

使用哈希表（通用字典已经被实现为哈希表）。作为4维索引的关键使用向量。作为价值存储你想要的东西。

来源

2010-10-24 13:35:46 Dewfy

您可以使用普通的Dictionary或创建一个适合您需要的类似地图（这将是一个数组，您可以根据您的4值计算散列值来放置元素），但您需要关心碰撞。

也是一个二进制SEACH树可以使的伎俩，如果你接受查找对数复杂..

来源

2010-10-24 13:35:53 Jack

如果您使用自定义对象并正确实现了'Equals（）'和'GetHashCode（）'，那么'Dictionary'将自行处理碰撞。 – svick 2010-10-24 13:39:23

我会做的是用散列表，而不是“正常”阵列对于这一点，那么（伪代码）：

// 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;

来源

2010-10-24 13:35:56

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

来源

2010-10-24 13:36:28 svick

极其稀疏数组

回答

相关问题