Skuteczny sposób sprawdzenia, czy dwie posortowane listy zawierają ten sam element Java.

Question

Mam ciasną pętlę, która wyszukuje coprimes. Lista primeFactors. Jej n-ty element zawiera posortowaną listę pierwotnego rozkładu n. Jestem sprawdzenie czy c i d są coprimes użyciu 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)) wygląda obiecująco, ale to zmienia mój wielokrotnego użytku primeFactors obiekt.

Tworzenie nowego obiektu odbywa się stosunkowo wolno. Czy istnieje sposób na przyspieszenie tego kroku? Czy mogę w jakiś sposób wykorzystać fakt, że listy są sortowane? Czy zamiast tego powinienem używać tablic?

Answer 1

Operacje ustawiania powinny być szybsze niż operacje na tablicach. tylko dla zabawy, za trudny to i porównać skuteczność przeciwko wykonywaniu strumieniowe:

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

Również rozważyć użycie List<Set<Integer>> primeFactors zamiast List<List<Integer>> primeFactors ponieważ podejrzewam, że nie naprawdę mieć listę czynniki pierwsze ale w rzeczywistości mają szereg czynników pierwszorzędnych.

Answer 2

Zwykle można użyć tablicy boolowskiej. Gdzie indeksem tablicy jest liczba, a wartość wartości logicznej zwraca true, gdy jest ona pierwotna, w przeciwnym wypadku, false.

Answer 3

Można użyć numeru Collection z szybszym wyszukiwaniem - np. Set, jeśli potrzebujesz tylko czynników głównych bez powtórzeń lub Map, jeśli potrzebujesz również liczby każdego czynnika.

Zasadniczo chcesz wiedzieć, czy przecięcie dwóch zestawów jest puste. Oracle Set tutorial pokazuje sposób obliczania przecięcia (podobnego do tego, co już wspomniano, przy użyciu retainAll na kopii, ale w Ustawieniach operacja powinna być bardziej wydajna).

Answer 4

Można zrobić coś wzdłuż linii:

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

Po mierzyć tę skuteczność, można zastąpić „parallelStream()” dla „strumienia()” powyżej i zobacz, jakie korzyści czerpać.

Answer 5

Ponieważ Twoje listy są stosunkowo małe, a operacja ta jest wykonywana bardzo często, powinieneś unikać tworzenia nowych list lub zestawów, ponieważ może to prowadzić do znacznego ciśnienia GC.

Algorytm liniowego skanowania

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

również rozważyć użycie list prymitywnych int s zamiast pudełkowych liczb całkowitych, np. sol. z biblioteki fastutil.