Subtract HashSets (and return a copy)?

Mark_65387 0
Viewed 13563

I've got a HashSet,

var universe = new HashSet<int>();

And a bunch of subsets,

var sets = new List<HashSet<int>>(numSets);

I want to subtract a chunk, which I can do like this:

var remaining = universe.ExceptWith(sets[0]);

But ExceptWith works in-place. I don't want to modify the universe. Should I clone it first, or is there a better way?

hashset c#
6 Answers

I benchmarked Linq's Except method against cloning and using the HashSet-native function ExceptWith. Here are the results.

static class Program
{
    public static HashSet<T> ToSet<T>(this IEnumerable<T> collection)
    {
        return new HashSet<T>(collection);
    }

    public static HashSet<T> Subtract<T>(this HashSet<T> set, IEnumerable<T> other)
    {
        var clone = set.ToSet();
        clone.ExceptWith(other);
        return clone;
    }

    static void Main(string[] args)
    {
        var A = new HashSet<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        var B = new HashSet<int> { 2, 4, 6, 8, 10 };
        var sw = new Stopwatch();

        sw.Restart();
        for (int i = 0; i < 1000000; ++i)
        {
            var C = A.Except(B).ToSet();
        }
        sw.Stop();
        Console.WriteLine("Linq: {0} ms", sw.ElapsedMilliseconds);

        sw.Restart();
        for (int i = 0; i < 1000000; ++i)
        {
            var C = A.Subtract(B);
        }
        sw.Stop();
        Console.WriteLine("Native: {0} ms", sw.ElapsedMilliseconds);

        Console.ReadLine();
    }
}

Linq: 1297 ms
Native: 762 ms

http://programanddesign.com/cs/subtracting-sets/

Mark_653870

Very late answer but maybe useful sometimes.

@mpen answered by using Linq's Except(IEnumerable<>)

Which make linq loop trough IEnumerable check if it's contains.

How about

setA.Where(i => !setB.Contains(i))

user_31871830

Obviously in a few cases 'manually' adding items in a loop is more efficient than copying the whole set and then removing items. One I can think of ...

// no more set ops planned? then returning list is an option
public static List<T> ExceptWith<T>(HashSet<T> allObjects, Hashset<T> minus)
{
    //  Set Capacity of list   (allObjects.Count-minus.Count?)
    List<T> retlst = new List<T>(allObjects.Count); 

    foreach( var obj in allObjects) {
        if( minus.Contains(obj)==false)
            retlst.Add(obj);
    }
    return retlst;
}

// Special case where quantity of copying will be high
// more expensive in fact than just adding
public static HashSet<T> ExceptWith<T>(HashSet<T> allObjects, HashSet<T> minus)
{
    if( minus.Count > allObjects.Count * 7/8 )
    {
        HashSet<T> retHash = new HashSet<T>(); 

        foreach( var obj in allObjects) {
            if( minus.Contains(obj)==false)
                retHash.Add(obj);
        }
        return retHash;

    }
    else
    {
        // usual clone and remove
    }
}
user_102708200
Related