Un moyen efficace de cloner un HashSet<T> ?

Question

Il y a quelques jours, j'ai répondu une question intéressante sur SO à propos de HashSet<T> . Une solution possible consistait à cloner le hashset, et dans ma réponse j'ai suggéré de faire quelque chose comme ceci :

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

Bien que cette approche soit assez simple, je pense qu'elle est très inefficace : le constructeur de la nouvelle fonction HashSet<T> doit ajouter séparément chaque élément du hashset original, et vérifier s'il n'est pas déjà présent . Il s'agit clairement d'une perte de temps : puisque le recueil des sources est une ISet<T> il est garanti qu'il ne contient pas de doublons. Il devrait y avoir un moyen de tirer parti de cette connaissance...

Idéalement, HashSet<T> devrait mettre en œuvre ICloneable mais malheureusement, ce n'est pas le cas. J'ai également vérifié auprès de Reflector pour voir si les HashSet<T> le constructeur faisait quelque chose de spécifique si la collection source était un hashset, mais ce n'est pas le cas. Cela pourrait probablement être fait en utilisant la réflexion sur les champs privés, mais ce serait un hack moche...

Alors, quelqu'un a-t-il trouvé une solution intelligente pour cloner un hashset plus efficacement ?

(Notez que cette question est purement théorique, je n'ai pas besoin de faire cela dans un programme réel)

Answer 1

Si vous vouliez vraiment le moyen le plus efficace de cloner une HashSet<T> vous feriez ce qui suit (mais peut-être au prix de la maintenabilité)

1. Utilisez le réflecteur ou le débogueur pour déterminer exactement quels sont les champs de l'application HashSet<T> doivent être copiés. Vous devrez peut-être effectuer cette opération de manière récursive pour chaque champ.
2. Utilisez Reflection.Emit ou utiliser des arbres d'expression pour générer une méthode qui effectue la copie nécessaire de tous les champs. Il peut être nécessaire d'appeler d'autres méthodes générées qui copient la valeur de chaque champ. Nous utilisons la génération de code à l'exécution parce que c'est le seul moyen d'accéder directement aux champs privés.
3. Utilisez FormatterServices.GetUninitializedObject(...) pour instancier un objet vierge. Utilisez la méthode générée à l'étape 2 pour copier l'objet original vers le nouvel objet vierge.

Answer 2

EDITAR: Après une inspection plus approfondie, cela ne semble pas être une bonne idée, avec moins de 60 éléments dans le hashset d'origine, la méthode ci-dessous semble être plus lente que la simple création d'un nouveau hashset.

CLAUSE DE NON-RESPONSABILITÉ : cela semble fonctionner mais à utiliser à vos propres risques, si vous allez sérialiser les hashsets clonés, vous voudrez probablement copier SerializationInfo m_siInfo.

J'ai également été confronté à ce problème et j'ai tenté de le résoudre. Vous trouverez ci-dessous une méthode d'extension qui utilise FieldInfo.GetValue et SetValue pour copier les champs requis. C'est plus rapide que d'utiliser HashSet(IEnumerable), combien dépend de la quantité d'éléments dans le hashset original. Pour 1 000 éléments, la différence est d'environ un facteur 7. Pour 100 000 éléments, elle est d'un facteur 3.

Il existe d'autres méthodes qui peuvent être encore plus rapides, mais cette méthode m'a permis d'éliminer le goulot d'étranglement pour l'instant. J'ai essayé d'utiliser les arbres d'expression et l'émission, mais j'ai rencontré un obstacle. Si je parviens à les faire fonctionner, je mettrai ce message à jour.

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);
        }
    }
}

Answer 3

Un modèle facile qui debe ne le fera pas travail pour de nombreuses collections :

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

Malheureusement, je ne sais pas si Microsoft a fait quelque chose pour empêcher l'appel de MemberwiseClone dans des endroits où il ne devrait pas être appelé (par exemple en déclarant quelque chose d'autre qu'une méthode - comme peut-être une classe - avec le nom MemberwiseClone), donc je ne sais pas comment on peut dire si une telle approche a des chances de fonctionner.

Je pense qu'il y a une bonne raison pour qu'une collection standard ne supporte pas une méthode de clonage publique mais seulement une méthode protégée : il est possible qu'une classe qui dérive d'une collection puisse se casser sévèrement si elle est clonée, et si la méthode de clonage de la classe de base est publique, il n'y a aucun moyen d'empêcher un objet d'une classe dérivée d'être donné au code qui s'attend à le cloner.

Ceci étant dit, il aurait été bien que .net inclue cloneableDictionary et d'autres classes de ce type comme types standard ( bien qu'évidemment pas mis en œuvre essentiellement comme ci-dessus).

Answer 4

Serait-il possible d'utiliser la méthode serialize -> de-serialize ?

http://stackoverflow.com/questions/78536/cloning-objects-in-c

Answer 5

Un clone en O(n) est aussi bon qu'il peut l'être, théoriquement, pour cloner deux ensembles qui ne partagent pas la même structure de données sous-jacente.

Vérifier si un élément se trouve ou non dans un HashSet doit être une opération en temps constant (c'est-à-dire O(1)).

Vous pourriez donc créer un wrapper qui ne ferait qu'envelopper un HashSet existant et conserverait tous les nouveaux ajouts, mais cela semble plutôt pervers.

Quand vous dites "efficace", vous voulez dire "plus efficace que la méthode O(n) existante". Je pense qu'il est impossible d'être plus efficace que O(n) sans jouer à des jeux sémantiques sérieux sur la signification du mot "clone".