Carlos Luis Carlos Luis - 5 months ago 20
Java Question

Implementing the difference between two sorted Lists of comparable items in java

Implement a method in Java to compute the difference () between L1 and L2. L1 \ L2 = { x | x ∈ L1 and x ∉ L2 }.

This is my implementation so far:

public static <AnyType extends Comparable<? super AnyType>>
void difference(List<AnyType> L1, List<AnyType> L2, List<AnyType> Difference){

if(L1 == null){
Difference = null;
}
else if(L2 == null){
Difference = L1;
}
else if(L1.size()==0 || L2.size()==0){
Difference = L1;
}
else{
Iterator<AnyType> it1 =L1.listIterator();
Iterator<AnyType> it2 =L2.listIterator();

AnyType a = it1.next();
AnyType b = it2.next();

while(true){
if(a.compareTo(b)>0){
if(it2.hasNext()){
b = it2.next();
}
else{
Difference.add(a);
while(it1.hasNext()){
a = it1.next();
Difference.add(a);
}
break;
}
}
else if(a.compareTo(b)<0){
Difference.add(a);
if(it1.hasNext()){
a = it1.next();
}
else break;
}
else {
if(it1.hasNext()){
a =it1.next();
}
else break;
}
}
}
System.out.println("Difference Set: " + Arrays.toString(Difference.toArray()));
}



This is not the trivial solution which would be to implement two nested for loops and save to the result list the right elements, that solution is O(n^2).

Another possible solution is to search the second list using binary search, that algorithm would be O(n*Log(n))


The solution here implemented, attempts to go through the lists only once and finish in the first pass, this will be O(n) linear.

The algorithm works fine, however it feels like it could use some optimization still, it feels like spaghetti code lol. Any pointers that could help me to optimize this?

Answer

The first thing I see is that you perform a.compareTo(b) twice for each iteration through the loop. Instead, use compareTo once and store the result for use in both if statements.

Secondly, use for a consistent naming scheme like objA and iterA instead of a and it1. It'll just make it a little easier to follow. For that matter, don't be afraid of longer names. listA than l1 might be a couple extra characters, but it's worth it for readability. (Also, don't forget that you shouldn't start a variable with a capital letter, so L1 is doubly-uncool.)

Finally, comment comment comment. I know this algorithm, so I can follow the code pretty well, but it's far from self-documenting. Comment each if statement and loop to document what the condition is, why you're checking, and what you're doing with the results.

Comments