14

2つのArrayList同じデータ構造（hashCode（）とequals（）がオーバーライドされています）があります。Cは学生の記録を表します。2つのリストは同じサイズで、それぞれ新しい学生の記録と古い記録を表しています（学生は両方のリストで同じであり、順序が異なる場合があります）。変更されたAのレコードのみを保持したいと思います。そういうものとして、私はします：ABC

 A.removeAll(B)

javadocsによると、これはAの各レコードを取得し、Bの各レコードと比較し、両方が等しい場合はAからレコードを削除します。AのレコードがB、そしてAのすべての学生もBにいるので、それはAのその記録が変更されたことを意味します。問題は、簡単にn平方の複雑さになることです。

別のアプローチは次のとおりです。

Map<C> map = new HashMap<C>();
for (C record : B){
    map.add(record.getStudentId(),record);
}
List<C> changedRecords = new ArrayList<C>();
for (C record : A){
    if (record.equals(map.get(record.getStudentId())){
        changedRecords.add(record);
    }
}

これは、上記のソリューションよりも複雑さが少ないと思います。あれは正しいですか ？

4

4 に答える 4

11

はい、後者のアルゴリズムは よりも優れO(n^2)ていBます.AO(|A| + |B|)

ただし、重複するエントリはないと思います。この場合は、次の手順を実行することもできます(順序を に保持する場合は にHashSet変更します):LinkedHashSetA

HashSet<C> tmp = new HashSet<C>(A);
tmp.removeAll(B);                     // Linear operation
A = new ArrayList<C>(tmp);

(または、順序が重要でない場合は、最後までHashSets を使用できます。)

以下のコメントで @Daud が指摘しているように、ハッシュ セットのサイズが複雑さに影響するコレクションよりも小さい場合 (少なくとも OpenJDK では) 、HashSet.removeAll(Collection c)実際には繰り返し呼び出されます。c.containsこれは、実装が常に小さいコレクションを反復処理することを選択するためです。

于 2012-04-03T07:29:30.510 に答える
1

メモリ割り当てで失う可能性のある複雑さを節約できるものは、必ずしもより効率的ではありません。Arraylist は、インプレース パーティショニング アルゴリズムに似たものを使用して、バッキング アレイを実行し、比較に対してテストします。

比較するときは、バッキング配列に対して最初に一致したインデックスを見つけようとしますObject[]。アルゴリズムは 2 つのインデックスを維持します。1 つはバッキング配列を反復処理するためのもので、もう 1 つは一致のプレースホルダーとしてのものです。一致した場合は、バッキング配列のインデックスを移動し、次の着信要素に進みます。これは比較的安いです。

着信コレクションにバッキング配列の現在のインデックスの値が含まれていないことが判明した場合、新しいメモリ割り当てを発生させることなく、最後に一致した要素を現在のインデックスの要素で単純に上書きします。 . このパターンは、ArrayList 内のすべての要素が着信コレクションと比較されるまで繰り返されるため、懸念される複雑さになります。

例: 1,2,4,5 の配列リスト A と、照合対象の 4,1 のコレクション 'C' を考えてみましょう。4 と 1 を削除したい場合。ここでは、0 -> 4 になる for ループの各反復を示します。

反復: r は、arraylist a の for ループ インデックスです。for (; r < size; r++)

r = 0 (C には 1 が含まれていますか? はい、次へスキップします) A: 1,2,4,5 w = 0

r = 1 (C には 2 が含まれますか? いいえ、r の値を w++ が指す場所にコピーします) A: 2,2,4,5 w=1

r = 2 (C には 4 が含まれていますか? はいスキップ) A: 2,2,4,5 w=1

r = 3 (C には 5 が含まれていますか?いいえ、r の値を w++ が指す場所にコピーします)

A: 2,5,4,5 w=2

r=4、ストップ

w をバッキング配列のサイズである 4 と比較します。これらは等しくないため、w から配列の末尾までの値を Null アウトし、サイズをリセットします。

A: 2,5 サイズの 2

組み込みの removeAll も、ArrayLists に null を含めることができると見なします。上記のソリューションでは、record.getStudentId() で NPE をスローできます。最後に、removeAll は Collection.contains の比較で例外から保護します。その場合、finally を使用してネイティブの memcopy を実行し、非常に効率的な方法でバッキング アレイを破損から保護します。

于 2012-04-03T09:44:49.387 に答える
1

一部のインスタンス (EMF モデルの操作に関連) で、メンバー removeAll でパフォーマンスのボトルネックが発生しました。ArrayList上記のように、標準を使用するだけですが、たとえばremoveAllA が EList の場合、n^2 が発生する可能性があります。

したがって、特定の実装の隠れた優れた特性に依存することは避けてくださいList< T >。Set.contains()O(1) は保証です (a を使用しHashSet、適切な hashCode をTreeSet使用し、順序付け関係に log2(n) を使用する場合)、それを使用してアルゴリズムの複雑さを制限します。

無駄なコピーを避ける次のコードを使用します。意図は、データ構造をスキャンして、不要な要素を見つけて「todel」に追加することです。

同時変更を回避する、ツリーをナビゲートするなどの何らかの理由で、このトラバーサルを行っているため、要素を削除できません。したがって、それらを HashSet "todel" に累積します。

関数では、通常は呼び出し元の属性であるため、「コンテナー」をその場で変更する必要がありますが、「コンテナー」で remove(int index) を使用すると、要素の左シフトが原因でコピーが発生する可能性があります。これを実現するために、コピー「コンテンツ」を使用します。

テンプレートの引数は、選択プロセス中に C のサブタイプを取得することが多いためですが、どこでも自由に < T > を使用できます。

/**
 * Efficient O (n) operation to removeAll from an aggregation.
 * @param container a container for a set of elements (no duplicates), some of which we want to get rid of
 * @param todel some elements to remove, typically stored in a HashSet.
 */
public static <T> void removeAll ( List<T> container, Set<? extends T> todel ) {
    if (todel.isEmpty())
        return;
    List<T> contents = new ArrayList<T>(container);
    container.clear();
    // since container contains no duplicates ensure |B| max contains() operations
    int torem = todel.size();
    for (T elt : contents) {
        if ( torem==0 || ! todel.contains(elt) ) {
            container.add(elt);
        } else {
            torem--;
        }
    }
}

したがって、あなたのケースでは、次のように呼び出します:removeAll(A, new HashSet < C >(B)); 選択フェーズ中に Set< C > に実際に蓄積できない場合は、 B の 1 つのコピーを支払います。

使いやすいように、ユーティリティ クラスと静的インポートに配置します。

于 2015-07-01T19:07:07.367 に答える
1

間違いなく 2 番目の「アルゴリズム」は、償却分析を考慮すると最初のアルゴリズムよりも優れています。それは最善の方法ですか？あなたはそれが必要ですか？パフォーマンスに関してユーザーに目に見える影響を与えますか? リスト内のアイテムの数が非常に多くなり、システムのボトルネックになりますか?

最初のアプローチはより読みやすく、コードを保守する人々にあなたの意図を伝えます。また、車輪を再発明する代わりに「テスト済み」の API を使用することをお勧めします (絶対に必要な場合を除きます)。

不可欠と思われる場合は、@aioob のような Set を使用したソリューションを使用する可能性があります

于 2012-04-03T11:03:40.227 に答える