Splitting two lists into OnlyA, Both, and OnlyB

Question

This is a part of my Minesweeper analyzer code that didn't fit into the last question.

This code uses FieldGroup which extends ArrayList because I am using some more data than just the elements themselves.

I am mostly wondering: Can any simplifications be made in the split method? Even though the current code is fast enough, I am wondering if it can be optimized further.

The idea is to split two FieldGroups (A and B) into three parts:

• onlyA: Elements that exists in A but not in B
• both: Elements that exists in both A and B
• onlyB: Elements that exists in B but not in A

The reason for why I am using List instead of Set is that I want the capability to have multiple equal elements. The order does not matter of the elements. I am aware of Guava's MultiSet but I'm not a big fan of introducing a dependency in this code.

For testing purposes the FieldGroup class can be as follows:

class FieldGroup<T> extends ArrayList<T> {
}

public class FieldGroupSplit<T> {

    private final FieldGroup<T> onlyA;
    private final FieldGroup<T> both;
    private final FieldGroup<T> onlyB;

    private FieldGroupSplit(FieldGroup<T> onlyA, FieldGroup<T> both, FieldGroup<T> onlyB) {
        this.onlyA = onlyA;
        this.onlyB = onlyB;
        this.both = both;
    }

    public FieldGroup<T> getBoth() {
        return both;
    }

    public FieldGroup<T> getOnlyA() {
        return onlyA;
    }

    public FieldGroup<T> getOnlyB() {
        return onlyB;
    }

    public boolean splitPerformed() {
        return !onlyA.isEmpty() || !onlyB.isEmpty();
    }

    @Override
    public String toString() {
        return "FieldGroupSplit:" + onlyA + " -- " + both + " -- " + onlyB;
    }

    public static <T> FieldGroupSplit<T> split(FieldGroup<T> a, FieldGroup<T> b) {
        if (a == b) {
            return null;
        }
        if (Collections.disjoint(a, b)) {
            return null; // Return if the groups have no fields in common
        }
        FieldGroup<T> both = new FieldGroup<T>(a);
        FieldGroup<T> onlyA = new FieldGroup<T>(a);
        FieldGroup<T> onlyB = new FieldGroup<T>(b);
        both.retainAll(b);
        onlyA.removeAll(both);
        onlyB.removeAll(both);

        // Check if ALL fields are in common
        if (onlyA.isEmpty() && onlyB.isEmpty()) {
            // If this is called in a loop an infinite loop can occur if we don't do this because we're creating a NEW object all the time to hold them both.
            // We should reuse one of the existing ones and go back to using == above.
            both = a;
        }

        return new FieldGroupSplit<T>(onlyA, both, onlyB);
    }

}

I am using return null in the split method because it is a fairly common result and I feel that creating an object to represent that response is not necessary.

Here's a test for the method:

public class FieldGroupSplitTest {

    private <T> FieldGroupSplit<T> split(FieldGroup<T> a, FieldGroup<T> b) {
        return FieldGroupSplit.split(a, b);
    }

    @Test
    public void allFieldsCommon() {
        FieldGroup<String> a = new FieldGroup<String>(Arrays.asList("a", "b", "c"));
        FieldGroup<String> b = new FieldGroup<String>(Arrays.asList("a", "b", "c"));
        FieldGroupSplit<String> split = split(a, b);
        assertTrue(split.getOnlyA().isEmpty());
        assertFalse(split.getBoth().isEmpty());
        assertSame(a, split.getBoth());
        assertTrue(split.getOnlyB().isEmpty());
        assertFalse(split.splitPerformed());
    }

    @Test
    public void split() {
        FieldGroup<String> a = new FieldGroup<String>(Arrays.asList("a", "b", "c"));
        FieldGroup<String> b = new FieldGroup<String>(Arrays.asList("b", "c", "d"));
        FieldGroupSplit<String> split = split(a, b);
        assertEquals(new FieldGroup<String>(Arrays.asList("a")), split.getOnlyA());
        assertEquals(new FieldGroup<String>(Arrays.asList("b", "c")), split.getBoth());
        assertEquals(new FieldGroup<String>(Arrays.asList("d")), split.getOnlyB());
        assertTrue(split.splitPerformed());
    }

    @Test
    public void disjointGroups() {
        FieldGroup<String> a = new FieldGroup<String>(Arrays.asList("a", "b", "c"));
        FieldGroup<String> b = new FieldGroup<String>(Arrays.asList("d", "e", "f"));
        FieldGroupSplit<String> split = split(a, b);
        assertNull(split);
    }

}

