2

長方形 (x、y、幅、高さ) またはポイント (x、y) のリストに変換できる部屋と通路のセットがあります。RoomどちらもインターフェースをPassage拡張しPointableます。getPoints() メソッドは、Room クラスに対して次のように実装されます。

public Set<Point> getPoints() {
    Set<Point> array = new HashSet<Point>();
    for (int i = 0; i < width; i++) {
        for (int j = 0; j < height; j++) {
            array.add(new Point(x + i, y + j));
        }
    }
    return array;
}


問題:特定のが属する を
特定する必要があります。交差する部屋はありません。私はもともと a を使用して、それぞれを aに関連付けました。これにより、O(n) 時間ですばやく答えにアクセスできました。ただし、レベルの生成では複数回再計算する必要があります。この時点で、(生成とアクセスを考慮して) HashMap を使用する方が効率的ですか? それとも、2 次元間隔ツリーのセットなど、別の方法を使用する必要がありますか?PointablePointHashMap<Point,Pointable>PointPointableHashMap

4

1 に答える 1

1

この時点で、(生成とアクセスを考慮して) HashMap を使用する方が効率的ですか? それとも、2 次元間隔ツリーのセットなど、別の方法を使用する必要がありますか?

測った人以外はわかりません。それはすべて、データを更新する必要がある頻度、データが変更される頻度、クエリされる頻度によって異なります。

また、のサイズでRoom。典型的なシナリオでは、ポイントが数個あればHashMap勝利しますが、数千個の場合は、ポイントを更新するオーバーヘッドが支配的です。

すべての s に配列を使用できませんPointか? もしそうならHashMap、特に更新の場合（本当に巨大にならない限り）、より確実に高速になります。

これは役立つ場合とそうでない場合があります。

実際には、それぞれRoomがいくつかPointの s を持つだけでなく、それぞれPointが 1 つRoom(n:1) を持つこともあります。それがどのように実装されるかは、別の問題です。

これを考えると、標準的な問題があります。双方向にリンクする場合、両方のリンクを同期させておく必要があります。最も簡単な解決策は、セッター (「adders」/「removers」) を可能な限り非公開にし、メソッドからのみ呼び出すことです。

void link(Room room, Point point) {
    Room oldRoom = point.getRoom();
    if (oldRoom!=null) oldRoom.removePoint(point);
    room.addPoint(point);
    point.setRoom(room);
}

Pointからへのリンクは外部ですが、これはほとんど何も変更しません (小さく、おそらくきれいに保ち、各アクセスに HashMap の小さなオーバーヘッドを追加することRoomを除いて)。Point

通常、更新よりもクエリの方がはるかに多いため、通常は最速です。あなたの問題は、更新コストがRoomサイズによって拡大されることです。数値を教えていただけなければ、見積もりはできません。

サイズがあまり大きく変化しないポイントと部屋が多すぎる場合、ポイント座標をいくつかの倍数に丸め、nグリッドと交差するすべての部屋のセットを保持する配列を保持できます。前と同じように進めることもできますが、更新のオーバーヘッドは部屋の面積 (*) によって与えられる係数のほぼ 1 倍低くなり、検索のオーバーヘッドは高くなります。これは、セットから実際に一致する部屋 (存在する場合) を選択する必要があるためです。

(*) グリッドに整列していない部屋の場合、交差する長方形の数は明らかに多くなります。

于 2014-11-24T04:33:57.513 に答える