34

Set<Integer>多くの要素を含む可能性のある不変のセット ( としてキャスト) があります。そのセットの要素と 1 つの追加要素を含むコレクションが必要です。セットをコピーしてから要素を追加するための厄介なコードがありますが、物事をできるだけ効率的に保つ正しい方法を探しています。

Guava を利用できますが、使用する必要はありません。

4

7 に答える 7

40

パフォーマンスについてはわかりませんが、Guava のImmutableSet.Builder:

import com.google.common.collect.ImmutableSet

// ...
Set<Integer> newSet = new ImmutableSet.Builder<Integer>()
                                .addAll(oldSet)
                                .add(3)
                                .build();

もちろん、そのためのヘルパー メソッドを自分で作成することもできます。

public static <T> Set<T> setWith(Set<T> old, T item) {
  return new ImmutableSet.Builder<T>().addAll(old).add(item).build();
}

// ...
Set<Integer> newSet = setWith(oldSet, 3);
于 2012-04-27T16:23:03.900 に答える
7

Sets.union() を検討してください。構築は速くなりますが、使用は遅くなります。

public static <T> Set<T> setWith(Set<T> old, T item) {
  return Sets.union(old, Collections.singleton(item);
}

(com.google.common.collect.Sets & java.util.Collections)

于 2012-04-29T03:23:20.050 に答える
3

3 つのオプションがあります。

  • 可変セットを使用します。
  • 要素がまだ存在していないことを確認します。存在しない場合は、セットのコピーを作成して要素を追加します。
  • 前のセットと要素を含むラッパー セットを作成します。

値の分布に依存するよりも、BitSeta の方が適している場合があります。Set<Integer>

于 2012-04-27T16:23:32.223 に答える
3

セットが不変の場合、セットをコピーしてから新しい要素を追加する以外にそれを行う方法はありません。セットのコピーは、新しいセットを作成するときに基本セットをコンストラクター関数に渡すのと同じくらい簡単です。

于 2012-04-27T16:22:19.557 に答える
0

フル コピーよりも優れたパフォーマンスが必要で、要素に順序付けがある場合は、B+ ツリーの周りに事実上不変のラッパーを使用して、インクリメンタル セットのパフォーマンスを向上させることができます。

B+ ツリーにアイテムを追加するには、O(n) ではなく、O(log(n)) 時間と増分割り当てが必要ですImmutableSet.builder().addAll(...).add(...).build()。これは、n 個の増分追加からセットを構築すると、O(sqr(n)) ではなく O(n*log(n)) になることを意味します。

この回答にはjdbmライブラリへのポインタがあるため、一見の価値があるかもしれませんjdbm:jdbm.

于 2016-10-27T13:03:31.853 に答える
-1

「不変」と「追加」を同じ文で読むと、認知的不協和を経験しています。不変値の可変コピーの末尾に新しい要素を追加することはできますが、不変セットを変更することはできません。私はエレガントなことを知りません。

于 2012-04-27T16:22:56.483 に答える