The code is using Java 1.6

Answer 1

Just a few quick minor notes:

1. This comment:

   // Check if ALL fields are in common
   if (onlyA.isEmpty() && onlyB.isEmpty()) {
   

   could be replaced with an explanatory local variable:

   boolean allFieldsAreInCommon = onlyA.isEmpty() && onlyB.isEmpty();
   if (allFieldsAreInCommon) {
   

2. The same is true for this one:

   if (Collections.disjoint(a, b)) {
       return null; // Return if the groups have no fields in common
   }
   

   Result:

   boolean noFieldsInCommon = Collections.disjoint(a, b);
   if (noFieldsInCommon) {
       return null;
   }
   

3. 160-character long line width is a little bit long here:

   // If this is called in a loop an infinite loop can occur if we don't do this because we're creating a NEW object all the time to hold them both.
   // We should reuse one of the existing ones and go back to using == above.
   

   A few linebreak would avoid horizontal scrolling.

4. The following patterns is duplicated in the test method:

   new FieldGroup<String>(Arrays.asList("a", "b", "c"))
   

   I would create a createFieldGroup(String...) method for that.

5. I would consider using Optional from Guava instead of null return values.

Answer 2

The time complexity/scalability of your method is approximately \$O(n^3)\$ because:

1. your code performs intersection analysis multiple times (3 times):

   1. both.retainAll(b);
   2. onlyA.removeAll(both);
   3. onlyB.removeAll(both);

2. Each of these 3 operations is an \$O(n^3)\$ operation:

   1. scan the members in one set is \$O(n)\$ (where n is the size of the first set)
   2. with that member, scan the other set is \$O(n)\$ (where n is the size of the secomd set)
   3. remove the member if it matches which is \$O(n)\$ (because it is an ArrayList, and removing a member means shifting all members after the removed item by one).

3. For small data sets, this is a viable option, but, as the n sizes get larger (beyond about 10), the scalability drops off very quickly.

The thing with ArrayList is that the add operation is \$O(1)\$. A HashSet has a time complexity for the 'contains' method of \$O(1)\$

Your code can be rearranged to use more convenient data structures that help significantly:

• only add to the list (don't remove)
• use a Set for the lookups.

This costs a bit to set up the Set, but the cost is recouped quickly when the data sets become even modestly big....

private static final boolean areSame(Object a, Object b) {
    // a == b covers case when both are null too
    return (a == b) || (a != null && a.equals(b));
}

public static final <T> FieldGroupSplit<T> splitHash(final FieldGroup<T> a, final FieldGroup<T> b) {

    if (a == b || a.isEmpty() || b.isEmpty()) {
        return null;
    }

    final boolean aissmall = a.size() <= b.size();

    final FieldGroup<T> wsml = aissmall ? a : b;
    final Set<T> wbig = new HashSet<>(aissmall ? b : a);

    final Set<T> both = new HashSet<>(wsml.size());

    final FieldGroup<T> aonly = new FieldGroup<>(a.size());
    final FieldGroup<T> bonly = new FieldGroup<>(b.size());

    final FieldGroup<T> smlonly = aissmall ? aonly : bonly;
    final FieldGroup<T> bigonly = aissmall ? bonly : aonly;

    for (final T val : wsml) {
        if (wbig.contains(val)) {
            both.add(val);
        } else {
            smlonly.add(val);
        }
    }

    if (both.isEmpty()) {
        return null;
    }

    for (final T val : wbig) {
        if (!both.contains(val)) {
            bigonly.add(val);
        }
    }

    return new FieldGroupSplit<>(aonly, aonly.isEmpty() ? a : new FieldGroup<T>(both), bonly);

}

So, the above code uses scalable structures to do the algorithm, but incurs the setup cost for the Set.

After that, the scalability is about \$O(n)\$ ...

In my testing, for data of sizes less than about 10, your code was faster, but, after 10, my code was faster.... and, when you have sets up to 80 or more, my code was 1X faster, and up to 400, my code was 12X faster.

To make things work even better, I added this function (BOBW is 'best of both worlds'):

public static final <T> FieldGroupSplit<T> splitBOBW(final FieldGroup<T> a, final FieldGroup<T> b) {
    return (a.size() + b.size() > 20) ? splitHash(a, b) : split(a,b);
}

20 was about where it made sense to switch.... YMMV