Efficient way of finding intersection of 5 Sets

Question

I have 5 sets which has numeric values. I am interested in finding the intersection of all 5 sets.

Right now, I am thinking of the following

Do a Collections.sort() on all 5 sets

Find the shortest set and do a

shortestSet.retainAll(otherSet);

on all the other sets.

Is there a more efficient way of doing this ?

I think that would be an efficient way indeed (assuming you mean to sort the *sizes* of the sets) — Vincent van der Weele, Apr 26 '13 at 18:11
Almost dup: http://stackoverflow.com/questions/7574311/efficiently-compute-intersection-of-two-sets-in-java — leonbloy, Apr 26 '13 at 18:11
Does this answer your question? [Efficiently compute Intersection of two Sets in Java?](https://stackoverflow.com/questions/7574311/efficiently-compute-intersection-of-two-sets-in-java) — TAbdiukov, Jan 07 '20 at 11:53

score 2 · Answer 1 · answered Apr 26 '13 at 18:34

2

Your solution looks right to me, if we understand that when you write Collections.sort() you are sorting the list of sets, according to their sizes. The rationale would be that, if we are going to use set1.retainAll(set2) (and if the sets are HashSets) each intersection running time should be roughly linear on the number of elements of set1. So it makes sense to start with the smallest one.

answered Apr 26 '13 at 18:34

leonbloy

73,180
20
142
190

In addition to sorting the sets by size before calling retainAll(), would it make a difference if we sort the sets itself ? – Skynet Apr 26 '13 at 18:44
@Skynet: No (if you are talking about sorting content of the sets). – nhahtdh Apr 26 '13 at 18:46
@Skynet: No. Further, sets do not have order. ( you `sort` lists, not sets) – leonbloy Apr 26 '13 at 19:07

score 0 · Answer 2 · answered Apr 26 '13 at 18:14

0

Your solution is fine. There would be no need to sort the numbers before calling the retainAll method though.

answered Apr 26 '13 at 18:14

Slihp

763
5
12

score 0 · Answer 3 · answered Apr 26 '13 at 18:18

0

Try to use

static <E> Sets.SetView<E> intersection(Set<E> set1, Set<?> set2)

In Google Guava

answered Apr 26 '13 at 18:18

SerCe

5,826
2
32
53

Efficient way of finding intersection of 5 Sets

3 Answers3