c# - How should I calculate the disjoint elements of 2 sets? -

given 2 (either ordered or not ordered) sets , b of elements of same type, arbitrary number of elements exists in a, b or both.

i determine elements in not contained in b elements of b not contained in a.

this can done via

var da = a.except(b); var db = b.except(a); 

my question: efficient algorithm task?

since above iterates both sets, appears might able re-use information first iteration reduce effort spent on second.

let n size of set a , m size of set b. if assume a , b implemented hash tables, there's simple o(min(n,m)) expected time algorithm find a \ b , b \ a.

w.l.o.g let n < m (otherwise swap sets).

1. iterate through a. every element, check whether in b well. if yes, remove b. if no, add da.
2. i thought there second step in fact you're done already.

the result in da , b.

if don't want destroy b, can create copy of beforehand, should fast when implemented simple memcpy.

you could instead use persistent data structure represent b, adds considerable cost , unlikely helpful, unless set sizes very unbalanced.