The efficeient approach to calculate the interaction or union of two sets

I have two arraylists, where each of which stores a set of elements. I would like to obtain and output the intersection of these two sets. Is the开发者_Go百科re any efficient and elegant way of achieve this? How about union?

HashSet s0 = new HashSet(arraylist0);
s0.retainAll(arraylist1);
System.out.println("Intersection: " + s0);

s0 = new HashSet(arraylist0);
s0.addAll(arraylist1);
System.out.println("Union: " + s0);

If the data is logically a set, it should be stored in a Set such as a HashSet rather than a List. If you don't mind creating a new copy set and/or modifying one of the existing sets, addAll and retainAll can be used get the union/intersection.

Another option is to use Guava's Sets class to create views of the union, intersection, etc. of the two sets:

Set<Foo> union = Sets.union(firstSet, secondSet);

Such views are very efficient to create (constant time) and to do most operations (particularly contains) on, but may have to iterate over the elements for other operations such as size. They also reflect the state of their input sets even as those sets are modified after creation.

The simplest way to compute an intersection/union is to do it lazily. This takes a constant amount of time and memory. For example, to take a union of two sets which are described by some point membership classifier (aka a PMC), you could do the following:

def union(pmc_a, pmc_b)
    return lambda x : pmc_a(x) or pmc_b(x)

Of course to avoid such trivialities, you must define the union and intersection relative to the type of sets you are interested in and the type of data structure you wish to use.

1. For example, if the sets are discrete, then you should use a hash set, as both Marcin and Pajton suggest.

2. If they are continuous sets formed by intersections, unions and complements of closed halfspaces (ie Nef polyhedra), then a BSP tree is a better data structure giving you linear time boolean operations (for fixed dimension).

3. On the other hand, if they are arbitrary algebraic sets (in other words given by the 0's of a set of polynomial equations), then you would be stuck using Buchberger's algorithm to compute the Grobner basis.

4. Finally, for general semialgebraic sets (ie sets of polynomial inequalities), the best you can do is use Tarski-Sedenberg, and the cylindrical algebraic decomposition. These latter methods are somewhat unreliable, and undecidable in generality.

There are of course many more types of algorithms which are specialized to various types of sets and their representations. So, the bottom line is that in order to compute these operations you have to first describe what sorts of objects you are working with, and how they are to be represented.

Union: add them to a hashset.

Intersection: Add one of them to a hashset. When adding the members of the second list, record which ones are a clash.