1

StackOverflow に関する質問を (おそらく数十件) 調べましたが、探しているものが見つからなかったと思います。

次のプロパティを持つ Java 構造が必要です。

  1. ソート済み
  2. 反復可能
  3. ジェネリックをサポート
  4. O(logn) (またはそれ以上) の挿入と削除
  5. O(logn) (またはそれ以上) の要素へのアクセス
  6. 重複エントリーを許可

なんで？k-最近距離アルゴリズムを実装しています。データ コレクションの各ポイントについて、k 番目に近い他のポイントまでの距離を見つける必要があります。このアルゴリズムは、ポイントの各ペアを繰り返し処理し、それらの間の距離を計算し、その距離がそのリスト内の他の要素よりも近い場合、各ポイントの最も近い距離の並べ替えられた構造にその距離を追加することによって機能します。デモ用のコードを次に示します。

ArrayList<SortedThing<Double>> nearestDistances = new ArrayList<SortedThing<Double>>(numPoints);
for (int i = 0; i < numPoints; i++) {
    nearestDistances.add(new SortedThing<Double>(k));
}

for (int point = 0; point < numPoints; point++) {
    for (int otherPoint = point+1; otherPoint < numPoints; otherPoint++) {
        double distance = computeDistance(point, otherPoint);

        if (nearestDistances.get(point).size < k)
            nearestDistances.get(point).add(distance);
        else if (nearestDistances.get(point).last() > distance) {
            nearestDistances.get(point).removeLast();
            nearestDistances.get(point).add(distance);
        }

        if (nearestDistances.get(otherPoint).size < k)
            nearestDistances.get(otherPoint).add(distance);
        else if (nearestDistances.get(otherPoint).last() > distance) {
            nearestDistances.get(otherPoint).removeLast();
            nearestDistances.get(otherPoint).add(distance);
        }
    }
}

以下の組み込み Java クラスのいずれかを提案する前に、私がそれらを使用したくない理由を次に示します。

  1. PriorityQueue - 最後の要素にアクセスできません
  2. TreeSet - 距離の重複は許可されません
  3. ArrayList - はい、ArrayList を使用して、n-1 の距離をすべて挿入し、O(nlogn) 時間で並べ替えてから、k 番目の要素を削除できます。ただし、これには O(nk) スペースではなく O(n^2) スペースが必要です。
  4. ArrayList - 別の方法として、並べ替えられた ArrayList を維持し、最後の要素を削除して新しい要素を正しい位置に挿入することもできますが、挿入には挿入ごとに O(k) の時間がかかり、位置を見つけるのに O(logk) かかりますインサート。

そのような構造を知っている人はいますか？私は最近、このことについてよく考えていましたが、Java がそのような構造を提供していないことに驚きました。

4

2 に答える 2

1

Apache Commons Collectionsの TreeBagを確認してください。

TreeBagTreeMapエントリを保持するために使用します。

于 2013-05-30T21:22:52.120 に答える
1

最近隣検索を行っている場合は、kd ツリーを使用することをお勧めします。これは Java の実装です (ソース コードについては、.jar ファイルの \bak ディレクトリを参照してください)。

それ以外の場合は、値がキーの重複の数である TreeMap を使用することをお勧めします (1 は重複がないことを意味し、2 は重複が 1 つであることを意味します)。

Map<Key, Integer> map = new TreeMap<>();

if(map.containsKey(key)) {
    map.put(key, map.get(key) + 1);
} else {
    map.put(key, 1);
}
于 2013-05-30T21:20:23.500 に答える