1

構造体k => v(kおよびvは>=0int ) はすべてkが一意でvあり、等しい場合があります (k1 => vおよび) は、値k2 => vの昇順で並べ替える必要があります。次に例を示します。v

新しいペアを[35 => 1, 23 => 4, 9 => 9, 2 => 14]挿入したい20 => 5場合、結果は になります[35 => 1, 23 => 4, 20 => 5, 9 => 9, 2 => 14]。

いくつかの入力データに基づいて作成し、左から「1つずつ」方法でさらに反復するために使用できるJavaで最速の構造は何ですか? SortedHashMap?

4

3 に答える 3

1

そのための既存の構造はないと思います。

SortedMap は、値ではなくキーを使用してソートするため、適切ではありません。

HashMap を使用し、entrySet をリストにコピーする追加のメソッドでソートを実装します。リストは、値を比較するカスタム コンパレータを使用して並べ替えられます。

ここでパフォーマンスが重要なポイントである場合は、独自の構造を実装することを検討する必要があります。これを行うには多くの可能性があり、何が最速かは言えません。どの操作をどのくらいの頻度で実行するかによって異なります。

于 2012-08-15T10:00:44.993 に答える
1

少し前に、私は同様の状況に遭遇しました。いくつかのマップを並行して使用しました。

  • A HashMap<K, P>M (P はペア タイプ)。キーでペアを検索できるようにします。

  • A TreeMap<P, P>S。最初に値で、次にキーでソートするコンパレータを使用して、常に正しいソート順を使用できるようにします。

両方の構造を並行して維持することで、キーをソート値として使用しなくても、ペアを常にソートすることができます。

ペアを追加するには:

M.put(key, pair);
S.put(pair, pair);

キーでペアを取得するには:

M.get(key);

ペアを削除するには:

P pair = M.get(key);
M.remove(key);
S.remove(pair);

並べ替えられたペアのリストを取得するには:

S.keySet();

コア操作の平均的な複雑さは次のとおりです。

  • 追加: O(logn)( TreeMap)
  • 取得: O(1)( HashMap)
  • 削除: O(logn)( TreeMap)
于 2012-08-15T10:09:53.420 に答える
1

増分構築が必要ない場合は、次のようにします。

List<Pair> pairs = ...;
Collections.sort(pairs, new Comparator<Pair>() {
    @Override public int compare(Pair p1, Pair p2) {
        return p1.v - p2.v;
    }
}
LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
map.addAll(pairs); // retains insertion order
return map;
于 2012-08-15T10:10:36.783 に答える