不変のスタックの使用

Question

今日、Microsoft.Bcl.Immutable NuGetパッケージの安定版のリリースを発表したpostを見ました。

不変のスタックの使用法は何でしょうか？それが役に立つと思われる例やシナリオを見つけることができません。不変性の私の理解かもしれない。このことが、具体的な例を挙げて、どのように役立つかもしれないのかを明らかにすればいいでしょう。

Answer 1

コレクションのこのライブラリの背後にあるアイデアは、コレクションの古いバージョンすべてが有効である同じコレクションの新しいバージョンを作成するコレクションを提供することです。

バージョン管理システムの動作と似ています。ソースツリーの新しいバージョンを作成して、コードを変更してサーバーに変更をコミットすることができます。それまでの間は、以前のリビジョンをチェックアウトすることができます。

不変のコレクションの場合、変更されないコレクションへのポインタを保持することによって、古いバージョン（本質的には不変のスナップショット）にアクセスすることができます。

このシナリオはスタックにはあまり役に立ちませんが、おそらくスタックを使用して各アイテムを正確に1回追加したり取得したり、順序を保持することができると主張できます。通常、スタックの使用は、単一の実行スレッドで実行されているコードに非常に結びついています。

しかし、入力したところで、スタックの状態を追跡する必要がある遅延パーサーがあると、特定の使用例が考えられます。その後、初期解析中の状態で、コピーせずにポインタを不変のスタックに保存し、遅延した作業を解析するときにそれを取得することができます。

Answer 2

最後の要求が優先度として扱われるため、要求が単一のパイプラインで受信され、スタックに格納されるというシナリオを想像してください。次に、スレッド化されたリクエストコンシューマが用意されています。各リクエストコンシューマは、特定のタイプのリクエストを処理します。メインマーシャリングコードはスタックを構築し、すべてのコンシューマが準備が整うと、そのスタックをコンシューマに渡して新しいスタックを開始します。

スタックが変更可能であれば、各コンシューマは並行して実行され、他のコンシューマのためにどのステージでも変更できる同じスタックを共有します。スタックからポップするアイテムを制御して、それらがすべて同期していることを確認するには、ロックが必要です。消費者がスタックがロックされているアクションを完了するまでに長時間を要した場合、他のスタックはすべて停止します。

不変のスタックを持つことによって、各消費者は他の消費者を気にせずにスタックに必要なことを自由に行うことができます。スタックからアイテムをポップすると、新しいアイテムが返され、オリジナルは変更されません。したがって、ロックは不要で、各スレッドは他のスレッドを気にせずに実行することができます。

Answer 3

私は不変のコレクションが大好きですが、しばしば問題が必要な解決策のように感じます。 how they are implementedのためにunexpectedly slowになる可能性があります。foreachループとインデクサーをアルゴリズム的に複雑にするという代償を払って、メモリを効率的に使用することは非常に難しいです。豊富な記憶があるので、そのコストを正当化することは難しいかもしれません。不変のコレクションの使用に関する成功情報（ImmutableArray<T>以外）については、Web上で見つかる情報が不足しています。それを修正しようとして、ImmutableStack<T>が本当に便利であると判明したこの3年以上前の質問に対する回答を追加すると思いました。

public class TreeNode 
{ 
    public TreeNode Parent { get; private set; } 
    public List<TreeNode> ChildNodes { get; set; } 

    public TreeNode(TreeNode parent) 
    { 
     Parent = parent; 
    } 
} 

私はこの基本的なパターンを何度も何度に従い、実際には、それは常に私のために働いたのクラスを作成しました：

は、この非常に基本的なツリー状の構造を考えてみましょう。さらに最近では、私はこのような何かを開始しました：さまざまな理由

public class TreeNode 
{ 
    public ImmutableStack<TreeNode> NodeStack { get; private set; } 
    public ImmutableStack<TreeNode> ParentStack { get { return NodeStack.IsEmpty ? ImmutableStack<TreeNode>.Empty : NodeStack.Pop(); } } 
    public TreeNode Parent { get { return ParentStack.IsEmpty ? null : ParentStack.Peek(); } } 

    public ImmutableArray<TreeNode> ChildNodes { get; set; } 

    public TreeNode(TreeNode parent) 
    { 
     if (parent == null) 
      NodeStack = ImmutableStack<TreeNode>.Empty; 
     else 
      NodeStack = parent.NodeStack.Push(this); 
    } 
} 

を、私はルートに横断できるImmutableStack<T>TreeNodeのインスタンスではなく、単に参照を格納好むようになりましたインスタンスParentに送信します。

• ImmutableStack<T>の実装は基本的にリンクリストです。 ImmutableStack<T>の各インスタンスは、実際にはリンクされたリストのノードです。だからこそParentStackのプロパティーはPopがNodeStackです。 ParentStackはImmutableStack<T>の同じインスタンスを返します。Parent.NodeStackとなります。
• ParentTreeNodeへの参照を保存すると、ルートノードが決して終了しないなどの操作を引き起こす循環ループを作成しやすくなり、スタックオーバーフローまたは無限ループが発生することがあります。一方、ImmutableStack<T>は、Pop-ingによって上がることができ、それが終了することを保証する。
  • あなたがコレクション（ImmutableStack<T>）を使用するということは、あなたは、単にTreeNodeを構築するときparentTreeNodeが二回発生していないことを確認することによって、最初の場所で起こってから、円形のループを防止することができることを意味します。ただで開始することです

。私はImmutableStack<T>が木の操作をより簡単で安全にすると思います。 LINQを（安全に）使用することができます。 TreeNodeが別のものの子孫かどうかを知りたいですか？あなたは、単により一般的

ParentStack.Any(node => node == otherNode)を行うことができ、ImmutableStack<T>クラスはあなたが保証することができStack<T>は変更されることはありません、またはあなたがStack<T>の「スナップショット」を取得する簡単な方法が必要ですが、希望のいずれかの場合であるが、作成したくないスタックのコピーを作成します。一連のネストされたステップがある場合は、ImmutableStack<T>を使用して進捗状況を追跡することができます。ステップが完了すると、親ステップに作業を引き渡すことができます。その不変の性質は、あなたが並行して仕事をしようとしているときに特に役立ちます。