1

このクラスは、問題が発生する場所の例です。

public class ContainsSet {
    private static HashSet<E> myHashSet;

    [...]

    public static Set<E> getMyHashSet() {
        return new HashSet<E>(myHashSet);
    }

    public static boolean doesMyHashSetContain(E e) {
        return myHashSet.contains(e);
    }
}

ここで、2つの可能な関数を想像してください。

boolean method1() {
    return ContainsSet.getMyHashSet().contains(someE);
}
boolean method2() {
    return ContainsSet.doesMyHashSetContain(someE);
}

ここで、メソッド1がJava最適化後にメソッド2と同じ時間計算量を持つかどうかという質問です（複雑さがあることを強調するHashSet代わりに使用しました）。SetmyHashSet.contains(someE)O(1)

最適化がなければ、そうではありません。.contains()複雑さO(1)はありますが、new HashSet<E>(myHashSet)複雑さはありますO(n)。これにより、メソッド1の複雑さがになります。O(n) + O(1) = O(n)これは最愛の人と比較して恐ろしいことO(1)です。

この問題がインポートされる理由は、外部クラスがその内容を変更することを許可しない場合は、リストまたはセットを返さないように教えられているためです。コピーを返すことは明らかな解決策ですが、それは本当に時間がかかる可能性があります。

4

3 に答える 3

7

いいえ、javacこれを最適化しません (そしてできません)。ソースに記述したバイトコードをこのレベルまで出力する必要があります。そして、JVM は、これを最適化するほど十分にインテリジェントではありません。証明するには副作用がある可能性が高すぎます。

HashSet不変性が必要な場合は、のコピーを返さないでください。変更不可能なラッパーでラップします。Collections.unmodifiableSet(myHashSet)

于 2013-02-14T14:24:37.113 に答える
0

ここで言えることは、新しい HashSet を作成し、コンストラクターを介してデータを入力するのはコストがかかるということです!

Java はこの作業を「最適化」しません。あなたも私も、contains() 呼び出しを「通過」した場合と同じ結果が得られることを知っていても、Java はこれを知ることができません。

于 2013-02-14T14:24:24.833 に答える
0

いいえ、それは最適化を超えています。新しいオブジェクトを返し、それを別の場所で使用できます。Java はそれを省略することは想定されていません。新しい HashSet が作成されます。

これは、コピーを返すことをお勧めしません。時間がかかるだけでなく、スペースも消費します。Sean が言ったように、unmodifiableSet でラップするか、独自のクラスでラップすることができます。

これを試すことができます：

public static Set<E> getMyHashSet() {
    return Collection.unmodifiableSortedSet(myHashSet);
}

注: そのメソッドを使用すると、コピーではなく、セットのビューが返されます。

于 2013-02-14T14:37:11.367 に答える