Pregunta ¿Manera eficiente de clonar un HashSet ?


Hace unos días, respondí una pregunta interesante en SO sobre HashSet<T>. Una posible solución involucraba clonar el hashset, y en mi respuesta sugerí hacer algo como esto:

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

Aunque este enfoque es bastante sencillo, sospecho que es muy ineficiente: el constructor del nuevo HashSet<T> necesita agregar por separado cada elemento del hashset original, y verificar si no está presente. Esto es claramente una pérdida de tiempo: dado que la colección fuente es una ISet<T>, se garantiza que no contiene duplicados. Debería haber una forma de aprovechar ese conocimiento ...

Idealmente, HashSet<T> debería implementar ICloneable, pero lamentablemente no es el caso. También verifiqué con Reflector para ver si el HashSet<T> constructor hizo algo específico si la colección de origen era un hashset, pero no es así. Probablemente podría hacerse utilizando la reflexión en campos privados, pero sería un hack feo ...

Entonces, ¿se le ocurrió a alguien una solución inteligente para clonar un hashset de manera más eficiente?

(Tenga en cuenta que esta pregunta es puramente teórica, no necesito hacer eso en un programa real)


32
2017-10-13 20:37


origen


Respuestas:


Si realmente deseaba la manera más eficiente de clonar HashSet<T>, harías lo siguiente (pero posiblemente a costa de la capacidad de mantenimiento)

  1. Utilice el reflector o el depurador para averiguar exactamente en qué campos HashSet<T> necesita ser copiado Es posible que deba hacer esto recursivamente para cada campo.
  2. Utilizar Reflection.Emit o use árboles de expresiones para generar un método que haga la copia necesaria de todos los campos. Puede ser necesario llamar a otros métodos generados que copian el valor de cada campo. Estamos utilizando la generación de código de tiempo de ejecución porque es la única manera de acceder directamente a los campos privados.
  3. Utilizar FormatterServices.GetUninitializedObject(...) para crear una instancia de un objeto en blanco. Use el método generado en el paso 2 para copiar el objeto original al nuevo objeto en blanco.

9
2017-11-04 18:47



EDITAR: Después de una inspección más cercana, esta no parece ser una buena idea, con menos de 60 elementos en el hashset original, el método siguiente parece ser más lento que crear un nuevo hashset.

RENUNCIA: esto parece funcionar, pero utilícelo bajo su propio riesgo, si va a serializar los conjuntos de claves duplicados, probablemente quiera copiar SerializationInfo m_siInfo.

También me enfrenté a este problema y lo apuñalé, a continuación encontrará un método de extensión que usa FieldInfo.GetValue y SetValue para copiar los campos requeridos. Es más rápido que usar HashSet (IEnumerable), cuánto depende de la cantidad de elementos en el hashset original. Para 1,000 elementos, la diferencia es aproximadamente un factor 7. Con 100,000 elementos, se trata de un factor 3.

Hay otras formas que pueden ser aún más rápidas, pero esto me ha librado del cuello de botella por ahora. Intenté usar expressiontrees y emitir pero toco un roadblock, si logro que funcionen, actualizaré esta publicación.

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

2
2018-05-24 11:04



Patrón fácil que debería  no lo hará trabajo para muchas colecciones:

Clase clonableDiccionario (De T, U)
    Diccionario heredado (de T, U)
    Función clone () As Dictionary (Of T, U)
        Devuelve CType (Me.MemberwiseClone, cloneableDict (Of T, U))
    Función final
Clase final

Lamentablemente, no sé si Microsoft hizo algo para evitar llamar a MemberwiseClone en lugares donde no debería llamarse (por ejemplo, declarar algo distinto a un método, como una clase, con el nombre MemberwiseClone), así que no lo hago. saber cómo se puede saber si es probable que ese enfoque funcione.

Creo que hay una buena razón para que una colección estándar no admita un método público de clonación, sino solo uno protegido: es posible que una clase que se deriva de una colección se rompa severamente si se clona, ​​y si el método de clonación de la clase base es público no hay forma de evitar que un objeto de una clase derivada se le dé al código que espera clonarlo.

Habiendo dicho eso, habría sido bueno si .net incluye cloneableDictionary y otras clases similares como tipos estándar (aunque obviamente no implementado esencialmente como arriba).


0
2017-10-15 22:18



El clon O (n) es tan bueno como se puede obtener, teóricamente, para clonar dos conjuntos que no compartan la misma estructura de datos subyacente.

Comprobar si un elemento está o no en un HashSet debe ser una operación de tiempo constante (es decir, O (1)).

De modo que podría crear un contenedor que simplemente envolviera un HashSet existente y aferrarse a cualquier nueva adición, pero eso parece bastante perverso.

Cuando dice 'eficiente', quiere decir 'más eficiente que el método O (n)' existente - postulo que en realidad no puede ser más eficiente que O (n) sin jugar juegos semánticos bastante serios sobre lo que significa 'clon'.


-1
2017-11-03 18:43



Solo un pensamiento al azar. Puede ser tonto.

Como no implementaron ICloneable, y el constructor no utiliza el conocimiento de que la fuente es del mismo tipo, creo que nos queda una opción. Implementar la versión optimizada y agregarla como un método de extensión para el tipo.

Algo como:

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

Entonces, su código de la pregunta se vería así:

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

-3
2017-11-03 14:54