An effective way to find out if two sorted lists contain the same Java element.

Question

I have a complex loop that is looking for matches. primeFactors List. Its nth element contains a sorted list of simple decompositions of n. I check if c and d checkIfPrimes 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 change my reusable primeFactors object.

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

Answer 1

Set operations must be faster than array operations. Just for the bumps, try this and compare the performance with the flow performance:

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

Also, consider using List<Set<Integer>> primeFactors instead of List<List<Integer>> primeFactors , as I suspect you don't really have a list of simple factors, but actually have a set of simple factors.

Answer 2

You can use Collection with faster searches - for example. a Set if you need only simple coefficients without repetition, or Map if you also need a counter for each factor.

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

Answer 3

Since your lists are relatively small, and this operation is performed very often, you should avoid creating any new lists or sets, as this can lead to significant GC pressure.

Linear scanning algorithm

 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 int instead of integers in a block, e. d. from fastutil library.

Answer 4

You can usually use a boolean array. Where the array index is the number and value of the logical returns true when it is prim otherwise false .

Answer 5

You can do something line by line:

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

Once you measure this performance, you can replace "parallelStream ()" with "stream ()" above and see what benefits you get.