HashSets abziehen (und eine Kopie zurückgeben)?

Question

Ich habe ein HashSet bekam,

var universe = new HashSet<int>(); 

und eine Reihe von Untergruppen,

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

Ich möchte ein Stück subtrahieren, die ich so tun kann:

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

Aber ExceptWith funktioniert in-Place. Ich möchte die universe nicht ändern. Soll ich es zuerst klonen, oder gibt es einen besseren Weg?

Answer 1

Ich denke, ich sollte es erste klonen? Wie mache ich das?

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

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

nicht so einfach wie mit der Except Extension-Methode, aber wahrscheinlich schneller

Answer 2

Wie wäre es mit Except()?

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

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

Answer 3

Ein Hash-Set hat seinen Hash-Algorithmus Konstanten verfolgen (Sie sollen ein paar Performance-Tests, um sicherzustellen, laufen), und seine Überlaufbehälter. Die Elemente in dem Satz werden durch Bezugnahme gehalten. Das Erstellen eines neuen Hashs mit dem Copy-Konstruktor, wie Thomas Levesque vorschlägt, erzeugt eine flache Kopie dieses Overheads und sollte ziemlich schnell sein. Die Verwendung von Except() in der von James McNellis vorgeschlagenen Weise erstellt zunächst eine anonyme Kopie und übergibt diese dann an den Kopierkonstruktor, der die Felder im Anonymen verwendet, um seine eigenen Felder zu initialisieren. Wie Thomas sagte, könnten Sie ein paar Leistungstests durchführen, aber theoretisch sollte seine Antwort die Antwort von James schlagen. Und nebenbei, zu meiner Art zu denken, ist eine seichte Kopie kein Klon, da ich glaube, dass ein Klon impliziert, dass die zugrunde liegenden Elemente ebenfalls kopiert werden. Hash-Sätze mit gemeinsamen Elementen verwenden eine Kopie, wenn die Strategie geändert wird.

Answer 4

Ich Benchmark Linqs Except Methode gegen Klonen und Verwenden der HashSet-native Funktion ExceptWith. Hier sind die Ergebnisse.

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
Nativ: 762 ms

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

Answer 5

Sehr spät Antwort, aber vielleicht manchmal nützlich.

@mpen mithilfe von Linq der Ausnahme (IEnumerable <>)

beantwortet Welche Linq Schleife Trog IEnumerable zu überprüfen, ob es enthält machen.

Wie wäre es

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