sixtytrees sixtytrees - 4 months ago 9
Java Question

Efficient way to find out if two sorted lists contain same element Java.

I have a tight loop that searches coprimes. A list

primeFactors
. Its n-th element contains a sorted list of prime decomposition of n. I am checking if
c
and
d
are coprimes using
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))
looks promising, but it will alter my reusable
primeFactors
object.

Creating a new object is relatively slow. Is there a way to speed up this step? Can I somehow utilize the fact that lists are sorted? Should I use arrays instead?

Answer

You could do something along the lines of:

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

Once you measure this performance, you can substitute 'parallelStream()' for 'stream()' above and see what benefits you derive.