5

C＃で永続的なコレクション（リストなど）を作成することを考えていますが、優れたAPIを見つけることができません。

Clojureの意味で「 persistent」を使用します。永続リストは、参照セマンティクスではなく値セマンティクスを持っているかのように動作するリストですが、大きな値型をコピーするオーバーヘッドは発生しません。永続コレクションは、コピーオンライトを使用して内部構造を共有します。擬似コード：

l1 = PersistentList()
l1.add("foo")
l1.add("bar")
l2 = l1
l1.add("baz")

print(l1) # ==> ["foo", "bar", "baz"]
print(l2) # ==> ["foo", "bar"]
# l1 and l2 share a common structure of ["foo", "bar"] to save memory

Clojureはそのようなデータ構造を使用しますが、さらにClojureではすべてのデータ構造が不変です。すべてのコピーオンライト処理を実行するにはオーバーヘッドが発生するため、Clojureは、データ構造を他のユーザーと共有していないことが確実な場合に使用できる一時的なデータ構造の形式で回避策を提供します。データ構造への唯一の参照がある場合は、すべてのコピーオンライトオーバーヘッドを実行するのではなく、直接変更してみませんか。

この効率を上げる1つの方法は、データ構造の参照カウントを維持することです（ただし、Clojureがそのように機能するとは思いません）。refcountが1の場合、唯一の参照を保持しているため、更新を破壊的に行います。refcountが高い場合は、他の誰かが値型のように動作するはずの参照を保持しているため、他のリファラーの邪魔にならないようにコピーオンライトを実行してください。

このようなデータ構造に対するAPIでは、refcountingを公開して、APIの使用性を大幅に低下させたり、refcountingを実行できなかったりして、すべての操作がCOWされた場合、またはAPIで不要なコピーオンライトのオーバーヘッドが発生する可能性があります。値型の動作が失われ、ユーザーはCOWを手動で実行するタイミングを管理する必要があります。

C＃に構造体のコピーコンストラクターがある場合、これは可能です。実際のデータ構造への参照を含む構造体を定義し、その構造体のコピーコンストラクタとデストラクタですべてのincref（）/ decref（）呼び出しを実行できます。

APIユーザーを煩わせることなく、C＃で参照カウントや構造体コピーコンストラクターのようなことを自動的に行う方法はありますか？

編集：

  • 明確にするために、私はAPIについて質問しています。Clojureには、Javaで記述されたこれの実装がすでにあります。
  • すべての操作でCOWされる実際のコレクションを参照する構造体を使用することにより、このようなインターフェイスを作成することは確かに可能です。refcountingの使用は、不要なCOWを回避するための最適化ですが、正常なAPIでは明らかに不可能です。
4

4 に答える 4

3

厳密に言えば、あなたがしようとしていることは不可能です。参照カウントを行う静的関数を使用することで近づくことができますが、それがひどい口当たりの良いオプションではないことは理解しています。

出来たとしても、これは避けたい。あなたが説明するセマンティクスはClojureで役立つかもしれませんが、値型と参照型のセマンティクスの間のこのクロスは、ほとんどのC＃開発者を混乱させるでしょう（可変値型、または可変の値型セマンティクスを持つ型も通常悪と見なされます）。

于 2010-11-16T00:13:15.670 に答える
1

refcounting の代わりにWeakReferenceクラスを使用すると、refcounting がもたらす利点の一部を得ることができます。WeakReference 内のオブジェクトへの唯一のコピーを保持すると、ガベージ コレクションが実行されます。WeakReference には、そうであったかどうかを調べるためのフックがいくつかあります。

編集 3:このアプローチはトリックを行いますが、C# コレクションの値のセマンティクスを追求しないようにしてください。あなたの構造のユーザーは、プラットフォームでこの種の動作を期待していません。これらのセマンティクスにより、混乱が生じ、間違いが発生する可能性があります。

編集 2: 例を追加しました。@AdamRobinson: 残念ながら、どのWeakReferenceように使用できるかが明確ではありませんでした。ほとんどの場合、すべての操作で素朴な Copy-On-Write を実行するよりもさらに悪い可能性があります。これはガベージ コレクターの呼び出しによるものです。したがって、これは単なる学術的な解決策であり、本番システムでの使用はお勧めできません。しかし、それはあなたが求めることを正確に行います。

class Program
{

  static void Main(string[] args)
  {
    var l1 = default(COWList);
    l1.Add("foo"); // initialize
    l1.Add("bar"); // no copy
    l1.Add("baz"); // no copy
    var l2 = l1;
    l1.RemoveAt(0); // copy
    l2.Add("foobar"); // no copy
    l1.Add("barfoo"); // no copy
    l2.RemoveAt(1); // no copy
    var l3 = l2;
    l3.RemoveAt(1); // copy
    Trace.WriteLine(l1.ToString()); //  bar baz barfoo
    Trace.WriteLine(l2.ToString()); // foo baz foobar
    Trace.WriteLine(l3.ToString()); // foo foobar
  }
}

struct COWList
{
  List<string> theList; // Contains the actual data
  object dummy; // helper variable to facilitate detection of copies of this struct instance.
  WeakReference weakDummy; // helper variable to facilitate detection of copies of this struct instance.

