3
\$\begingroup\$

An API (I have no control over) gives me a bunch of Collections (Lists, to be precise,) and I need the elements that are common to all of them. In this concrete case, I'm trying to find Selenium WebElements that match several selectors. But I went off on a Yak-Shaving spree and tried to figure out how to make an intersection of a stream of Collections. This is what I came up with (and I think it works, at least my tests say so.)

/**
 * Given a stream of collections, intersect it.
 *
 * @param stream A stream of collections you want to intersect
 * @param <T> Any item that has a decent .equals()/.hashCode().
 *            Seriously, don't attempt this without a working .equals()/.hashCode().
 * @return The unique(!) elements present in *all* collections in the stream
 */
public static <T> Collection<T> intersect(Stream<Collection<T>> stream) {
  // Optimization: sorting by size so that the biggest constrainer
  // (smallest collection) comes first
  final Iterator<Collection<T>> allLists = stream.sorted(
        (l1, l2) -> l1.size() - l2.size()
  ).iterator();

  final Set<T> result = new HashSet<>(allLists.next());
  while(allLists.hasNext()) {
      result.retainAll(allLists.next());
  }
  return result;
}

I fiddled around with Collectors in the beginning, but that seemed to be too convoluted, since it'd require the unit element to be some special class.

Any better way of doing it? Is this woefully inefficient? I think its complexity is somewhere around O(n) where n should be the total number of elements in all the collections.

\$\endgroup\$
  • \$\begingroup\$ "Is this woefully inefficient?" you most efficiently do those things you don't do. So why are you sorting the list of lists? Did you measure that is make a difference or do you just assume to be more efficient? \$\endgroup\$ – Timothy Truckle Oct 29 '16 at 9:50
  • \$\begingroup\$ The list containing the fewest elements is likely to be the one imposing the biggest constraint in terms of items, so fewer items are going to have to be deleted. Also, sorting the lists is not going to be expensive relative to the whole operation. But you're right, maybe I should leave that to the caller, since .size() may be expensive. \$\endgroup\$ – Aleksandar Dimitrov Oct 29 '16 at 10:07
  • \$\begingroup\$ "The list containing the fewest elements is likely to be the one imposing the biggest constraint in terms of items, so fewer items are going to have to be deleted." that's your reasoning and that's OK, but did you measure the effect? \$\endgroup\$ – Timothy Truckle Oct 29 '16 at 10:09
  • \$\begingroup\$ Nope, just a case of premature optimization on my part, I guess :-) As I said, I believe that this could backfire badly if .size() is even a little bit expensive. \$\endgroup\$ – Aleksandar Dimitrov Oct 29 '16 at 11:25
  • \$\begingroup\$ I have rolled back the last edit. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Vogel612 Oct 29 '16 at 15:36
5
\$\begingroup\$

Using built-ins

You can use built-in comparators instead of creating your own. For example

final Iterator<Collection<T>> allLists = stream.sorted(
      (l1, l2) -> l1.size() - l2.size()
).iterator();

can be written more simply using the comparingInt comparator, which compares elements according to the result of applying the given function (returning an int) to each element. In this case, you could have:

final Iterator<Collection<T>> allLists =
    stream.sorted(Comparator.comparingInt(Collection::size)).iterator();

The function returning the integer to compare is written as a method-reference refering to Collection.size(). Also, it gets rid of the comparison by subtracting the two int values, which has a corner-case.

Bug if the stream is empty

There is a bug in the current method if the given stream is empty. This is because of

final Set<T> result = new HashSet<>(allLists.next());

which unconditionally invokes next() on the iterator of the stream. You can call intersect(Stream.empty()) to verify it; it will throw a NoSuchElementException. In the case of an empty stream, the method should return an empty collection instead.

Better generics

With the current signature of

<T> Collection<T> intersect(Stream<Collection<T>> stream)

the issue is that passing for example a Stream<List<Integer>> will not compile. To verify this, you can have

intersect(Arrays.asList(Arrays.asList(1)).stream())

Instead, we can introduce a second generic type C for the collection with the following signature:

<T, C extends Collection<T>> Collection<T> intersect(Stream<C> stream)

This makes sure that you can pass any collection for the elements of the input stream. With such a signature, you can verify that the above compilation error is not there anymore.

Huge performance improvement

If you're not dealing with sets, the retainAll process is very inefficient:

result.retainAll(allLists.next());

