ハッシュセットをクローンする効率的な方法？

StackOverflow https://stackoverflow.com/questions/3927789

質問

数日前、私は答えました 興味深い質問 そのことについて HashSet<T>. 。ハッシュセットのクローニングを含む可能性のある解決策が含まれ、私の答えでは、次のようなことをすることを提案しました。

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

このアプローチは非常に簡単ですが、私はそれが非常に非効率的だと思います：新しいもののコンストラクター HashSet<T> 元のハッシュセットから各アイテムを個別に追加する必要があり、 まだ存在していないかどうかを確認してください. 。これは明らかに時間の無駄です：ソースコレクションは ISet<T>, 、複製を封じ込めないことが保証されています。その知識を利用する方法があるはずです...

理想的には、 HashSet<T> 実装する必要があります ICloneable, 、しかし残念ながらそうではありません。また、リフレクターにチェックして、次のことを確認しました HashSet<T> ソースコレクションがハッシュセットである場合、コンストラクターは具体的なことをしましたが、そうではありません。おそらくプライベートフィールドでの反射を使用することで実行できますが、それは醜いハックになるでしょう...

それで、誰かがハッシュセットをより効率的にクローンするための巧妙なソリューションを思いついたのでしょうか？

（この質問は純粋に理論的であることに注意してください、私は実際のプログラムでそれをする必要はありません）

役に立ちましたか？

解決

あなたが本当にクローンする最も効率的な方法を望んでいたなら HashSet<T>, 、あなたは次のことをします（ただし、保守性の犠牲を払って）

  1. リフレクターまたはデバッガーを使用して、どのフィールドを正確に把握しますか HashSet<T> コピーする必要があります。各フィールドに対してこれを再帰的に行う必要がある場合があります。
  2. 使用する Reflection.Emit または、表現ツリーを使用して、すべてのフィールドの必要なコピーを実行するメソッドを生成します。各フィールドの値をコピーする他の生成されたメソッドを呼び出す必要がある場合があります。プライベートフィールドに直接アクセスする唯一の方法であるため、ランタイムコード生成を使用しています。
  3. 使用する FormatterServices.GetUninitializedObject(...) 空白のオブジェクトをインスタンス化します。ステップ2で生成されたメソッドを使用して、元のオブジェクトを新しい空白オブジェクトにコピーします。

他のヒント

編集： 綿密な検査の後、これは良いアイデアではないようであり、元のハッシュセットの60未満の要素が少ないと、以下の方法は新しいハッシュセットを作成するだけで遅くなるように見えます。

免責事項： これは機能しているようですが、クローン化されたハッシュセットをシリアル化しようとする場合は、あなた自身の責任で使用します。

また、この問題に直面し、それを刺しました。以下に、fieldinfo.getValueとsetValueを使用して必要なフィールドをコピーする拡張メソッドがあります。ハッシュセット（IENUMERABLE）を使用するよりも速く、元のハッシュセットの要素の量に依存する量がどれだけ速くなります。 1,000の要素の場合、差は係数7の約7です。100,000の要素が係数3になります。

さらに速いかもしれない他の方法がありますが、これは今のところ私にとってボトルネックを取り除いています。 ExpressionTreeを使用してエミッティングを試みましたが、この投稿を更新するように動作させた場合は、障害を発しました。

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

両方のバージョンの.NETフレームワークソースコードを確認しました 4.5.2 およびバージョン 4.7.2。バージョン4.7.2には、内部クローンロジックを使用して、渡されたコレクションがハッシュセットのタイプであるときに処理するコンストラクターに最適化があります。また、このロジックが機能するためには、コンストラクターに比較を渡す必要があります。バージョン4.5.2には、この最適化がないようです。

例：

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

簡単なパターン したほうがいい しない 多くのコレクションで働く：

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を呼び出すのを防ぐために何かをしたことを知りません（例：メソッド以外のものを宣言します - クラスのようなもの - メンバーウィセクロンという名前）そのようなアプローチが機能する可能性があるかどうかを知る方法を知ってください。

標準的なコレクションがパブリッククローンメソッドをサポートするのではなく、保護された方法のみをサポートするための公正な理由があると思います。コレクションに由来するクラスがクローン化された場合、ベースクラスのクローニング方法が公開されている場合は、派生クラスのオブジェクトが、それをクローンすることを期待するコードに与えられないようにする方法。

そうは言っても、.NETがCloneadedictionaryやその他の標準タイプなどのクラスが含まれている場合は良かったでしょう。明らかにそうではありませんが 上記のように本質的に実装されています）。

O（n）クローンは、理論的には、同じ基礎となるデータ構造を共有しない2つのセットをクローンするために得られるほど優れています。

要素がハッシュセットにあるかどうかを確認することは、一定の時間（つまり、o（1））操作である必要があります。

したがって、既存のハッシュセットをラップして新しい追加を保持するラッパーを作成できますが、それはかなりひねくれているようです。

「効率的」と言うと、「既存のO（n）メソッドよりも効率的」を意味します。「クローン」の意味についてかなり深刻なセマンティックゲームをプレイせずに、o（n）よりも実際に効率的になることはできません。

ただのランダムな考え。それは愚かなかもしれません。

彼らはiClonableを実装せず、コンストラクターはソースが同じタイプであるという知識を使用していないため、1つのオプションが残っていると思います。最適化されたバージョンを実装し、タイプに拡張メソッドとして追加します。

何かのようなもの：

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);
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top