Javaで2Dグリッドをプログラミングする

Question

Javaで2次元グリッドのタイルをプログラミングするときに使用する最適なデータ構造は何ですか？グリッド上のタイルは、それらの位置によって容易に参照されるべきであり、その結果、近傍および経路を効率的に計算することができる。 2D配列でなければならないのでしょうか？ ArrayList？他に何か？

Answer 1

速度やメモリをあまり心配していない場合は、2D配列を使用するだけで十分です。

速度やメモリが問題になる場合は、メモリ使用量とアクセスパターンによって異なります。

高性能が必要な場合は、1次元配列を使用します。適切なインデックスはy * wdt + xと計算されます。これには2つの潜在的な問題があります。キャッシュミスとメモリ使用です。

ほとんどの場合、要素の近隣ノードを取得するようなアクセスパターンであることがわかっている場合は、上述のように2D空間を1Dアレイにマッピングすると、キャッシュミスが発生する可能性があります。メモリ、および2つの異なる行からの隣人はそうではありません。 2次元タイルを別の順序で1次元配列にマップする必要があるかもしれません。例えば、Hilbert curvesを参照してください。

タイルのサイズが常に同じであることがわかっている場合は、sparse arrayまたはを実装することをおすすめします。どちらも、キャッシュの認識を考慮して、非常に効率的に実装できます（スパースな配列リンクがこれの良い例です）。もう1つの利点は、これらを動的に拡張できることです。ただし、これが機能するには、最後に間接的なレベルの特別な処理を行う必要があります。

注：キータイプがプリミティブ型の場合は、HashMapなどの汎用クラスを使用することに注意してください。パフォーマンスが心配な場合は特別な場所クラスを使用してください。インデックスを作成するたびにオブジェクトを割り当てるかハッシュマップやボクシング/ unboxingの価格を支払う。これに加えて、ハッシュマップでは効率的な空間クエリはできません（例えば、与えられたオブジェクトの半径Rに存在するすべてのオブジェクトを与えてください - クワッドツリーはこれより優れています）。

Answer 2

2D配列は、物を特定の場所に挿入する予定がある場合は良い選択です。固定サイズである限り。

Answer 3

グリッドの固定寸法がある場合は、2D配列を使用します。サイズを動的にする必要がある場合は、ArrayListのArrayListを使用します。

Answer 4

セルのグリッドとランダムなアドレス指定を繰り返すだけであれば、MyCellType [] []は問題ありません。これは、これらのユースケースのためのスペースと（予想される）時間の点で最も効率的です。

Answer 5

データ構造本当に実行する操作の種類に依存使用する：

グリッドにおける有意義な位置（非ゼロ/非デフォルト）の数がかなり低い場合には（< < n×m個）それは（x、y）の位置を特定のタイルにマップするハッシュマップを使用すると、スペース効率が向上する可能性があります。また、意味のあるポジションをより効率的に繰り返すことができます。さらに、隣接するタイルへの参照を各タイルに保存して、パス/近傍トラバーサルを高速化することもできます。

グリッドが "情報"でいっぱいになっている場合は、2次元配列またはArrayListを使用することを検討する必要があります（ある時点で、「タイル型」としてジェネリック型が関与する場合は、ジェネリック型のネイティブ配列は許可されません）。