3

私のアプリケーションでは、2D 座標 (x,y) のコレクションをチェックして、特定の座標がコレクション内にあるかどうかを確認する必要があります。可能な限り高速である必要があり、1 つのスレッドからのみアクセスされます。(衝突チェック用です)

誰かが私に正しい方向へのプッシュを与えることができますか?

4

5 に答える 5

5

私が考えることができる絶対的な最速は、それらのポイントの2Dマトリックスを維持することです:

//just once
int[][] occurrences = new int[X_MAX][Y_MAX];
for (Point p : points ) {
    occurrences[p.x][p.y]++;
}

//sometime later
if ( occurrences[x][y] != 0 ) {
    //contains Point(x, y)
}

いくつあるか気にしない場合は、booleanマトリックスだけで機能します。明らかに、マトリックスが一度だけ作成され、ポイントがコレクションに追加されると更新される場合にのみ、これは高速になります。

要するに、基本的なコレクションはこれには完全ではありません (ただし、それHashSetに近づくことはできます)。

編集

Set<Point>これを行うライブラリがまだ見つからない場合は、これを簡単に適応させることができます。このようなもの：

public class PointSet implements Set<Point> {
    private final boolean[][] data; 
    public PointSet(int xSize, int ySize) {
        data = new boolean[xSize][ySize];
    }

    @Override
    public boolean add(Point e) {
         boolean hadIt = data[e.x][e.y];
         data[e.x][e.y] = true;
         return hadIt;
    }

    @Override
    public boolean contains(Object o) {
        Point p = (Point) o;
        return data[p.x][p.y];
    }

    //...other methods of Set<Point>...
}
于 2010-06-07T17:17:06.310 に答える
2

いくつかのTrove コレクションのデータ構造を使用します。

ポイントがいくつintかまたはいくつかとして保存されている場合は、x 座標の場合は 32 ビット、y 座標の場合は 32 ビットにfloatパックできます。long次に、プリミティブ データを操作するために最適化されたTLongHashSetを使用できます (通常の Java コレクションと比較して、高速でメモリ消費量が少なくなります)。HashSet

座標がある場合intは、次のようになります

static private long computeKey(int h1, int h2)
{           
    return ((long)h1) << 32 | h2;
}

キーを計算してから使用する

TLongHashSet set = new TLongHashSet()
set.add(long v);
set.addAll(long[] v);
set.containsAll(..);

値がある場合floatは同じことができますが、浮動小数点ビットを .xml 内にパックする必要がありますlong。

于 2010-06-07T17:24:29.943 に答える
1

ハッシュセット。その O(1) 平均。真の O(1) が必要な場合は、コレクションへの参照を持つオブジェクトのラッパーを作成できます。そうすれば、あなたが持っているコレクションと単純に比較することはできません。

于 2010-06-07T17:25:24.637 に答える
0

コレクションを検索する場合と比較して、どのくらいの頻度でコレクションを更新する必要がありますか? それに基づいて適切なデータ構造を選択する必要があります。

Point2D は同等の実装ですよね？その場合、最善の策はおそらく TreeSet です。それらは信じられないほど高速であり、実際のデータベースやファイルシステムで使用されていることをご存知かもしれませんが、B+ ツリーに依存していると思います。

構造に対してかなりの量の更新を行うと思われる場合は、SkipList を見てください。O(log(operations)) を保証します **これは、実行するすべての操作に対するものであり、単一の操作の実行時間に関する保証はありません)

于 2010-06-07T17:24:39.033 に答える
-1

バイナリ検索を実行できるため、treeset などのソートされたセットを試すことができます。

于 2010-06-07T17:23:51.613 に答える