Вычесть HashSets (и вернуть копию)?

Question

У меня есть HashSet,

var universe = new HashSet<int>();

И куча подмножеств,

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

Я хочу вычесть кусок, который я могу сделать так:

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

Но ExceptWith работает на месте. Я не хочу изменять universe. Должен ли я сначала клонировать его, или есть лучший способ?

Answer 1

Думаю, я должен клонировать это первый? Как мне это сделать?

var universe = new HashSet<int>();
var subset = new HashSet<int>();
...

// clone the universe
var remaining = new HashSet<int>(universe);
remaining.ExceptWith(subset);

Не так просто, как при использовании метода расширения Except, но, вероятно, быстрее (вам нужно выполнить несколько тестов производительности, чтобы убедиться)

Answer 2

Как насчет Except()?

var x = new HashSet<int>();
var y = new HashSet<int>();

var xminusy = new HashSet<int>(x.Except(y));

Answer 3

Я протестировал метод Linq Except против клонирования и использования нативной функции HashSet ExceptWith.Вот результаты.

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();
    }
}

Линк: 1297 мс
Собственный: 762 мс

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

Answer 4

Хэш-набор должен отслеживать его константы алгоритма хэширования и его ячейки переполнения.Элементы в наборе хранятся по ссылке.Создание нового хэша с конструктором копирования, как предлагает Томас Левеск, создает поверхностную копию этих издержек и должно быть довольно быстрым.Использование Except () так, как предлагает Джеймс МакНеллис, сначала создает анонимную копию, а затем передает ее конструктору копирования, который использует поля в анонимной для инициализации собственных полей.Как сказал Томас, вы можете сделать несколько тестов производительности, но теоретически его ответ должен превзойти ответ Джеймса.И, кстати, по моему мнению, мелкая копия не является клоном, поскольку я считаю, что клон подразумевает, что базовые элементы также копируются.Хеш-наборы с общими элементами используют копию при изменении стратегии.

Answer 5

Очевидно, что в некоторых случаях «ручное» добавление элементов в цикле более эффективно, чем копирование всего набора и последующее удаление элементов.Один я могу думать о ...

// 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
    }
}

Answer 6

Очень поздно, но иногда полезно.

@ mpen ответил с помощью Linq's Except (IEnumerable <>)

Что делает цикл linq через IEnumerable проверяет, содержится ли он.

Как насчет

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