他のarraylistから1つのarraylist要素を削除する最も良い方法

Question

integer要素を別のものから削除するためのJava（7,8）の中で最高のパフォーマンスメソッドは何ですか？すべての要素は、1番目と2番目のリストで一意です。私はAPIメソッドremoveallを知っているし、それをこのように使う瞬間

：

tempList.removeAll(tempList2); 

問題は、私はで動作するときのArrayListが10000個のを超える要素を持って表示されます。たとえば、65000要素を削除すると、遅延は約2秒に見えます。しかし、私は1000000以上の要素を持つさらに大きなリストを必要とします。

この問題の戦略は何ですか？

新しいStream APIで何か問題が解決するはずですか？

Answer 1

TL; DR：

はそれをシンプルに保ちます。代わりに

list.removeAll(new HashSet<T>(listOfElementsToRemove)); 

を使用してください。低パフォーマンスは、一般的なremoveAll実装の擬似コードが

public boolean removeAll(Collection<?> c) { 
    for (each element e of this) { 
     if (c.contains(e)) { 
      this.remove(e); 
     } 
    } 
} 

だから、リスト上で行われるcontains呼び出しであることに起因：エランはすでにhis answerで述べたように

---

削除する要素によって、O（n * k）のパフォーマンスが発生します（ここで、nは削除する要素の数、kはメソッドが呼び出されるリストの要素の数です）。

Listのthis.remove(e)コールもO（k）を持つ可能性があり、この実装もまた2次的な複雑さを持つと想像することができます。しかし、これは事実ではありません：リストは具体的にはArrayListのインスタンスであると述べました。そして、ArrayList#removeAllメソッドは、基本配列で直接動作するbatchRemoveというメソッドに委譲するために実装され、ではなく、が要素を個別に削除します。

削除する要素を含むコレクション内のルックアップが高速であることを確認するだけです（できるだけO（1）が望ましい）。これは、これらの要素をSetに入れることで実現できます。これは、まず第一に、それはリストを並べ替えが必要です。

エランによって答えは私見二つの大きな欠点がある。最後に、ちょうど

list.removeAll(new HashSet<T>(listOfElementsToRemove)); 

---

サイドノートとして書き込むことができますO（n * logn）です - それは単に必要ではありません。しかし、もっと重要なのは（明らかに）：ソートすると要素の順序が変わる可能性が高いです！これは単に望ましくない場合はどうすればよいですか？

遠隔関連：removeAllの実装にはいくつかの微妙な点があります。たとえば、HashSet removeAll method is surprisingly slowなどです。削除される要素がリストに格納されている場合、これもO（n * n）になってしまいますが、この特定のケースでは実際の動作が驚くかもしれません。

Answer 2

よく、それはtempList2に表示するかどうかtempListの各要素のremoveAllチェックするため、実行時間が2つのリストのいずれかがない限りO(N^2)を意味第二のリストのサイズを掛けた最初のリストの大きさに比例します非常に小さく、「一定のサイズ」と考えることができます。

一方、リストをあらかじめソートしてから、両方のリストを1回の繰り返しでマージソートのマージステップと同じように反復すると、並べ替えはO(NlogN)となり、繰り返しはO(N)となります。合計実行時間はO(NlogN)です。ここではNは2つのリストのうち大きい方のサイズです。

リストをソートされた構造体（おそらくTreeSet）と置き換えることができる場合は、並べ替えを行う必要がないため、線形時間でremoveAllを実装できます。

（tempListとtempList2ソートされているの両方を想定して）私はそれをテストしていませんが、このような何かが動作することができます：

Iterator<Integer> iter1 = tempList.iterator(); 
Iterator<Integer> iter2 = tempList2.iterator(); 
Integer current = null; 
Integer current2 = null; 
boolean advance = true; 
while (iter1.hasNext() && iter2.hasNext()) { 
    if (advance) { 
     current = iter1.next(); 
     advance = false; 
    } 
    if (current2 == null || current > current2) { 
     current2 = iter2.next(); 
    } 
    if (current <= current2) { 
     advance = true; 
     if (current == current2) 
      iter1.remove(); 
    } 
} 

Answer 3

私はArrayListのから削除する疑いがある、リスト以来perfromanceヒットであるかもしれないいずれか中間の要素が削除されたとき、または要素が削除された後にリストを圧縮する必要がある場合に分割されます。

あなたは建設でそれに十分な大きさを与えることができR.それを呼び出す、あなたが必要とする新しい結果のArrayListを作成を削除する要素の「SET」を作成

1. ：それはこれを行うには速いかもしれません。
2. 要素を削除する必要がある元のリストを繰り返し、要素がセットに見つかった場合はそれをRに追加しません。そうでない場合は追加します。

これはO(N)である必要があります。セットを作成してルックアップを定数にすると仮定します。