Un modo efficiente per clonare un HashSet <T>?

Question

Alcuni giorni fa, ho risposto a an interesting question su SO su HashSet<T>. Una possibile soluzione coinvolto clonazione del HashSet, e nella mia risposta che ho suggerito di fare qualcosa di simile:

HashSet<int> original = ... 
HashSet<int> clone = new HashSet<int>(original); 

Anche se questo approccio è abbastanza semplice, ho il sospetto che sia molto inefficiente: il costruttore delle nuove HashSet<T> bisogno di aggiungere a parte ogni articolo dall'hashset originale e verifica se non è già presente. Questa è chiaramente una perdita di tempo: poiché la raccolta di origine è una ISet<T>, è garantito che non contenga duplicati. Ci dovrebbe essere un modo per sfruttare questa conoscenza ...

Idealmente, HashSet<T> dovrebbe implementare ICloneable, ma sfortunatamente non è il caso. Ho anche controllato con Reflector per vedere se il costruttore HashSet<T> ha fatto qualcosa di specifico se la collezione di origine era un hashset, ma non è così. Potrebbe probabilmente essere fatto usando la riflessione su campi privati, ma sarebbe un brutto attacco ...

Quindi, qualcuno ha escogitato una soluzione intelligente per clonare un hashset in modo più efficiente?

(Si noti che questa domanda è puramente teorica, non ho bisogno di farlo in un programma vero e proprio)

Answer 1

Se si voleva davvero il modo più efficace per clonare un HashSet<T>, devi eseguire le seguenti operazioni (ma possibilmente a costo di manutenzione)

1. Utilizzare riflettore o il debugger di capire esattamente quello che i campi in deve essere copiato. Potrebbe essere necessario farlo in modo ricorsivo per ogni campo.
2. Utilizzare Reflection.Emit o utilizzare alberi di espressioni per generare un metodo che esegue la copia necessaria di tutti i campi. Potrebbe essere necessario chiamare altri metodi generati che copiano il valore di ciascun campo. Stiamo utilizzando la generazione del codice di runtime perché è l'unico modo per accedere direttamente ai campi privati.
3. Utilizzare FormatterServices.GetUninitializedObject(...) per creare un'istanza di un oggetto vuoto. Utilizzare il metodo generato nel passaggio 2 per copiare l'oggetto originale nel nuovo oggetto vuoto.

Answer 2

Facile modello che dovrebbe non sarà lavoro per molte collezioni:

 
Class cloneableDictionary(Of T, U) 
    Inherits Dictionary(Of T, U) 
    Function clone() As Dictionary(Of T, U) 
     Return CType(Me.MemberwiseClone, cloneableDict(Of T, U)) 
    End Function 
End Class 

Sfortunatamente, non so che Microsoft abbia fatto qualcosa per evitare di chiamare MemberwiseClone in posti dove non dovrebbe essere chiamato Non so come si possa dire È probabile che un tale approccio funzioni.

Penso che ci sia un buon motivo per una raccolta standard che non supporta un metodo di clonazione pubblica ma solo una protetta: è possibile che una classe derivante da una raccolta si rompa gravemente se clonata e se il metodo di clonazione della classe base è pubblico non c'è modo di impedire che un oggetto di una classe derivata venga dato al codice che si aspetta di clonarlo.

Detto questo, sarebbe stato bello se .net includesse cloneableDictionary e altre classi come i tipi standard ( sebbene ovviamente non implementato essenzialmente come sopra).

Answer 3

Solo un pensiero casuale. Potrebbe essere sciocco.

Poiché non hanno implementato ICloneable, e il costruttore non usa la consapevolezza che la fonte è dello stesso tipo, suppongo che resteremo con una sola opzione. Implementazione della versione ottimizzata e aggiunta come tipo di estensione al tipo.

Qualcosa di simile:

namespace ExtensionMethods 
{ 
    public static class MyExtensions 
    { 
     public static HashSet<int> Clone(this HashSet<int> original) 
     { 
      HashSet<int> clone = new HashSet<int>(); 
      //your optimized code here 
      return clone; 
     } 
    } 
} 

