使用不可变堆栈

本文关键字：堆栈 不可变 | 更新日期: 2023-09-27 18:32:49

我今天看到帖子宣布发布Microsoft.Bcl.Immutable NuGet包的稳定版本。

我想知道：不可变堆栈的用途是什么？我找不到有用的示例或场景。可能是我对不变性的理解。如果你能阐明为什么这个东西可能有用，最好有一个具体的例子，那就太好了。

使用不可变堆栈

这个集合库背后的想法是提供集合，当更改时，会生成同一集合的新版本，其中集合的所有旧版本仍然有效。

它类似于版本控制系统的工作方式：您可以更改代码，并将更改提交到服务器，从而生成新版本的源代码树。同时，您仍然可以签出任何以前的修订版。

对于不可变集合，您可以通过保留指向不会更改的集合的指针来保留对旧版本(实质上是不可变快照(的访问。

您可能会争辩说，这种情况对堆栈不太有用，因为您可能使用堆栈来添加和检索每个项目一次，并保留顺序。通常，堆栈的使用与在单个执行线程上运行的代码密切相关。

但是现在我正在打字，如果你有一个需要跟踪堆栈中的某个状态的惰性解析器，我可以想到一个特定的用例。然后，可以将指向不可变堆栈的指针保存为初始分析期间的状态，而无需复制，并在分析延迟工作时检索它。

我喜欢不可变的集合，但它们通常感觉像是需要解决问题的解决方案。由于它们的实现方式，它们可能会出乎意料地慢：它们非常努力地有效地使用内存，代价是使foreach循环和索引器在算法上更加复杂。以内存的丰富程度，很难证明这一成本是合理的。网络上缺乏有关成功使用不可变集合(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>实例。
  • 如果您存储对Parent TreeNode的引用，则很容易创建一个循环循环，该循环将导致诸如查找根节点之类的操作永远不会终止，并且您要么得到堆栈溢出，要么得到无限循环。另一方面，ImmutableStack<T>可以通过Pop-ing上升，保证它将终止。
    • 使用集合(ImmutableStack<T>(的事实意味着您可以通过简单地确保parent TreeNode在构造TreeNode时不会发生两次来防止循环的发生。

这只是开始。我认为ImmutableStack<T>使树木操作更简单、更安全。您可以(安全地(在其上使用 LINQ。想知道一个TreeNode是否是另一个的后代吗？你可以简单地做ParentStack.Any(node => node == otherNode)

更一般地说，ImmutableStack<T>类适用于任何情况，您希望Stack<T>可以保证永远不会被修改，或者您需要一种简单的方法来获取Stack<T>的"快照"，但又不想创建该堆栈的一堆副本。如果您有一系列嵌套步骤，则可以使用ImmutableStack<T>来跟踪进度，因此当步骤完成时，它可以将工作移交给其父步骤。当您尝试并行工作时，它的不可变性质特别有用。

相关文章：