Josh Josh - 3 months ago 15
Java Question

Best way to make conjunctions and disjunctions over a collection in java

What's the most efficient way to create an

and
and
or
methods over two ArrayLists?

//not coded in java

HashSet<String> first = {"hello", "to", "you"}
HashSet<String> second = {"hello", "to", "me"}

HashSet<String> and = and(first, second) = {"hello", "to"}
HashSet<String> or = or(first, second) = {"hello", "to", "you", "me"}


I need to implement those two methods (pretty easy) but I would need to do it efficiently, because I will
and
and
or
over collections with hundreds of Strings. Any tip?

Answer

To avoid confusion I'll call the methods intersection and union as the meanings of AND and OR are a little ambiguous.

There is a retainAll method on Set that will do the job of the intersection. You need to take heed of my caveats in another answer (of mine) on SO.

There is an addAll method on Collection that will do the job of union.

Here is an example:

public static void main(String[] args) throws Exception {
    final Set<String> first = new HashSet<>(Arrays.asList("hello", "to", "you"));
    final Set<String> second = new HashSet<>(Arrays.asList("hello", "to", "me"));

    System.out.println(intersection(first, second));
    System.out.println(union(first, second));

}

public static Set<String> intersection(final Set<String> first, final Set<String> second) {
    final Set<String> copy = new HashSet<>(first);
    copy.retainAll(second);
    return copy;
}

public static Set<String> union(final Set<String> first, final Set<String> second) {
    final Set<String> copy = new HashSet<>(first);
    copy.addAll(second);
    return copy;
}

Note use usage of Set rather than List. This serves two purposes:

  1. Set has O(1) contains as opposed to O(n) for a List. This helps in the intersection case.
  2. Set guarantees uniqueness. This helps in the union case.

Also note that I copy the collections before carrying out the operations - as Java passes references by value not copying would cause the original collection to be changed.

If you need to preserve order, you will need to use a LinkedHashSet as a HashSet has no order.