2

今日のコーディング中にcontainsAll()（インターフェースメソッド）を発見しましたが、かなり滑らかに見えます。Listパフォーマンス/反復の観点から、これにどれだけの費用がかかるか知っている人はいますか?

ドキュメントはそれに関してあまり提供しませんでした。

4

4 に答える 4

3
  • 最初に、提供されたコレクションの各要素を反復します
  • 次に、リストのすべての要素を繰り返し、現在の要素とそれらを比較します.equals(..)（注：質問で指定したように、これはリストに関するものです。他のコレクションの動作は異なります）

つまり、O(n*m) です。ここで、n と m は両方のコレクションのサイズです。

public boolean containsAll(Collection<?> c) {
    Iterator<?> e = c.iterator();
    while (e.hasNext())
        if (!contains(e.next()))
        return false;
    return true;
}
于 2012-04-17T21:59:46.123 に答える
3

ソースを使用してください、ルーク:)

編集：Bozhoが指摘したように、あなたはList.containsAll()どのオーバーライドについて尋ねていますCollection.containsAll()。次のとりとめのないことは、主に後者に関係しています。

ほとんどのCollectionクラスはfromの実装をcontainsAllAbstractCollection使用します。これは次のようになります。

public boolean containsAll(Collection<?> c) {
    for (Object e : c)
        if (!contains(e))
            return false;
    return true;
}

ただし、一部の実装が完全に異なる動作をするという保証はありません。実行時の動作が良くなったり悪くなったりする可能性があります。

上記の の実装はcontainsAll、少なくとも O(n) になります。ここで、n は、渡すCollectionパラメーター内のアイテムの数と、それにかかる時間を加えたものです。contains

  • HashSet/の場合、HashMapこれは O(1) (最良の場合、衝突なし) になる可能性があるため、全体の実行時間containsAllは依然として O(n) になります。
  • の場合、ArrayListはcontainsO(m) かかります。ここで、m はリスト内の項目数 (パラメーターではありません) であるため、全体の時間はcontainsAllO(n*m) になります。
于 2012-04-17T22:00:01.883 に答える
1

A.containsAll(B) を呼び出している場合

openjdk は、A.contains(b) を呼び出して B のすべての要素を繰り返します。

A.contains(b) は、a.equals(b) を呼び出して A のすべての要素を反復します。

これは、 open jdk 7のソースから取得したものです。

于 2012-04-17T22:04:08.717 に答える
0

検討

n.ContainsAll(m)

考えられる最善のシナリオは O(m) であり、それは n が完全なハッシュ セットである場合です。

ソートされていないリストを考慮すると、O(n*log(n) + m*log(m)) アルゴリズムを考え出すことができます

于 2012-04-17T22:01:03.457 に答える