2つのソートされたリストに同じ要素のJavaが含まれているかどうかを調べる効率的な方法。

Question

私は、冗談を検索するタイトなループを持っています。リストprimeFactors。そのn番目の要素には、nの素数分解のソートされたリストが含まれています。 cとdは有望に見えるが、それは私の再利用可能なprimeFactorsオブジェクトを変更しますcheckIfPrimes

boolean checkIfPrimes(int c, int d, List<List<Integer>> primeFactors) { 
    List<Integer> common = new ArrayList<>(primeFactors.get(d)); //slow 
    common.retainAll(primeFactors.get(c));   
    return (common.isEmpty()); 
} 

primeFactors.get(d).retainAll(primeFactors.get(c))を使用してcoprimesある場合、私はチェックしています。

新しいオブジェクトの作成は比較的遅いです。このステップをスピードアップする方法はありますか？リストがソートされているという事実を何とか利用することはできますか？代わりに配列を使うべきですか？

Answer 1

設定操作は配列操作よりも速くなければなりません。 だけキックのために、これをしようと考えると、ストリームのパフォーマンスに対するパフォーマンスを比較：私はあなたが 本当に素因数のリストを持っていないと思われるので、

final Set<Integer> commonSet; 
final Set<Integer> cSet = new HashSet<Integer>(); 
final Set<Integer> dSet = new HashSet<Integer>(); 

cSet.addAll(primeFactors.get(c)); 
dSet.addAll(primeFactors.get(d)); 

commonSet = dSet.retainAll(cSet); 

return (commonSet.isEmpty()); 

はまた、 ではなくList<List<Integer>> primeFactorsのList<Set<Integer>> primeFactors を使用することを検討してください実際にはプライムファクタのセットを持っています。

Answer 2

通常、ブール値配列を使用できます。配列のインデックスが数値でブール値がtrueの場合は、それ以外の場合はfalseを返します。

Answer 3

Collectionを使用すると、より高速な検索が可能です。繰り返しなしで素因数のみが必要な場合はSet、各要素の数も必要な場合はMapが必要です。

基本的に、2つのセットの交差が空であるかどうかを知りたいとします。 Oracle Set tutorialは交差点を計算する方法を示しています（すでに述べたものに似ていますが、コピー上でretainAllを使用しますが、操作がより効率的になるように設定してください）。

Answer 4

あなたはの線に沿って何かを行うことができます：あなたはこのパフォーマンスを測定したら、あなたは上のための「parallelStream（）」「（ストリーム）」を置き換えて、あなたが導き出すメリットかを見ることができます

List<Integer> commonElements = 
     primeFactors.get(d).stream() 
          .filter(primeFactors.get(c)::contains) 
          .collect(Collectors.toList()); 

を。

Answer 5

リストが比較的小さく、この操作は非常に頻繁に実行されるため、新しいリストやセットを作成することは避けてください。これはGCの重要な圧力につながる可能性があるためです。

スキャン線形アルゴリズムは

public static boolean emptyIntersection(List<Integer> sortedA, List<Integer> sortedB) { 
    if (sortedA.isEmpty() || sortedB.isEmpty()) 
     return true; 
    int sizeA = sortedA.size(), sizeB = sortedB.size(); 
    int indexA = 0, indexB = 0; 
    int elementA = sortedA.get(indexA), elementB = sortedB.get(indexB); 
    while (true) { 
     if (elementA == elementB) { 
      return false; 
     } else if (elementA < elementB) { 
      indexA++; 
      if (indexA == sizeA) 
       return true; 
      elementA = sortedA.get(indexA); 
     } else { 
      // elementB < elementA 
      indexB++; 
      if (indexB == sizeB) 
       return true; 
      elementB = sortedB.get(indexB); 
     } 
    } 
} 

はまた、箱入りの整数の代わりに電子をプリミティブint秒のリストを使用することを検討しています。 g。ライブラリfastutilから。