Использование неизменяемого стека

Question

Я видел post, объявив о выпуске стабильной версии пакета NuGet Microsoft.Bcl.Immutable.

Мне интересно: что будет использоваться для неизменяемого стека? Я не могу найти пример или сценарий, где это было бы полезно. Мое понимание моего неизменности. Если бы вы могли пролить свет на то, почему эта вещь может быть полезна, желательно с конкретным примером, это было бы хорошо.

Answer 1

Идея этой библиотеки коллекций заключается в предоставлении коллекций, которые при изменении производят новые версии той же коллекции, где все старые версии коллекций остаются в силе.

Это похоже на работу системы управления версиями: вы можете изменять код и фиксировать изменения на сервере, создавая новую версию исходного дерева. Тем временем вы все равно можете проверить любую предыдущую ревизию.

Для неизменных коллекций вы сохраняете доступ к старой версии (по сути, неизменяемый снимок), сохраняя указатель на коллекцию, которая не изменится.

Вы можете утверждать, что этот сценарий менее полезен для стека, потому что вы, вероятно, используете стек для добавления и получения каждого элемента ровно один раз, а также сохранения порядка. Обычно использование стека очень привязано к коду, запущенному на одном потоке выполнения.

Но теперь, когда я набираю текст, я могу думать о конкретном случае использования, если у вас есть ленивый парсер, который должен отслеживать состояние в стеке. Затем вы можете сохранить указатель на неизменяемый стек в состоянии, которое было во время начального разбора, без копирования и получить его при анализе отложенной работы.

Answer 2

Представьте сценарий, в соответствии с которым запросы поступают в один конвейер и хранятся в стеке, поскольку последний запрос должен рассматриваться как приоритет. Затем у меня есть набор пользователей с потоковым запросом, каждый из которых имеет дело с определенным типом запроса. Основной код маршаллинга создает стек, а затем, когда все потребители готовы, передает этот стек потребителям и запускает новый стек.

Если стек был изменен, каждый потребитель будет работать параллельно и будет делиться тем же стеклом, который может измениться на любом этапе из-за других потребителей. Блокировка потребовалась бы для управления выталкиванием элементов из стека, чтобы они все оставались в синхронизации. Если потребителю требуется много времени для завершения действия, которое стек заблокирован, все остальные удерживаются.

Имея неизменяемый стек, каждый потребитель может делать то, что он хочет, в стек, не заботясь о других потребителях. Попадание элемента из стека приводит к новому, и оригинал не изменяется. Таким образом, блокировка не требуется, и каждая нить может работать без заботы о других.

Answer 3

Я люблю неизменные коллекции, но они часто чувствуют себя как решение, нуждающееся в решении проблемы. Они могут быть unexpectedly slow из-за how they are implemented: они очень стараются эффективно использовать память за счет того, что петли и индексы намного сложнее алгоритмически сложны. Насколько изощренной памятью, это может быть трудно оправдать эту стоимость. В Интернете есть информация о успешном использовании неизменных коллекций (кроме 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); 
    } 
} 

По разным причинам, я предпочитать Занесение ImmutableStack<T> из TreeNode экземпляров, которые я могу траверс корень, а не просто ссылки к экземпляру Parent.

• ImmutableStack<T> Реализация в основном связанный список. Каждый экземпляр ImmutableStack<T> действительно является узлом в связанном списке. Вот почему собственность ParentStack всего Pop - NodeStack. ParentStack вернет тот же экземпляр ImmutableStack<T>, что и Parent.NodeStack.
• Если вы храните ссылку на 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> для отслеживания прогресса, и поэтому, когда шаг будет завершен, он может передать работу на родительский шаг. Его неизменная природа особенно полезна, когда вы пытаетесь параллельно работать.