ハッシュセットを差し引く（およびコピーを返す）？

StackOverflow https://stackoverflow.com/questions/3897568

  •  29-09-2019
  •  | 
  •  

質問

ハッシュセットがあります、

var universe = new HashSet<int>();

そしてサブセットの束、

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

チャンクを減算したいのですが、これができることは次のとおりです。

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

しかし ExceptWith 内容を整えています。変更したくありません universe. 。最初にクローンする必要がありますか、それともより良い方法はありますか？

役に立ちましたか？

解決

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

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

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

ほど単純ではありません Except 拡張方法ですが、おそらくより速いです（確かにいくつかのパフォーマンステストを実行する必要があります）

他のヒント

どうですか Except()?

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

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

私はlinqをベンチマークしました Except ハッシュセットネイティブ関数のクローニングと使用に対する方法 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/

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

非常に遅い答えですが、多分時々便利です。

@mpenはlinqを除く（ienumerable <>）を使用して回答しました

これにより、Linqループが含まれているかどうかを確認できます。

どうですか

seta.where（i =>！setb.contains（i））

明らかに、いくつかの場合、「手動で」アイテムをループに追加することは、セット全体をコピーしてからアイテムを削除するよりも効率的です。私が考えることができるもの...

// 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
    }
}
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top