6

私は（C＃）からルックアップを行いたい、それぞれ8192の4つの次元を持つ非常にまばらな静的配列を持っています。これらの 4.5 * 10^15 値のうち 68796 のみが非ゼロです。速度とメモリ使用量が少ないことが不可欠で、これを行うための最速の方法は何ですか?

ありがとう

4

5 に答える 5

7

まず、単純な配列は、問題に対して明らかに間違った種類のデータ構造であると主張します。

4タプルをインデックスとして使用する辞書を使用するのはどうですか?

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

私はそれを自分でやったことがありませんが、うまくいくはずです。.NET Framework の .NET 4 より前のバージョンを使用しているために準備ができていない場合は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>();
于 2010-10-24T13:33:25.860 に答える
1

プレーンを使用するDictionaryか、ニーズに合った同様のマップを作成できます (4 つの値で計算したハッシュ値に従って要素を配置する配列になります) が、衝突に注意する必要があります。

また、検索に対数の複雑さを受け入れる場合は、バイナリ検索ツリーでうまくいく可能性があります..

于 2010-10-24T13:35:53.303 に答える
0

ハッシュテーブルを使用します (一般的な Dictionary は Hashtable として既に実装されています)。キーとして 4 次元インデックスのベクトルを使用します。欲しいものをバリューストアとして。

于 2010-10-24T13:35:46.307 に答える
0

私がしたいことは、これに「通常の」配列の代わりにハッシュリストを使用することです(疑似コード):

// 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-24T13:35:56.883 に答える
0

Dictionary<T, int>最善の方法は、4 つのインデックスを含むカスタムでインデックス付けされたハッシュ テーブル ( ) を使用することだと思いstructます。オーバーライドすることobject.Equals()を忘れないでください。object.GetHashCode()struct

于 2010-10-24T13:36:28.273 に答える