10
\$\begingroup\$

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 A but not in B

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

\$\endgroup\$
  • \$\begingroup\$ How large are typical and extreme input FieldGroup sets? 10 members, 5 members? thousands of members? \$\endgroup\$ – rolfl Jul 9 '14 at 14:01
  • \$\begingroup\$ I would say over 9000! (but it's a bit cliché) \$\endgroup\$ – Marc-Andre Jul 9 '14 at 14:08
  • \$\begingroup\$ @rolfl It's usually only 2-8, sometimes even 1. Once each analyze there's a bigger one, which starts at 256 and then for each analyze is decreased as the game progresses. \$\endgroup\$ – Simon Forsberg Jul 9 '14 at 14:34
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I really find using null awkward. I've never use something like Optional, this is really something I need to dig! \$\endgroup\$ – Marc-Andre Jul 9 '14 at 13:41
  • 1
    \$\begingroup\$ @Marc-Andre: Then you might find interesting that Java 8 has another implementation: docs.oracle.com/javase/8/docs/api/java/util/Optional.html \$\endgroup\$ – palacsint Jul 9 '14 at 14:05
  • \$\begingroup\$ An alternative to Optional when working with collections is to return an empty one. For example, you could have created a private static final EMPTY_SPLIT in FieldGroupSplit class and return it instead of null from the split method. See this article for Collections.emptyList() method usage and remember that the returned list is immutable. \$\endgroup\$ – mkalkov Jul 10 '14 at 10:44
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ There are some cases in which your code does not result in the same as my original code. I added more test cases to better highlight those. This is not at all to "invalidate" your answer, only to show better how the original code actually works. I tried fixing the problem for allFieldsCommon but I haven't managed to do so yet. \$\endgroup\$ – Simon Forsberg Jul 10 '14 at 9:45
  • \$\begingroup\$ @SimonAndréForsberg = modified the code to pass the unit tests now. (see the diff, just a couple of small changes). \$\endgroup\$ – rolfl Jul 10 '14 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.