使用不可變的堆棧

Question

我已經看到post今天宣佈發佈穩定版本的Microsoft.Bcl.Immutable NuGet包。

我想知道：對於不可變的堆棧會有什麼用法？我找不到有用的示例或場景。可能是我對不變性的理解。如果你可以闡明爲什麼這個東西可能是有用的，最好用一個具體的例子，這將是很好的。

Answer 1

這個收藏品庫背後的想法是提供收藏品，當收藏品發生變化時產生相同收藏品的新版本，其中舊版本的收藏品仍然有效。

它與版本控制系統的工作方式類似：可以更改代碼並將更改提交到服務器，從而生成新版本的源代碼樹。在此期間，您仍然可以簽出任何以前的修訂。

對於不可變集合，通過保持指針指向不會更改的集合，可以保留舊版本（實質上是不可變的快照）。

你可能會認爲這個場景對於堆棧不太有用，因爲你可能使用堆棧來一次添加和檢索每個項目，並且還保存順序。通常，堆棧的使用與在單個執行線程上運行的代碼非常相關。

但現在我打字了，如果你有一個懶惰的解析器需要跟蹤堆棧中的某些狀態，我可以考慮一個特定的用例。然後，您可以在初始解析期間保存一個指向不可變堆棧的指針，而不進行復制，並在解析延遲工作時檢索它。

Answer 2

想象一下這樣一種場景，即請求在單個管道中進入並存儲在堆棧中，因爲最後一個請求將被視爲優先級。然後，我有一組線程化的請求使用者，每個使用者都處理特定類型的請求。主編組代碼構建堆棧，然後當所有使用者都準備好時，將該堆棧傳遞給使用者並啓動新的堆棧。

如果堆棧是可變的，那麼每個消費者將並行運行，並將共享相同的堆棧，由於其他消費者而可能在任何階段發生更改。需要鎖定才能控制彈出物品，以確保它們全部保持同步。如果消費者花費很長時間來完成堆疊被鎖定的動作，則所有其他動作都被阻止。

通過擁有一個不可改變的堆棧，每個消費者可以自由地按照自己想要的方式執行堆棧，而無需關心其他消費者。從堆棧中彈出一個項目會產生一個新項目，而原始項目不會改變。所以不需要鎖定，每個線程都可以自由運行，而不必關心其他線程。

Answer 3

我喜歡不變的集合，但他們常常覺得自己像是需要解決問題的解決方案。由於how they are implemented，它們可以是unexpectedly slow：他們儘量使用內存的效率很高，代價是使得循環和索引器的循環和索引器在算法上更加複雜。記憶豐富，可能很難證明這一成本。網上的信息很少，關於成功使用不可變的集合（ImmutableArray<T>除外）。爲了糾正這種情況，我想我會爲這個3歲以上的問題添加一個答案，以便我發現ImmutableStack<T>真正有用。

考慮這個非常基本的樹形結構：

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

由於各種原因，我已經開始喜歡儲存TreeNode的ImmutableStack<T>的情況下，我可以遍歷到根，而不是一個簡單的參考到Parent實例。

• ImmutableStack<T>的實現基本上是一個鏈表。 ImmutableStack<T>的每個實例都是鏈表上的一個節點。這就是爲什麼ParentStack財產只是Pop的NodeStack。 ParentStack將返回與Parent.NodeStack相同的ImmutableStack<T>的相同實例。
• 如果您存儲對ParentTreeNode的引用，那麼很容易創建一個循環循環，這會導致諸如查找根節點永不終止等操作，並且您將得到堆棧溢出或無限循環。另一方面，ImmutableStack<T>可以上升Pop -ing，保證它將終止。
  • 你使用一個集合（ImmutableStack<T>），這意味着您可以防止環形迴路通過簡單地確保了parentTreeNode構建TreeNode時，不會出現兩次在第一時間發生的事情。

這只是開始。我認爲ImmutableStack<T>使樹操作更簡單，更安全。你可以（安全地）使用LINQ。想知道一個TreeNode是否是另一個的後代？你可以簡單地做ParentStack.Any(node => node == otherNode)

更一般地，ImmutableStack<T>類是，你想一個Stack<T>就可以保證不會被修改，或者你需要一個簡單的方法來獲得一個Stack<T>的「快照」，但任何情況下，不想創建一堆該堆棧的副本。如果您有一系列嵌套步驟，您可以使用ImmutableStack<T>來跟蹤進度，所以當一個步驟完成時，它可以將工作交給其父步驟。當你試圖並行工作時，它的不變性特別有用。