Javaコレクションの差または交差を計算するパフォーマンス

Question

Javaでは、のremoveAll()およびretainAll()メソッドを使用して、2つのコレクションオブジェクトの(set theoretic) differenceおよびintersectionを計算することができます。

のJava 6のAbstractCollection classにおけるこれら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; 
} 

が速く上記（明らかに高価な）動作を実現または実行する任意の方法はありますか？

は例えば、相違点や交差点を計算する前にコレクションを並べ替えから任意の全体的なパフォーマンスの向上があるだろうか？

これらの操作を使用するのに好適コレクションフレームワーク（パフォーマンスワイズ）のいずれかのクラスがありますか？

Answer 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 

Answer 2

これらの実装はAbstractCollectionであり、したがって、彼らは非常に少し抽象化のこのレベルで収集し、利用可能な操作の数を知っているので、非常に一般的なものです非常に限られています。 Collectionインターフェイスで許可されているものだけを提供し、コレクションの種類と実装の詳細については何も知らないのは、もっとスマートにするのは難しいことです。ソートは、このレベルでコードが知ることができない、問題のコレクションのサイズとタイプによって効果的かどうかは関係ありません。だから、変更不可能なコレクションを実装するには

、プログラマだけ にこのクラスを拡張し、イテレータの実装を提供する必要があります[...]

私は：

Answer 3

AbstractCollectionのJavadocを読みます特定のクラスに対してIteratorがどのように実装されているかを確認し、それらのメソッドのパフォーマンスを実際に理解する必要があると考えてください。

Answer 4

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

これらの操作が実際にどれほど費用がかかるかは、コレクションがcontains（）の引数として渡された方法によって異なります。それはHashSetだ場合、containsは直線的に（予想される）時間を完了するために、removeAllまたはretainAllを引き起こし、一定の（予想される）時間操作です。

並べ替えが高価になります。

、よく、それはSetで行われたときに、設定された操作が最も効率的であることが合理的である、それはないですか？

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