SetAlgebra test difference

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 self that is not in other

which is equivalent (via De Morgan's laws) to

not (all elements of self are in other)

which is exactly !self.isSubset(of: other).


oooh i didn’t think of reversing the order of self and other. thanks!