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 use a Collection with faster lookup - e.g. a Set if you only need the prime factors without repetitions, or a Map if you also need the count of each factor.

Basically, you want to know whether the intersection of two Sets is empty. Oracle Set tutorial shows a way to calculate the intersecton (similar to what you already mentioned, using retainAll on a copy, but on Sets the operation should be more efficient).

Answer 2

Since your lists are relatively small, and this operation is executed very often, you should avoid creating any new Lists or Sets, because it might lead to a significant GC pressure.

The scan linear algorithm is

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

Also consider using lists of primitive ints instead of boxed integers, e. g. from fastutil library.