look i know no one really pays attention to this type but should Set<T> have the ability to test if at least one element is in self that is not in the other set? This is basically set.subtract(other).isEmpty except the result set is not needed.
We can test that without result set.
let setA = Set([0, 1])
let setB = Set([1, 2])
assert(setA.isSubset(of: setB) == setA.subtracting(setB).isEmpty)
1 Like
that does a lot more computation than is necessary though
I looked into the implementations.
isSubset calls _comapreSet, and _comapreSet returns immediately when find a lhs element which is not contained in rhs.
The worst case is when lhs is a subset of rhs but it is necessary cost I think.
On the other hand, any subtracts try to remove all elements in other from self.
I don't know which is faster setA.subtracting(setB).isEmpty or setA.isSubset(of: setB).
Can you explain why subtract base algorithm is more efficient?
I think isSubset is the exact operation you want here, and so presumably does as much computation as is necessary. The problem could be phrased as:
there exists some element of
selfthat is not inother
which is equivalent (via De Morgan's laws) to
not (all elements of
selfare inother)
which is exactly !self.isSubset(of: other).
11 Likes
oooh i didn’t think of reversing the order of self and other. thanks!