10

パフォーマンスに関しては、次の使用に大きな違いはありますか?

  • ArrayList.contains(o) と foreach|iterator の比較
  • LinkedList.contains(o) と foreach|iterator の比較

もちろん、 foreach|iterator ループでは、メソッドを明示的に比較し、それに応じて true または false を返す必要があります。

私が比較しているオブジェクトは、equals()とhashcode()が両方とも適切にオーバーライドされているオブジェクトです。

編集:結局のところ、containsValue について知る必要はありません。申し訳ありません。そして、はい、私は愚かです.containsKeyとforeachに関する私の質問がどれほど愚かであるかに気づきました。それについては気にしないでください。私は基本的に上記のものについて知りたいです（他のものは編集されています）。

4

6 に答える 6

9

編集:

HashMap と TreeMap が含まれなくなった新しい形式の質問では、私の答えはまったく異なります。私は今ノーと言います。

他の人がこれに答えたと確信していますが、LinkedList と ArrayList の両方で、contains() は indexOf() を呼び出すだけで、コレクションを反復処理します。

LinkedList と ArrayList の間、および contains と foreach の間の両方で、わずかなパフォーマンスの違いがある可能性がありますが、大きな違いはありません。

于 2010-05-21T21:56:22.233 に答える
6

これは、contains(o) が indexOf(o) を呼び出し、次のように単純にループするため、違いはありません。

for (int i = 0; i < size; i++)
    if (o.equals(elementData[i]))
       return i;

(ArrayListでチェック)

于 2010-05-21T22:11:33.087 に答える
3

ベンチマークを行わない場合、contains はすべてのケースでより高速であるか同じである必要があります。

1 と 2 については、反復子メソッドを呼び出す必要はありません。内部でループする可能性があります。ArrayList と LinkedList の両方が、indexOf に関して contains を実装します。

  1. ArrayList - indexOf はバッキング配列の C スタイルの for ループです。
  2. LinkedList - indexOf は、リンクされたリストを C スタイルの for ループでウォークします。

3 と 4 については、containsKey と containsValue を区別する必要があります。

3.  HashMap、containsKey は O(1) です。キーをハッシュし、関連するバケットを取得してから、リンクされたリストをたどることによって機能します。containsValue は O(n) であり、ネストされた for ループ内のすべてのバケットのすべての値をチェックするだけで機能します。

4.  TreeMap、containsKey は O(log n) です。範囲内かどうかを確認し、赤黒木を検索します。O(n) である containsValue は、ツリーの順序付きウォークを使用します。

于 2010-05-21T21:55:58.057 に答える
2

ArrayList.contains は

return indexOf(o) >= 0;

どこ

public int indexOf(Object o) {
if (o == null) {
    for (int i = 0; i < size; i++)
    if (elementData[i]==null)
        return i;
} else {
    for (int i = 0; i < size; i++)
    if (o.equals(elementData[i]))
        return i;
}
return -1;
}

LinkedList の場合も同様ですが、.next() を使用して要素を反復処理するだけなので、大きな違いはありません。

public int indexOf(Object o) {
    int index = 0;
    if (o==null) {
        for (Entry e = header.next; e != header; e = e.next) {
            if (e.element==null)
                return index;
            index++;
        }
    } else {
        for (Entry e = header.next; e != header; e = e.next) {
            if (o.equals(e.element))
                return index;
            index++;
        }
    }
    return -1;
}

HashMap.containKey は、キーのハッシュを使用してそのハッシュ (高速) を持つすべてのキーを取得し、それらのキーに対してのみ equals を使用するため、改善されています。しかし、containsValue() は for を使用して値を調べます。

TreeMap.containsKey は、コンパレーターを使用して情報に基づいた検索を行い、キーをより速く見つけるように見えるので、さらに優れています。しかし、値が見つかるまで、containsValue は 3 つ全体を通過しているようです。

全体として、毎回ループを実行するよりも書きやすいので、メソッドを使用する必要があると思います:)。

于 2010-05-21T22:10:26.910 に答える
0

一般に、ライブラリの実装は同じものを手動で実装するよりも効率的であるため、contains を使用する方が良いと思います。オブジェクトの構築中または後で、カスタム equals とハッシュコードの実装を処理する、作成したコンパレータ メソッドを渡すことができるかどうかを確認してください。

ありがとう、クリシュナ

于 2010-05-21T21:58:14.187 に答える
0

foreach/iterator を使用したコンテナーのトラバースは、常に O(n) 時間です。ArrayList/LinkedList 検索も O(n) です。

HashMap.containsKey() は O(1)償却時間です。

TreeMap.containsKey() は O(log n) 時間です。

HashMap と TreeMap の両方で、containsValue() は O(n) ですが、containsValue() が containsKey() と同じくらい高速になるように最適化された実装があるかもしれません。

于 2010-05-21T22:06:03.990 に答える