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.

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

Sign up