6

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

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

4

3 回答 3

7

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

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

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

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

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

于 2013-09-26T10:16:23.680 回答
2

想象一个场景，请求来自单个管道并存储在堆栈中，因为最后一个请求将被视为优先级。然后我有一组线程请求消费者，每个消费者处理特定类型的请求。主编组代码构建堆栈，然后当所有消费者都准备好时，将该堆栈传递给消费者并启动一个新堆栈。

如果堆栈是可变的，则每个消费者将并行运行，并且将共享同一堆栈，该堆栈可能由于其他消费者而在任何阶段发生变化。需要锁定来控制从堆栈中弹出项目，以确保它们都保持同步。如果消费者需要很长时间才能完成堆栈被锁定的操作，则所有其他操作都会被搁置。

通过拥有一个不可变的堆栈，每个消费者都可以自由地对堆栈做自己想做的事情，而无需关心其他消费者。从堆栈中弹出一个项目会产生一个新项目，而原来的项目不会改变。所以不需要锁定，每个线程都可以自由运行而无需关心其他线程。

于 2013-09-26T10:34:57.917 回答
2

我喜欢不可变集合，但它们通常感觉像是需要解决问题的解决方案。由于它们的实现方式，它们可能会出乎意料地慢：它们非常努力地尝试有效地使用内存，但代价是使循环和索引器在算法上更加复杂。凭借如此丰富的内存，很难证明这一成本是合理的。在网上找不到关于成功使用不可变集合（除了）的信息。为了纠正这一点，我想我会为这个 3 年多的问题添加一个答案，这个问题是关于一个我发现真正有用的案例。foreachImmutableArray<T>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);
    }
}

由于各种原因，我开始更喜欢存储可以遍历到根ImmutableStack<T>的实例，而不是简单地引用实例。TreeNodeParent

  • ImmutableStack<T>的实现基本上是一个链表。的每个实例ImmutableStack<T>实际上是链表上的一个节点。这就是为什么该ParentStack属性只是Pop. 将返回相同的实例。NodeStackParentStackImmutableStack<T>Parent.NodeStack
  • 如果您存储对 的引用Parent TreeNode，则很容易创建一个循环循环，该循环会导致诸如查找根节点之类的操作永远不会终止，并且您将获得堆栈溢出或无限循环。ImmutableStack<T>另一方面，An可以通过Pop-ing 升序，保证它会终止。
    • 使用集合 ( ImmutableStack<T>) 的事实意味着您可以通过简单地确保parent TreeNode在构造TreeNode.

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

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

于 2017-07-05T22:30:01.540 回答