4

2 つのセットが与えられた場合: Java でそれらを効率的に比較する方法は?

  • (a) それらをLists として保持し、並べ替えて比較します。( Comparable)
  • (b) それらを s として保持し、セットSetの を比較しますか?hashCode

バックグラウンド：

多くの比較を行う必要がある セットは小さい (通常、セットあたり < 5 要素)。

4

4 に答える 4

9

2 つのセットを比較する適切な方法は、 メソッドを使用するequalsことです。これがパフォーマンスの問題を引き起こしているコードの一部であることが証明されない限り、パフォーマンスについて心配することはありません (私は疑います)。セットのサイズ (5 要素) を考慮すると、これは非常に高速です (おそらくサブミリ秒)。

それらをリストとして保持し、並べ替えて比較します。（同程度の）

要素をコピーし、並べ替えて比較する必要があるため、確かに遅くなります。

それらをセットとして保持し、セットのハッシュコードを比較しますか?

2 つのセットが等しい (同じ内容を持っている) 場合、それらは同じハッシュコードを持ちます。逆数は当てはまりません。コンテンツが異なる 2 つのセットが同じハッシュコードを持つ場合があります。またHashSet、たとえば a の場合、ハッシュコードはすべての要素を反復することによって計算されるため、無料の操作ではないことに注意してください。

于 2012-11-13T12:27:38.667 に答える
2

equalsの何が問題になってい ますか? ドキュメントには、両方が同じサイズの場合containsAll()に true を返すと記載されており、true を返す場合、私にはかなり効率的に聞こえます。

いずれにせよ、ハッシュコードを比較して等しいかどうかをテストしないでください。2 つの異なるオブジェクトが同じハッシュコードを持つ可能性があります。

更新:コメント (および assylias の回答) に記載されているように、ハッシュコードは等価テスト ロジックの一部として使用できます (異なるハッシュコードは異なるオブジェクトを意味しますが、その逆は意味しません)。上記の私の発言は、ハッシュコードだけでは (一般的に) 十分ではないことを意味します。

于 2012-11-13T12:27:29.873 に答える
0

の要素set1 がまったく同じかどうかを比較したいとしますset2。

set1.equals(set2)またset2.equals(set1)、両方がまったく同じであることを確認します。

于 2012-11-13T12:50:14.120 に答える
0

2 つのがある場合、 1 つのセットのみを反復する必要があるためHashSet、それらを比較すると O(n) になり、もう 1 つのセットはそれ自体が O(1) である によってチェックされます。Set.equalscontains

あなたのような小さなセットの場合、O(n) と O(n 2 ) の差はごくわずかであるため、最も単純なアプローチでも優れたパフォーマンスが得られることに注意してください。

于 2012-11-13T12:50:18.523 に答える