CODEWITHSUNDEEP
scalaset
Yann Moisan
Yann Moisan

Reputation: 8281

How to test if a Set contains at least one value in another set

Given a Set a with a size a

And a Set b with a size b

What is the most performant solution to test if b contains at least one value in a.

Solution 1 : What is the complexity of intersect ?

def containsAtLeastOne[A](a:Set[A], b: Set[A]) = a.intersect(b).nonEmpty

Solution 2 : O(a) in worst case

def containsAtLeastOne[A](a:Set[A], b: Set[A]) = a.exists(b.contains(_))

Solution 3 : O(b) in worst case

def containsAtLeastOne[A](a:Set[A], b: Set[A]) = b.exists(a.contains(_))

Upvotes: 3

Views: 4239

Answers (1)

Shailesh
Shailesh

Reputation: 388

Solution 2 and 3 are faster compared to 1st solution.

But which is faster out of solution 2 and solution 3?

This depends on data that each set contains. For example imagine that setA has 100 elements and setB has 3 elements and last element in setA is only common element in these two sets. In this case 3rd solution is faster. So this just not depends on set size but the data that set contains as well.

Anyway you should always prefer 2nd and 3rd solution if need more optimized, you can call exists method on smaller set, it should be faster in most of the cases.

Upvotes: 4

Related Questions