Effizienter Weg, um herauszufinden, ob zwei sortierte Listen das gleiche Element Java enthalten.

Question

Ich habe eine enge Schleife, die Koprime sucht. Eine Liste primeFactors. Ihr n-tes Element enthält eine sortierte Liste der Hauptzerlegung von n. Ich überprüft, ob c und d sind coprimes 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)) sieht vielversprechend aus verwenden, aber es wird mein wiederverwendbar primeFactors Objekt verändern.

Das Erstellen eines neuen Objekts ist relativ langsam. Gibt es eine Möglichkeit, diesen Schritt zu beschleunigen? Kann ich irgendwie die Tatsache ausnutzen, dass Listen sortiert sind? Soll ich stattdessen Arrays verwenden?

Answer 1

Set-Operationen sollten schneller sein als Array-Operationen. Just for Kicks, halten dies versuchen und die Leistung gegen den Strom Leistung vergleichen:

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()); 

Bedenken Sie auch List<Set<Integer>> primeFactors statt List<List<Integer>> primeFactors verwenden, da ich, dass Sie vermuten, dass dies nicht tun wirklich eine Liste von Primfaktoren haben aber tatsächlich eine Reihe von Primfaktoren haben.

Answer 2

Normalerweise können Sie ein boolesches Array verwenden. Wobei der Index des Arrays die Zahl ist und der Wert des Booleschen Wertes true zurückgibt, wenn es ein Prim ist, andernfalls false.

Answer 3

Sie könnten eine Collection mit schnellerer Suche verwenden - z. a Set Wenn Sie nur die Primfaktoren ohne Wiederholungen benötigen oder eine Map, wenn Sie auch die Anzahl der einzelnen Faktoren benötigen.

Grundsätzlich möchten Sie wissen, ob die Schnittmenge von zwei Sets leer ist. Oracle Set tutorial zeigt eine Möglichkeit zur Berechnung des Schnittpunkts (ähnlich dem, was Sie bereits erwähnt haben, wobei retainAll auf einer Kopie verwendet wird, aber auf Sets sollte die Operation effizienter sein).

Answer 4

Sie könnten etwas entlang der Linien von tun:

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

Sobald Sie diese Leistung messen, können Sie ‚parallelStream()‘ für ‚Strom()‘ oben und sehen Sie ersetzen, welche Vorteile Sie ableiten.

Answer 5

Da Ihre Listen relativ klein sind und diese Operation sehr oft ausgeführt wird, sollten Sie es vermeiden, neue Listen oder Sets zu erstellen, da dies zu einem erheblichen GC-Druck führen kann.

Der Scan-lineare Algorithmus ist

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); 
     } 
    } 
} 

auch statt boxed ganzen Zahlen, e mit Listen von primitiven int s betrachten. G. von fastutil Bibliothek.