c# - HashSetsを減算します（そしてコピーを返します）？

Question

私はHashSetを持っています、

var universe = new HashSet<int>();

そして、サブセットの束、

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

チャンクを減算したいのですが、これは次のように実行できます。

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

しかしExceptWith、その場で動作します。を変更したくありませんuniverse。最初にクローンを作成する必要がありますか、それとももっと良い方法がありますか？

score 15 · Accepted Answer

最初にクローンする必要があると思いますか？それ、どうやったら出来るの？

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

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

拡張メソッドほど単純ではありませんExceptが、おそらくより高速です (確認するためにいくつかのパフォーマンステストを実行する必要があります)。

score 11 · Accepted Answer

どうExcept()ですか？

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

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

score 9 · Accepted Answer

Exceptクローン作成と HashSet-native function の使用に対してLinq の方法をベンチマークしました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();
    }
}

Linq: 1297 ミリ秒
ネイティブ: 762 ミリ秒

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

score 1 · Accepted Answer

ハッシュセットは、ハッシュアルゴリズム定数とオーバーフロービンを追跡する必要があります。セット内の要素は参照によって保持されます。Thomas Levesque が示唆するように、コピーコンストラクターを使用して新しいハッシュを作成すると、このオーバーヘッドの浅いコピーが作成され、非常に高速になるはずです。James McNellis が提案する方法で Except() を使用すると、最初に匿名コピーが作成され、それが匿名のフィールドを使用して独自のフィールドを初期化するコピーコンストラクターに渡されます。Thomas が言ったように、いくつかのパフォーマンステストを行うこともできますが、理論的には、彼の答えは James の答えよりも優れているはずです。ちなみに、私の考え方では、浅いコピーはクローンではありません。クローンは、基になる要素もコピーされることを意味すると考えているからです。共通の要素を持つハッシュセットは、戦略が変更されたときにコピーを使用します。

c# - HashSetsを減算します（そしてコピーを返します）？

6 に答える 6

Related

Reference