2

Java では、Collection インターフェースのおよびメソッドを介して、2 つの Collection オブジェクトの(集合論的) 差と交差を計算できます。removeAll()retainAll()

Java 6のAbstractCollection クラスでのこれら 2 つのメソッドの実装は、

public boolean removeAll(Collection<?> c) { // Difference
boolean modified = false;
Iterator<?> e = iterator();
while (e.hasNext()) {
    if (c.contains(e.next())) {
    e.remove();
    modified = true;
    }
}
return modified;
}

public boolean retainAll(Collection<?> c) { // Intersection
boolean modified = false;
Iterator<E> e = iterator();
while (e.hasNext()) {
    if (!c.contains(e.next())) {
    e.remove();
    modified = true;
    }
}
return modified;
}

上記の（明らかに高価な）操作をより速く実装または実行する方法はありますか？

たとえば、差や交差を計算する前にコレクションをソートすると、全体的なパフォーマンスが向上しますか?

これらの操作を使用するために(パフォーマンス的に)好ましいコレクションフレームワークのクラスはありますか?

4

4 に答える 4

1

AbstractCollectionこのレベルの抽象化では、コレクションについての知識がほとんどなく、利用可能な操作の数が非常に限られているため、これらの実装は非常に汎用的です。Collectionインターフェイスが許可するものだけが与えられ、コレクションの種類とその実装の詳細について何も知らない場合、これ以上賢いものを作ることは困難です。問題のコレクションのサイズとタイプに応じて、並べ替えが効果的である場合と効果的でない場合がありますが、このレベルではコードはそれを知ることができません。

于 2012-05-11T07:44:08.157 に答える
1

の javadoc を読むAbstractCollection:

変更不可能なコレクションを実装するには、プログラマーはこのクラスを拡張し、反復子の実装を提供するだけで済みます[...]

したがって、これらのメソッドのパフォーマンスを本当に理解するには、特定のクラスに対して Iterator がどのように実装されているかを確認する必要があると思います。

于 2012-05-11T07:45:47.113 に答える
1

はい、もっと速い方法があります。指定したコードは、e のすべての要素に対して c をループします。100 要素の 2 つの配列では、約 100,000 要素を比較します。

最初に両方の配列を並べ替えると、上位 2 つの要素を比較し続けるだけで済みます。これにより、数百回の比較が行われます。これはマージソートに似ています。leftソートされたコレクションとの交差を行うには、次のようにしrightます。

function intersect(left, right)
    var list result
    while length(left) > 0 and length(right) > 0
        if first(left) == first(right)
            append first(left) to result
            left = rest(left)
            right = rest(right)
        else if first(left) < first(right)
            left = rest(left)
        else
            right = rest(right)
    end while
    return result
于 2012-05-11T07:42:51.887 に答える
1

上記の（明らかに高価な）操作をより速く実装または実行する方法はありますか？

これらの操作の実際のコストは、引数として渡されたコレクションが contains() をどのように実装するかによって異なります。の場合はHashSet、contains一定の (予想される) 時間の操作であり、直線的な (予想される) 時間でremoveAllまたは完了します。retainAll

並べ替えはそれよりも費用がかかります。

集合操作が で行われたときに最も効率的であることは理にかなってSetいますね。

EnumSetコレクション内の要素が列挙型または密な整数である場合は、またはを使用して速度を上げることができますBitSet。

于 2012-05-12T01:22:17.370 に答える