Efficient way of comparing two arraylists in order to retain a delta between them

Question

Here's the problem that I have:

I need to compare two ArrayLists and return if they are the same or if they are different, return the elements that are new from one of them, the pivot so to speak.

Here's the behaviour of the data-set:

• the two ArrayLists are made of Strings
• they're populated from the same source so are most of the time the same
• are ordered (in the sense of the custom logic attached to them)
• there will never be any empty Strings
• all of the Strings have the same length, always
• no duplicates

What I want:

• the fastest possible way of achieving my two goals, whichever the case
• using only Java 1.6 standard library features, I'd prefer not to implement a hybrid class that emulated something from List and then Set for example.

Example:

A: [ 'a', 'b', 'c', 'd']   

B: [ 'a', 'c', 'd']

Result: Lists are different, return the element 'b'; A will be the 'work' List, we will make comparisons based on what's new in this ArrayList, since B will never change.

Thanks for any replies and your input.

Answer 1

Your fastest possible requirement bothers me a lot--I'm quite against optimizing--I generally consider early optimization one of the worst programming practices around.

If you really want to do that, just walk the two lists in order.

if the first entries match, you put that one into a "Same" pile and increment both indexes. If they are different, put the first (lower/less-than) one into a "Different" pile and increment that lists index. Loop this way until you hit the end of one list (any remaining in the other obviously go into the "Different" collection.

That should give you "close" to the fastest way. If you want the absolute fastest then you have to start by using arrays, not lists, and then pay a lot of attention to what else you do every step of the way--but the algorithm should still be pretty close to optimal.

As an example of sub-optimal but much more readable you could use some set manipulation.

Set set1=new HashSet(list1)
Set set2=new HashSet(list2)
Set same=set1.retainAll(set2) // I forget if retainAll modifies set1--if so you need to copy it first
set1.removeAll(list2)
set2.removeAll(list1)
Set different=set1.addAll(set2)

// at this point same contains all the similar values and different contains the ones that don't match.  Done.

This is short and readable and probably more performant than you would think. It would be bad practice to code your own if something like this works well enough (Say, in GUI code where speed is unlikely to matter).

Answer 2

Pretty simple (assuming the list is ordered ascending, can be easily changed for descending order):

ArrayList<String> delta(ArrayList<String> a , ArrayList<String> b , Comparator<String> comp){
    if(a.isEmpty())
        return new ArrayList(b);
    if(b.isEmpty())
        return new ArrayList(a);

    Iterator<String> it_a = a.iterator();
    Iterator<String> it_b = b.iterator();

    ArrayList<String> delta = new ArrayList<>();

    String a_s = it_a.next() , b_s = it_b.next();
    boolean onechecked = false;

    while(!onechecked){
        int comp_v = comp.compare(a_s , b_s);

        if(comp_v == 0){
            //strings are equal -> ommit them
            if(it_a.hasNext())
                a_s = it_a.next();
            else
                onechecked = true;

            if(it_b.hasNext())
                b_s = it_b.next();
            else
                onechecked = true;
        }else if(comp_v < 0){
            //a_s is not part of b
            delta.add(a_s);
            if(it_a.hasNext())
                a_s = it_a.next();
            else
                onechecked = true;
        }else{
            //b_s is not part of a
            delta.add(b_s);
            if(it_b.hasNext())
                b_s = it_b.next();
            else
                onechecked = true;
        }
    }

    //add remaining items
    delta.add(it_a.hasNext() ? a_s : b_s);

    for(Iterator<String> it = (it_a.hasNext() ? it_a : it_b) ; it.hasNext();)
        delta.add(it.next());

    return delta;
}

Sorry for not adding any explanation, but the code has to speak for itself, since i have no idea how to explain it.