Sottrai hash set (e restituisce una copia)?

Question

Ho un HashSet,

var universe = new HashSet<int>(); 

e un gruppo di sottoinsiemi,

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

voglio sottrarre un pezzo, che posso fare in questo modo:

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

Ma il ExceptWith funziona sul posto. Non voglio modificare lo universe. Devo prima clonarlo o esiste un modo migliore?

Answer 1

Credo che dovrei clonarlo prima? Come lo faccio?

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

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

non è così semplice come con il metodo Except estensione, ma probabilmente più veloce (si dovrebbe eseguire alcuni test di performance per essere sicuri)

Answer 2

Che ne dici di Except()?

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

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

Answer 3

Un insieme di hash deve monitorare le sue costanti algoritmo di hash, e i suoi contenitori di trabocco. Gli elementi nel set sono tenuti per riferimento. Creare un nuovo hash con il costruttore di copie, come suggerisce Thomas Levesque, crea una copia superficiale di questo overhead e dovrebbe essere abbastanza veloce. Usare Except() nel modo in cui James McNellis suggerisce di creare prima una copia anonima e poi passarla al costruttore di copie che usa i campi nell'anonimo per inizializzare i propri campi. Come ha detto Thomas, potresti fare alcuni test sulle prestazioni, ma in teoria la sua risposta dovrebbe battere la risposta di James. E a proposito, per il mio modo di pensare, una copia superficiale non è un clone poiché credo che un clone implichi che anche gli elementi sottostanti vengano copiati. I set di hash con elementi comuni usano una copia quando viene modificata la strategia.

Answer 4

Ho eseguito il benchmark del metodo Except di Linq contro la clonazione e utilizzando la funzione nativa di HashSet ExceptWith. Ecco i risultati.

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/

Answer 5

risposta molto tardi, ma forse utile a volte.

@mpen risposta utilizzando Linq di Salvo (IEnumerable <>)

che rendono LINQ ciclo attraverso assegno IEnumerable se è contiene.

Come su

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