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

Question

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 1

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.