Since this method checks to see if the collection given as parameter doesn't contain the elements of this collection (in order to remove them), using this on a List is O(n), making the whole operation O(n²). Instead, pass a new HashSet:

result.retainAll(new HashSet<>(allLists.next()));

Since the contains operation is constant time for sets, this will always be O(n), and, thus, a lot faster (at the expense of more memory).

Why sort?

The comment in your code says that the sorting step is used as an optimization, to ensure that shorter collections comes first. Intrigued, I made a benchmark comparing the code with and without sorting. It applied the two methods to a stream having 1000 and 10.000 elements where each inner collections had 100 and 1.000 elements. The elements chosen were random integers. Here are the results (Windows 10 x64, JDK 1.8.0_102, i5, 2.90 GHz):

Benchmark                 (lengthOfEach)  (totalLength)  Mode  Cnt    Score   Error  Units
StreamTest.intersect                 100           1000  avgt   30    1,757 ± 0,069  ms/op
StreamTest.intersect                 100          10000  avgt   30   18,876 ± 0,954  ms/op
StreamTest.intersect                1000           1000  avgt   30   17,287 ± 0,378  ms/op
StreamTest.intersect                1000          10000  avgt   30  177,633 ± 7,043  ms/op
StreamTest.intersectSort             100           1000  avgt   30    1,805 ± 0,080  ms/op
StreamTest.intersectSort             100          10000  avgt   30   18,434 ± 0,621  ms/op
StreamTest.intersectSort            1000           1000  avgt   30   19,472 ± 0,981  ms/op
StreamTest.intersectSort            1000          10000  avgt   30  184,440 ± 5,380  ms/op

For the values tested, this shows that there is really no measurable difference between the two, so I'd just get rid of this sorting.

Code of benchmark for completeness:

@Warmup(iterations = 10, time = 700, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 10, time = 700, timeUnit = TimeUnit.MILLISECONDS)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Fork(3)
public class StreamTest {

    public static <T, U extends Collection<T>> Collection<T> intersectSort(Stream<U> stream) {
        final Iterator<U> allLists = stream.sorted(Comparator.comparingInt(Collection::size)).iterator();

        if (!allLists.hasNext()) return Collections.emptySet();

        final Set<T> result = new HashSet<>(allLists.next());
        while (allLists.hasNext()) {
            result.retainAll(new HashSet<>(allLists.next()));
        }
        return result;
    }

    public static <T, C extends Collection<T>> Collection<T> intersect(Stream<C> stream) {
        final Iterator<C> allLists = stream.iterator();

        if (!allLists.hasNext()) return Collections.emptySet();

        final Set<T> result = new HashSet<>(allLists.next());
        while (allLists.hasNext()) {
            result.retainAll(new HashSet<>(allLists.next()));
        }
        return result;
    }

    @State(Scope.Benchmark)
    public static class Container {

        @Param({ "100", "1000" })
        private int totalLength;

        @Param({ "1000", "5000" })
        private int lengthOfEach;

        private List<List<Integer>> list;
        private Stream<List<Integer>> stream;

        @Setup(Level.Trial)
        public void setUp() {
            ThreadLocalRandom rnd = ThreadLocalRandom.current();
            list = rnd.ints(totalLength).mapToObj(i -> rnd.ints(lengthOfEach).boxed().collect(Collectors.toList())).collect(Collectors.toList());
        }

        @Setup(Level.Invocation)
        public void makeStream() {
            stream = list.stream();
        }

    }

    @Benchmark
    public Collection<Integer> intersectSort(Container a) {
        return intersectSort(a.stream);
    }

    @Benchmark
    public Collection<Integer> intersect(Container a) {
        return intersect(a.stream);
    }

}
\$\endgroup\$
  • \$\begingroup\$ Fantastic, thanks for your comprehensive answer, that's exactly the sort of thing I was looking for. What baffled me is that a.retainsAll(b) seems to work exactly opposite to what I thought. I'd have thought it does for (T e : b) { if (a.contains(e)) { … } } but you're saying it's the other way around! Isn't your proposal of creating a new HashSet for each constituent Collection also wasteful, because the creation of a HashSet necessarily does .contains() checks on itself during construction? \$\endgroup\$ – Aleksandar Dimitrov Oct 29 '16 at 15:09
  • \$\begingroup\$ @AleksandarDimitrov Constructing a HashSet from a collection is linear in terms of the number of elements. It doesn't call contains on the given collection, but just adds all of its elements to the set. \$\endgroup\$ – Tunaki Oct 29 '16 at 15:18

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.