Poi, il codice dalla questione sarebbe simile a questa:

HashSet<int> original = ... 
HashSet<int> clone = HashSet<int>.Clone(original); 

Answer 4

O (n) clone è buono come si può ottenere, in teoria, per clonare due set che non condivideranno la stessa struttura dati sottostante.

Controllare se un elemento è in un HashSet o meno deve essere un'operazione costante (ad esempio O (1)).

Quindi è possibile creare un wrapper che avvolga solo un HashSet esistente e si attenga a eventuali nuove aggiunte, ma ciò sembra piuttosto perverso.

Quando si dice "efficiente", si intende "più efficiente rispetto al metodo O (n) esistente" - Suppongo che in realtà non si possa essere più efficienti di O (n) senza giocare a giochi semantici abbastanza seri su cosa " clone 'significa.

Answer 5

EDIT: Dopo un esame più attento questo non sembra essere una buona idea, con meno di 60 elementi della HashSet originale il seguente metodo sembra essere più lento di solo la creazione di un nuovo hashset.

NOTA BENE: questo sembra funzionare, ma utilizzare a proprio rischio, se avete intenzione di serializzare i hashsets clonati probabilmente da copiare SerializationInfo m_siInfo.

Ho anche affrontato questo problema e ho preso una piega, di seguito troverete un metodo di estensione che utilizza FieldInfo.GetValue e SetValue per copiare i campi richiesti. È più veloce dell'utilizzo di HashSet (IEnumerable), quanto dipende dalla quantità di elementi nell'hashset originale. Per 1000 elementi la differenza è di circa un fattore 7. Con 100.000 elementi è circa un fattore 3.

Ci sono altri modi che possono essere anche più veloci, ma per il momento mi sono sbarazzato del collo di bottiglia. Ho provato a usare expressiontrees ed emettere ma ho colpito un posto di blocco, se riesco a farlo funzionare, aggiorno questo post.

using System; 
using System.Collections.Generic; 
using System.Reflection; 
using System.Runtime.Serialization; 

public static class HashSetExtensions 
{ 
    public static HashSet<T> Clone<T>(this HashSet<T> original) 
    { 
     var clone = (HashSet<T>)FormatterServices.GetUninitializedObject(typeof(HashSet<T>)); 
     Copy(Fields<T>.comparer, original, clone); 

     if (original.Count == 0) 
     { 
      Fields<T>.freeList.SetValue(clone, -1); 
     } 
     else 
     { 
      Fields<T>.count.SetValue(clone, original.Count); 
      Clone(Fields<T>.buckets, original, clone); 
      Clone(Fields<T>.slots, original, clone); 
      Copy(Fields<T>.freeList, original, clone); 
      Copy(Fields<T>.lastIndex, original, clone); 
      Copy(Fields<T>.version, original, clone); 
     } 

     return clone; 
    } 

    static void Copy<T>(FieldInfo field, HashSet<T> source, HashSet<T> target) 
    { 
     field.SetValue(target, field.GetValue(source)); 
    } 

    static void Clone<T>(FieldInfo field, HashSet<T> source, HashSet<T> target) 
    { 
     field.SetValue(target, ((Array)field.GetValue(source)).Clone()); 
    } 

    static class Fields<T> 
    { 
     public static readonly FieldInfo freeList = GetFieldInfo("m_freeList"); 
     public static readonly FieldInfo buckets = GetFieldInfo("m_buckets"); 
     public static readonly FieldInfo slots = GetFieldInfo("m_slots"); 
     public static readonly FieldInfo count = GetFieldInfo("m_count"); 
     public static readonly FieldInfo lastIndex = GetFieldInfo("m_lastIndex"); 
     public static readonly FieldInfo version = GetFieldInfo("m_version"); 
     public static readonly FieldInfo comparer = GetFieldInfo("m_comparer"); 

     static FieldInfo GetFieldInfo(string name) 
     { 
      return typeof(HashSet<T>).GetField(name, BindingFlags.Instance | BindingFlags.NonPublic); 
     } 
    } 
}