java - 2D データを格納するためのデータ構造のアイデアはありますか?

Question

x-by-y の大きな 2D グリッドがあります。アプリケーションのユーザーは、このグリッド上の特定のポイントに関するデータを追加します。残念ながら、グリッドが実行されているシステムには十分なメモリがないため、グリッドは大きすぎて大きな x 行 y 列の配列として実装できません。

データが追加されたポイントのみがメモリに保存されるように、これを実装する良い方法は何ですか?

私の最初のアイデアは、データポイントの BST を作成することでした。ノードの比較には、「(long)x<<32 + y」などのハッシュ関数が使用されます。

次に、バランスが取れていないと効率が低下する可能性があると結論付けたので、ポイントの同等の BST の BST を使用するというアイデアを思いつきました。外側の BST は、x 値に基づいて内側の BST を比較します。内側の BST は、点を y 値で比較します (そして、それらはすべて同じ x になります)。そのため、プログラマーが (5,6) にポイントがあるかどうかを確認したい場合、外側の BST に 5 を問い合わせます。そのポイントに内側の BST が存在する場合、プログラマーは内側の BST に 6 を問い合わせます。結果は次のようになります。返されます。

これを実装するためのより良い方法を考えられますか?

編集: HashMaps に関して: ほとんどの HashMaps には、ルックアップ用の配列が必要です。「data[hash(Point)] = Point();」と言う人もいるでしょう。ポイントを設定し、それをハッシュしてインデックスを見つけることでポイントを見つけます。ただし、問題は、配列がハッシュ関数の範囲のサイズでなければならないことです。この範囲が追加されるデータポイントの総数よりも少ない場合は、余裕がないか、オーバーフローに追加する必要があります。追加されるポイントの数がわからないため、この数が特定の量よりも少ないと仮定して、配列をそのサイズに設定する必要があります。繰り返しますが、これは非常に大きな配列をインスタンス化します (ただし、x*y よりもデータポイントが少ないと仮定すると、元の配列よりも小さくなります)。

一部の人が言及したように、私が欲しいのはSparseArrayのようです。それらは、BST 内に BST を持つのと同様に実装されていますか?

Edit2: Map<> はインターフェースです。Map を使用する場合は、TreeMap<> が最適なようです。したがって、人々が行った Map< Map< Point> > の提案に似た TreeMap< TreeMap< Point> > になります。これは基本的に BST 内の BST です。TreeMap<> が基本的に BST の Java SDK であることを知らなかったので、情報をありがとう。

Edit3: 関係者にとっては、選択された回答が最善の方法です。最初に、(x,y) を含み、comparable を実装する Point クラスを作成する必要があります。Point は、(((long)x)<<32)+y) のようなもので比較できる可能性があります。次に、それぞれのデータを指す TreeMap を作成します。バランスの取れたツリーにあるため、これを検索すると効率的であり、log(n) のコストがかかります。ユーザーは、データとともに Point のセットを返す TreeMap.entrySet() 関数を使用して、このデータのすべてを照会したり、データを繰り返し処理したりすることもできます。

結論として、これにより、スパース配列 (私の場合は 2D 配列) のスペース効率と検索効率の高い実装が可能になり、効率的に反復することもできます。

score 7 · Accepted Answer

Quadtree、k -d-tree、またはR-treeのいずれか。

大きなポイント配列へのインデックスを空間構造の 1 つに格納します。このような空間構造は、地理データが都市に集中し、海にはポイントがないなど、データが均等に分散されていない場合に有利です。

通常のグリッドを忘れて、クアッドツリーを使用できるかどうかを考えてください。
(なぜ通常のグリッドが必要なのか考えてみてください。通常、通常のグリッドは単に単純化したものです)

いかなる場合でも、オブジェクトを使用してポイントを格納しないでください。そのようなオブジェクトは、それがオブジェクトであるという事実のためにのみ 20 バイトを必要とします! 巨大なデータセットの悪い考えです。

、int x[]およびint[] y、またはint[]xy配列は、メモリ使用量に関連して理想的です。

読むことを検討してください

ハナン・サメットの 「多次元データ構造の基礎」

（少なくとも紹介）。

score 4 · Accepted Answer

を使用しMap<Pair, Whatever>てデータを保存できます (Pair クラスを作成する必要があります)。特定の順序でデータを反復する必要がある場合は、 PairComparableを作成して使用しますNavigableMap

score 2 · Accepted Answer

1 つのアプローチが考えられますMap<Integer, Map<Integer, Data>>。外側のマップのキーは行の値で、内側のマップのキーは列の値です。Dataその内部マップ (この場合は型) に関連付けられた値は、のデータに対応し(row, column)ます。もちろん、行列演算などを行おうとしている場合、これは役に立ちません。そのためには、疎行列が必要です。

もう 1 つの方法は、行と列をCoordinateクラスまたはクラスとして表すことPointです。equalsandを実装する必要がありますhashCode(非常に簡単なはずです)。次に、データをMap<Point, Data>またはとして表すことができますMap<Coordinate, Data>。

score 1 · Accepted Answer

オブジェクトのリストのリストを持つことができ、そのオブジェクトはその水平および垂直位置をエンコードできます。

class MyClass
{
    int x;
    int y;
    ...
}

score 0 · Accepted Answer

メモリ効率の良い方法でこれを行うのは正しい方向に進んでいると思います-クラスにラップされたマップのマップを使用して、ルックアップ用のクリーンなインターフェイスを提供することで、かなり簡単に実装できます。

別の (そしてよりメモリ効率の良い) アプローチは、キーがタプル (x,y) である単一のマップを使用することです。ただし、「Give me all values where」のようなクエリを作成する必要がある場合、これはあまり便利ではありませんx == some value。

score 0 · Accepted Answer

FlexCompColMatrix、CompColMatrix、およびマトリックスツールキットプロジェクトの他のスパースマトリックスの実装を参照することをお勧めします。

パフォーマンスは実際には書き込み/読み取り比とマトリックスの密度に依存しますが、マトリックスパッケージを使用している場合は、実装を切り替えることで簡単に実験できます。

score 0 · Accepted Answer

あなたへの私の提案は、Commons Math: The Apache Commons Mathematics Libraryを使用することです。アプリケーションが必要とする数学の力を活用することで、1 日を節約できるからです。

score 0 · Accepted Answer

ここでは単純化しすぎているかもしれませんが、通常のHashMap. キーとしてカスタムPointオブジェクトが含まれます。

class Point {
    int x;
    int y;
}

x次に、equals メソッド (および hashCode メソッド) をオーバーライドして、 andに基づいていyます。そうすれば、何らかのデータを持つポイントのみを保存できます。

java - 2D データを格納するためのデータ構造のアイデアはありますか?

8 に答える 8

Related

Reference