  /// <summary>
  /// Check whether this COWList has already been constructed properly.  
  /// </summary>
  /// <returns>true when this COWList has already been initialized.</returns>
  bool EnsureInitialization()
  {
    if (theList == null)
    {
      theList = new List<string>();
      dummy = new object();
      weakDummy = new WeakReference(dummy);
      return false;
    }
    else
    {
      return true;
    }
  }

  void EnsureUniqueness()
  {
    if (EnsureInitialization())
    {

      // If the COWList has been copied, removing the 'dummy' reference will not kill weakDummy because the copy retains a reference.
      dummy = new object();

      GC.Collect(2); // OUCH! This is expensive. You may replace it with GC.Collect(0), but that will cause spurious Copy-On-Write behaviour.
      if (weakDummy.IsAlive) // I don't know if the GC guarantees detection of all GC'able objects, so there might be cases in which the weakDummy is still considered to be alive.
      {
        // At this point there is probably a copy.
        // To be safe, do the expensive Copy-On-Write
        theList = new List<string>(theList);
        // Prepare for the next modification
        weakDummy = new WeakReference(dummy);
        Trace.WriteLine("Made copy.");

      }
      else
      {
        // At this point it is guaranteed there is no copy.
        weakDummy.Target = dummy;
        Trace.WriteLine("No copy made.");

      }
    }
    else
    {

      Trace.WriteLine("Initialized an instance.");

    }
  }

  public void Add(string val)
  {
    EnsureUniqueness();
    theList.Add(val);
  }

  public void RemoveAt(int index)
  {
    EnsureUniqueness();
    theList.RemoveAt(index);
  }

  public override string ToString()
  {
    if (theList == null)
    {
      return "Uninitialized COWList";
    }
    else
    {
      var sb = new StringBuilder("[ ");
      foreach (var item in theList)
      {
        sb.Append("\"").Append(item).Append("\" ");
      }
      sb.Append("]");
      return sb.ToString();
    }
  }
}

これは以下を出力します:

Initialized an instance.
No copy made.
No copy made.
Made copy.
No copy made.
No copy made.
No copy made.
Made copy.
[ "bar" "baz" "barfoo" ]
[ "foo" "baz" "foobar" ]
[ "foo" "foobar" ]
于 2010-11-16T00:09:55.867 に答える
0

私の柔軟なツリーコレクションオブジェクトにこのようなものを置きたいのですが、値型のセマンティクス（.netでは本質的に不可能です）を使用するのではなく、クローンに「仮想」を生成させることによってです。コレクション内のすべてのノードを実際に複製するのではなく、ディープクローンを作成します。正確な参照カウントを維持しようとする代わりに、すべての内部ノードには次の3つの状態があります。

  1. フレキシブル
  2. SharedImmutable
  3. UnsharedMutable

sharedImmutableノードでClone（）を呼び出すと、元のオブジェクトが生成されます。フレキシブルノードでクローンを呼び出すと、SharedImmutableノードに変わります。共有されていない可変ノードでCloneを呼び出すと、そのすべての子孫のクローンを保持する新しいノードが作成されます。新しいオブジェクトはFlexibleになります。

オブジェクトを書き込む前に、UnsharedMutableにする必要があります。オブジェクトがまだUnsharedMutableになっていない場合は、その親（アクセス元のノード）をUnsharedMutable（再帰的に）にします。次に、オブジェクトがSharedImmutableの場合は、（ForceCloneメソッドを使用して）クローンを作成し、新しいオブジェクトを指すように親のリンクを更新します。最後に、新しいオブジェクトの状態をUnsharedMutableに設定します。

この手法の重要な側面は、データを保持し、データへのインターフェイスを提供するための個別のクラスを持つことです。次のようなステートメント

MyCollection ["this"] ["that"] ["theOther"]。Add（ "George"）
インデックス作成操作で、MyCollectionへの参照を保持するインデクサークラスを返すようにすることで評価する必要があります。その時点で、「追加」メソッドは、必要なコピーオンライト操作を実行するために必要な中間ノードに作用することができます。

于 2011-01-27T20:02:39.820 に答える
0

私はあなたが何を求めているかを読み、「ターミナルサーバー」タイプの API 構造を考えています。

まず、「サーバー」となるスレッドセーフな内部シングルトン クラスを定義します。それは実際にあなたが見ているデータを保持しています。設定または取得される値の文字列を取得する Get および Set メソッドを公開します。このメソッドは、ReaderWriterLock によって制御され、誰でも値を読み取ることができるようにしますが、だれかが書き込んでいる間ではなく、一度に 1 人だけが書き込めるようにします。 .

次に、「端末」であるクラスのファクトリを提供します。このクラスは公開され、内部シングルトンへの参照が含まれます (それ以外の場合は表示されません)。これには、実際にはシングルトン インスタンスの単なるパススルーであるプロパティが含まれます。このようにして、すべて「サーバー」から同じデータを参照し、そのデータをスレッドセーフな方法で変更できる多数の「端末」を提供できます。

コピー コンストラクターと、各インスタンスがアクセスする値のリストを使用して、コピー型の情報を提供できます。また、値の名前をオブジェクトのハンドルとマッシュアップして、L1 と L2 が A を共有しているが、L3 は別々に宣言されているために異なる A を持つ場合をサポートすることもできます。または、L3 は、L1 と L2 が持つ同じ A を取得できます。これをどのように構造化しても、基本的な .NET での動作とは異なるため、どのように動作すると予想されるかを非常に明確に文書化します。

于 2010-11-16T00:16:19.393 に答える