Użycie niezmiennego stosu

Question

Widziałem już post ogłaszając wydanie stabilnej wersji pakietu NuGet Microsoft.Bcl.Immutable dzisiaj.

Zastanawiam się: jakie byłoby użycie niezmiennego stosu? Nie mogę znaleźć przykładu ani scenariusza, w którym byłoby to przydatne. Być może rozumiem niezmienność. Gdybyś mógł rzucić nieco światła na to, dlaczego ta rzecz może być użyteczna, najlepiej konkretnym przykładem, byłoby to miłe.

Answer 1

Ideą tej biblioteki zbiorów jest zapewnienie kolekcji, które po zmianie tworzą nowe wersje tej samej kolekcji, w której wszystkie stare wersje kolekcji są nadal aktualne.

Jest podobny do działania systemu kontroli wersji: Możesz zmienić kod i zatwierdzić zmiany na serwerze, tworząc nową wersję drzewa źródłowego. W międzyczasie nadal możesz sprawdzić poprzednią wersję.

W przypadku niezmiennych kolekcji zachowujemy dostęp do starej wersji (w zasadzie niezmiennej migawki), zachowując wskaźnik do kolekcji, która nie ulegnie zmianie.

Można argumentować, że ten scenariusz jest mniej użyteczny dla stosu, ponieważ prawdopodobnie używasz stosu, aby dodać i pobrać każdy przedmiot dokładnie jeden raz, a także zachować zamówienie. Zwykle użycie stosu jest bardzo powiązane z kodem działającym na pojedynczym wątku wykonania.

Ale teraz, kiedy piszę, mogę wymyślić konkretny przypadek użycia, jeśli masz leniwy analizator składni, który musi śledzić stan w stosie. Następnie można zapisać wskaźnik na niezmiennym stosie w stanie, w jakim znajdował się podczas początkowego analizowania, bez kopiowania, i pobrać go podczas analizowania odroczonej pracy.

Answer 2

Wyobraź sobie scenariusz, w którym żądania przychodzą na jednym potoku i są przechowywane w stosie, ponieważ ostatnie żądanie należy traktować jako priorytet. Następnie mam zestaw wątkowych klientów żądań, z których każdy dotyczy konkretnego typu żądania. Główny kod rozgałęziający tworzy stos, a gdy wszyscy konsumenci są gotowi, przekazuje stos do konsumentów i rozpoczyna nowy stos.

Jeśli stos był zmienny, każdy konsument działałby równolegle i dzieliłby ten sam stos, który mógłby ulec zmianie na dowolnym etapie ze względu na innych użytkowników. Blokowanie będzie wymagane w celu kontrolowania zdejmowania przedmiotów ze stosu, aby zapewnić, że wszystkie pozostaną zsynchronizowane. Jeśli konsument wykonuje długi czas, aby zakończyć akcję, która jest zablokowana, wszystkie pozostałe są wstrzymywane.

Dzięki niezmiennemu stosowi, każdy konsument może swobodnie robić to, co chce, bez zwracania uwagi na innych konsumentów. Wyrzucenie przedmiotu ze stosu powoduje, że nowy i oryginalny pozostaje niezmieniony. Więc nie jest wymagane żadne blokowanie i każda nić może być uruchamiana bez opieki dla innych.

Answer 3

Uwielbiam niezmienne kolekcje, ale często czuję się jak rozwiązanie wymagające problemu. Mogą być unexpectedly slow ze względu na how they are implemented: bardzo starają się efektywnie wykorzystywać pamięć kosztem tworzenia pętli i indeksatorów o wiele bardziej złożonych algorytmicznie. Przy tak dużej ilości pamięci trudno jest uzasadnić ten koszt. W Internecie brakuje informacji o udanych zastosowaniach niezmiennych kolekcji (innych niż ImmutableArray<T>). Próbując to naprawić, pomyślałem, że dodam odpowiedź na to ponad 3-letnie pytanie dotyczące przypadku, w którym stwierdziłem, że ImmutableStack<T> jest naprawdę użyteczny.

Rozważmy to bardzo podstawowe drzewiastą strukturę:

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

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

I utworzeniu klasy, które obserwować tą podstawowy wzór wiele, wiele razy, aw praktyce to zawsze pracował dla mnie. Niedawno zacząłem robić coś takiego:

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

Z różnych powodów, Doszedłem do preferują Zapisywanie ImmutableStack<T> z TreeNode instancji, że mogę Ruch do korzeni, a nie tylko odniesienie do instancji Parent. Wykonanie

• ImmutableStack<T> jest w zasadzie połączoną listą. Każde wystąpienie ImmutableStack<T> jest tak naprawdę węzłem na połączonej liście. Dlatego właśnie właściwość ParentStack jest tylko Pop 's NodeStack. ParentStack spowoduje wyświetlenie tego samego wystąpienia z ImmutableStack<T> jako Parent.NodeStack.
• Jeśli przechowujesz odniesienie do ParentTreeNode, łatwo byłoby utworzyć okrągłą pętlę, która spowodowałaby takie operacje, jak znalezienie węzła głównego, który nigdy się nie zakończy, a otrzymasz przepełnienie stosu lub nieskończoną pętlę. Z drugiej strony, ImmutableStack<T> może zostać wzniesiony przez Pop -ing, gwarantując, że się zakończy.
  • Fakt, że używasz Collection (ImmutableStack<T>) oznacza, że ​​można zapobiec okrężne pętle z dzieje się w pierwszej kolejności, po prostu upewniając się parentTreeNode nie występuje dwukrotnie przy konstruowaniu TreeNode.

Na początek. Myślę, że ImmutableStack<T> sprawia, że ​​operacje na drzewach są prostsze i bezpieczniejsze. Możesz (bezpiecznie) użyć LINQ na nim. Chcesz wiedzieć, czy jeden TreeNode jest potomkiem innego? Można po prostu zrobić ParentStack.Any(node => node == otherNode)

Bardziej ogólnie, klasa ImmutableStack<T> jest dla każdego przypadku, w którym chcieliby Państwo Stack<T> że można zagwarantować, nigdy nie zostaną zmodyfikowane, czy trzeba w prosty sposób uzyskać „migawkę” na Stack<T> ale nie chcę tworzyć, stwórz masę kopii tego stosu. Jeśli masz szereg zagnieżdżonych kroków, możesz użyć ImmutableStack<T>, aby śledzić postępy, a kiedy krok zostanie ukończony, może przekazać pracę do kroku nadrzędnego. Jego niezmienny charakter jest szczególnie przydatny, gdy próbujesz pracować równolegle.