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

Question

Несколько дней назад я ответил на интересный вопрос о SO около HashSet<T>. Возможное решение заключалось в клонировании хэш-набора, и в своем ответе я предложил сделать что-то вроде этого:

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

Хотя этот подход довольно прост, я подозреваю, что он очень неэффективен: конструктору нового HashSet<T> необходимо отдельно добавить каждый элемент из исходного хэш-набора, и проверить, если он еще не существует, Это явно пустая трата времени: так как исходная коллекция - ISet<T>, она гарантированно не содержит дубликатов. Должен быть способ воспользоваться этими знаниями ...

В идеале HashSet<T> должен реализовывать ICloneable, но, к сожалению, это не так. Я также проверил с помощью Reflector, чтобы убедиться, что конструктор HashSet<T> сделал что-то конкретное, если исходная коллекция была хэш-набором, но это не так. Вероятно, это можно сделать, используя отражение в приватных полях, но это будет ужасный хак ...

Итак, кто-то придумал умное решение для более эффективного клонирования хэш-набора?

(Обратите внимание, что этот вопрос чисто теоретический, мне не нужно делать это в реальной программе)

Answer 1

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

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

Answer 2

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

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

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

Существуют и другие способы, которые могут быть даже быстрее, но на данный момент это избавило меня от узкого места.Я пытался использовать expresstrees и emitting, но наткнулся на контрольно-пропускной пункт, если я заставлю их работать, я обновлю этот пост.

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

Я проверил исходный код .NET Framework для версии 4.5.2 и версии 4.7.2 . Версия 4.7.2 действительно имеет оптимизацию в конструкторе для обработки, когда переданная коллекция имеет тип HashSet с использованием некоторой внутренней логики клонирования. Вы должны также передать компаратор в конструктор, чтобы эта логика работала. Версия 4.5.2 НЕ имеет этой оптимизации, кажется.

Пример:

var clonedSet = new HashSet(set, set.Comparer);

Answer 4

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

Проверка того, находится ли элемент в HashSet, должна выполняться с постоянным временем (т. Е. O (1)).

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

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

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

Answer 6

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

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 и другие такие классы в качестве стандартных типов (, хотя, очевидно, не реализован по существу, как указано выше).