Pertanyaan Cara efisien untuk mengkloning HashSet ?


Beberapa hari yang lalu, saya menjawab pertanyaan yang menarik pada SO tentang HashSet<T>. Solusi yang mungkin melibatkan kloning hashset, dan dalam jawaban saya, saya menyarankan untuk melakukan sesuatu seperti ini:

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

Meskipun pendekatan ini cukup mudah, saya menduga itu sangat tidak efisien: konstruktor yang baru HashSet<T> perlu secara terpisah menambahkan setiap item dari hashset asli, dan periksa apakah ini belum ada. Ini jelas membuang-buang waktu: karena pengumpulan sumber adalah a ISet<T>, dijamin tidak mengandung duplikat. Harus ada cara untuk memanfaatkan pengetahuan itu ...

Idealnya, HashSet<T> harus menerapkan ICloneable, tapi sayangnya bukan itu masalahnya. Saya juga memeriksa dengan Reflector untuk melihat apakah HashSet<T> konstruktor melakukan sesuatu yang spesifik jika koleksi sumbernya adalah hashset, tetapi tidak. Itu mungkin bisa dilakukan dengan menggunakan refleksi di lapangan pribadi, tapi itu akan menjadi peretasan yang buruk ...

Jadi, apakah seseorang muncul dengan solusi cerdas untuk mengkloning hashset dengan lebih efisien?

(Perhatikan bahwa pertanyaan ini murni teoritis, saya tidak perlu melakukannya dalam program nyata)


32
2017-10-13 20:37


asal


Jawaban:


Jika Anda benar-benar menginginkan cara yang paling efisien untuk mengkloning HashSet<T>, Anda akan melakukan hal berikut (tetapi mungkin dengan biaya pemeliharaan)

  1. Gunakan reflektor atau debugger untuk mencari tahu persis bidang apa di HashSet<T> perlu disalin. Anda mungkin perlu melakukan ini secara rekursif untuk setiap bidang.
  2. Menggunakan Reflection.Emit atau gunakan pohon ekspresi untuk menghasilkan metode yang melakukan penyalinan yang diperlukan dari semua bidang. Mungkin perlu memanggil metode lain yang dihasilkan yang menyalin nilai setiap bidang. Kami menggunakan pembuatan kode waktu proses karena ini satu-satunya cara untuk mengakses langsung bidang pribadi.
  3. Menggunakan FormatterServices.GetUninitializedObject(...) untuk instantiate objek kosong. Gunakan metode yang dihasilkan pada langkah 2 untuk menyalin objek asli ke objek kosong yang baru.

9
2017-11-04 18:47



EDIT: Setelah diamati lebih dekat, tampaknya ini bukan ide yang baik, dengan kurang dari 60 elemen dalam hashset asli, metode di bawah ini tampak lebih lambat daripada hanya membuat hashset baru.

PENOLAKAN: ini tampaknya berfungsi tetapi gunakan dengan resiko Anda sendiri, jika Anda akan membuat serialisasi kloning hashsets Anda mungkin ingin menyalin SerializationInfo m_siInfo.

Saya juga menghadapi masalah ini dan menikamnya, di bawah ini Anda akan menemukan metode ekstensi yang menggunakan FieldInfo.GetValue dan SetValue untuk menyalin bidang yang diperlukan. Lebih cepat daripada menggunakan HashSet (IEnumerable), berapa banyak tergantung pada jumlah elemen dalam hashset yang asli. Untuk 1.000 elemen perbedaannya adalah tentang faktor 7. Dengan 100.000 elemen tentang faktor 3.

Ada cara lain yang mungkin lebih cepat, tetapi ini telah menghilangkan hambatan bagi saya untuk saat ini. Saya mencoba menggunakan expressiontrees dan memancarkan tetapi menekan blokir jalan, jika saya mendapatkan orang-orang untuk bekerja Saya memperbarui posting ini.

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



Pola mudah yang mana harus  biasa berfungsi untuk banyak koleksi:

Kelas cloneableDictionary (Of T, U)
    Inherits Dictionary (Of T, U)
    Fungsi klon () Sebagai Kamus (Of T, U)
        Return CType (Me.MemberwiseClone, cloneableDict (Of T, U))
    Fungsi Akhir
Kelas Akhir

Sayangnya, saya tidak tahu bahwa Microsoft melakukan apa pun untuk mencegah pemanggilan MemberwiseClone di tempat-tempat di mana seharusnya tidak dipanggil (misalnya menyatakan sesuatu selain metode - seperti mungkin kelas - dengan nama MemberwiseClone) jadi saya tidak tahu bagaimana orang dapat mengetahui apakah pendekatan semacam itu mungkin berhasil.

Saya pikir ada alasan yang wajar untuk koleksi standar untuk tidak mendukung metode kloning publik tetapi hanya satu yang dilindungi: mungkin bahwa kelas yang berasal dari koleksi mungkin rusak parah jika dikloning, dan jika metode kloning kelas dasar adalah publik tidak ada cara untuk mencegah objek kelas turunan dari diberikan ke kode yang mengharapkan untuk mengkloningnya.

Yang telah dikatakan, itu akan menyenangkan jika .net termasuk cloneableDictionary dan kelas-kelas lain seperti tipe standar (walau jelas tidak diimplementasikan dasarnya seperti di atas).


0
2017-10-15 22:18



O (n) klon adalah sebaik yang bisa didapatkan, secara teoritis, untuk mengkloning dua set yang tidak akan berbagi struktur data dasar yang sama.

Memeriksa apakah suatu elemen dalam HashSet harus menjadi waktu yang konstan (yaitu operasi O (1)).

Jadi Anda bisa membuat pembungkus yang hanya akan membungkus HashSet yang ada dan berpegang pada tambahan baru, tapi itu tampaknya cukup jahat.

Ketika Anda mengatakan 'efisien', maksud Anda 'lebih efisien daripada metode O (n)' yang ada - saya mengandaikan Anda tidak bisa benar-benar mendapatkan lebih efisien daripada O (n) tanpa memainkan game semantik yang cukup serius tentang apa arti 'klon'.


-1
2017-11-03 18:43



Hanya pemikiran acak. Mungkin itu konyol.

Karena mereka tidak menerapkan ICloneable, dan konstruktor tidak menggunakan pengetahuan bahwa sumbernya memiliki tipe yang sama, saya kira kita hanya memiliki satu opsi. Menerapkan versi yang dioptimalkan dan menambahkannya sebagai metode perluasan ke jenisnya.

Sesuatu seperti:

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

Kemudian, kode Anda dari pertanyaan akan terlihat seperti ini:

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

-3
2017-11-03 14:54