Эффективный способ клонирования HashSet <T>?

Ответ 1

Если вам действительно нужен самый эффективный способ клонирования HashSet<T>, вы должны сделать следующее (но, возможно, за счет ремонтопригодности)

• Используйте рефлектор или отладчик, чтобы выяснить, какие поля в HashSet<T> необходимо скопировать. Возможно, вам понадобится сделать это рекурсивно для каждого поля.
• Используйте Reflection.Emit или используйте деревья выражений для генерации метода, который выполняет необходимое копирование всех полей. Может потребоваться вызвать другие сгенерированные методы, которые копируют значение каждого поля. Мы используем генерацию кода времени выполнения, поскольку это единственный способ прямого доступа к закрытым полям.
• Используйте FormatterServices.GetUninitializedObject(...) для создания пустого объекта. Используйте метод, сгенерированный на шаге 2, чтобы скопировать исходный объект в новый пустой объект.

Ответ 2

РЕДАКТИРОВАТЬ: После более тщательного изучения это не кажется хорошей идеей, при этом менее 60 элементов в исходном хэш-наборе метод ниже выглядит медленнее, чем просто создавая новый хешсет. p >

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: это работает, но использует на свой страх и риск, если вы собираетесь сериализовать клонированные хешеты, которые вы, вероятно, захотите скопировать SerializationInfo m_siInfo.

Я также столкнулся с этой проблемой и взял на нее удар, ниже вы найдете метод расширения, который использует FieldInfo.GetValue и SetValue для копирования необходимых полей. Это быстрее, чем использование HashSet (IEnumerable), насколько это зависит от количества элементов исходного хэшета. Для 1000 элементов разница составляет около фактора 7. С 100 000 элементов его примерно в 3 раза.

Есть и другие способы, которые могут быть еще быстрее, но на этот раз я избавился от узкого места. Я пробовал использовать expressiontrees и испускать, но попал в блокпост, если я заставлю их работать. Ill update this 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);
        }
    }
}

Ответ 3

Простой шаблон, который должен не будет работать для многих коллекций:

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

К сожалению, я не знаю, что Microsoft сделала что-либо, чтобы предотвратить вызов MemberwiseClone в тех местах, где он не должен быть вызван (например, объявление чего-то другого, кроме метода - например, возможно, класса - с именем MemberwiseClone), поэтому я не знаю, как можно определить, может ли такой подход работать.

Я считаю, что справедливая причина для стандартной коллекции не поддерживать общедоступный метод клонирования, а только защищенный: возможно, что класс, который происходит из коллекции, может сильно нарушиться при клонировании, а если метод клонирования базового класса public там нет способа предотвратить предоставление объекта производного класса коду, который ожидает его клонирования.

Было сказано, что было бы неплохо, если бы .net включал cloneableDictionary и другие такие классы, как стандартные типы ( хотя, очевидно, не, реализованные по существу, как указано выше).

Ответ 4

O (n) -лон так же хорош, как теоретически, он может клонировать два набора, которые не будут использовать одну и ту же базовую структуру данных.

Проверка наличия или отсутствия элемента в HashSet должна быть постоянной (то есть O (1)).

Итак, вы можете создать оболочку, которая просто завернет существующий HashSet и удержит любые новые дополнения, но это кажется довольно извращенным.

Когда вы говорите "эффективный", вы имеете в виду "более эффективный, чем существующий метод O (n)", - я полагаю, вы не можете получить более эффективную, чем O (n), не играя довольно серьезные семантические игры о том, что "клонировать" 'означает.

Ответ 5

Просто случайная мысль. Это может быть глупо.

Поскольку они не реализовали ICloneable, и конструктор не использует знания о том, что источник имеет тот же тип, я думаю, мы остаемся с одним вариантом. Реализация оптимизированной версии и добавление ее в качестве метода расширения для типа.

Что-то вроде:

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

Затем ваш код из вопроса будет выглядеть так:

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