多くのリストの共通要素をチェックする最適な方法は？

Question

私はArrayList<>年代は（O(1)対O(n)）を検索するための最速であり、LinkedList<>年代は&削除（O(1)対O(n)）を挿入するための最速であることを理解しています。

私の質問は、これら2つの組み合わせを使用する場合、共通の要素に対して多くのリスト（> 2）をチェックする最適な方法は何ですか？

電流法 3つのリストを使用して と反復法は：

out: 
for(int a = 0; a < list1.size(); a++) { 
    for(int b = 0; b < list2.size(); b++) { 
     for(int c = 0; c < list3.size(); c++) { 
      if(list1.get(a) == list2.get(b) && list1.get(a) == list3.get(c)) { 
       System.out.println(list1.get(a)); // list2.get(b) or list3.get(c) could have been subbed 
       break out; 
      } 
     } 
    } 
} 

これは効率のために最適化することができますか？

---

EDIT多くの有用な応答のための

感謝:) 何が最適に動作することが判明すると、一覧.retainAll()機能を使用することでした。

また、3つのリストの共通要素を見つけるために、以下の方法を改良しました。

list1.retainAll(list2); 
list1.retainAll(list3); 
for(int i : list1) { 
    System.out.println(i); 
} 

Answer 1

代わりretainAll(List<>)機能を使用する場合、

make hashmap h; 
    loop i=0 to m 
    loop j=0 to n 
     increment j[i] key in hashmap h 
    loop end 
    loop end 

loop i=0 to m for any list 
    check hashmap value for the element, if equals to n 
    print element 

複雑さO（NM）：あなたは、M個の要素それぞれ

アルゴリズムのnのリストを持っていると仮定 各要素の反復処理の実行時間が大幅に短縮され、可読性が向上しました。

新

list1.retainAll(list2); 
list1.retainAll(list3); 

旧

out: 
for(int a = 0; a < list1.size(); a++) { 
    for(int b = 0; b < list2.size(); b++) { 
     for(int c = 0; c < list3.size(); c++) { 
      if(list1.get(a) == list2.get(b) && list1.get(a) == list3.get(c)) { 
       System.out.println(list1.get(a)); 
       break out; 
      } 
     } 
    } 
} 

Answer 2

あなたは要素がhashCodeを実装すると仮定すると、すべてのリストの要素の数で予想時間の線形を取得することができます。

public static <T> Set<T> commonElements(List<? extends T> list1, List<? extends T>... lists) { 
    // use LinkedList for efficient delete operation 
    // make sure elements are distinct to not check the same element multiple times 
    List<T> commonElements = new LinkedList<>(new HashSet<>(list1)); 
    for (List<? extends T> l : lists) { 
     // use HashSet for fast contains check 
     // keep only elements in the list 
     commonElements.retainAll(new HashSet<>(l)); 
    } 
    return new HashSet<>(commonElements); 
} 

HashSetが期待O(1)で検索することができますので、これは、あなたのアプローチよりも高速です時間。

小さな入力リストの場合、この手法では、パフォーマンスが大幅に悪化する可能性があります。

Answer 3

javaのHashMapを使用して最適化することができます。 N < < < mは次に、複雑さ（N）

Answer 4

パフォーマンスを探しているなら、ハッシュルックアップを使用するAPIを書く方が良いでしょう。 list.retainAll（）は、単一のきれいなAPIコールですが、内部的には、特に引数が渡された場合にも処理が多くなります。ここでは、配列リストの）のretainAll（の実装を見てみましょう -

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/ArrayList.java#ArrayList.retainAll%28java.util.Collection%29

あなたが使用しているリストの実装を見て、それがあなたの性能要件で大丈夫であるかどうかを確認することができます。そうでない場合は、次のようなことを試してみてください...共通要素を返すAPIを作成します。

private static Set getCommonElements (List dataList, Set dataSet) { 
    Set commonDataSet = new LinkedHashSet(); 

    if (dataSet == null || dataSet.isEmpty()) 
     return commonDataSet; 

    for (Object elem: dataList) { 
     if (dataSet.contains(elem)) {//Hash based look up. Will be faster. 
      commonDataSet.add(elem); 
     } 
    } 

    return commonDataSet; 
} 

次にあなたが順序を懸念していない場合は、繰り返し

Set resultSet= new LinkedHashSet(list1); 
resultSet= getCommonElements(list2, resultSet); 
resultSet= getCommonElements(list3, resultSet); 

以下のように、あなただけの代わりにLinkedHashSetののHashSetのを使用できることを呼び出します。

この問題の1つは、list内の要素が共通要素よりも高い要素を反復処理することです。共通の要素を繰り返し処理してリストを参照することができれば、はるかに良いでしょう。しかし、そのためには、リスト内のデータをハッシュ・ベイク・リスト/セットで保持するか、ソート・リストを維持する必要があります。それ以外の場合、検索にはコストがかかるでしょう。