Uso di stack immutabile

Question

Ho visto il post annunciando il rilascio di una versione stabile del pacchetto Microsoft.Bcl.Immutable NuGet oggi.

Mi chiedo: quale sarebbe l'utilizzo per uno stack immutabile? Non riesco a trovare un esempio o uno scenario in cui ciò sarebbe utile. Potrebbe essere la mia comprensione dell'immutabilità. Se potessi far luce sul perché questa cosa potrebbe essere utile, preferibilmente con un esempio concreto, sarebbe bello.

Answer 1

L'idea alla base di questa libreria di collezioni è di fornire collezioni che, una volta cambiate, producono nuove versioni della stessa collezione, in cui tutte le vecchie versioni delle collezioni sono ancora valide.

È simile a come funziona il sistema di controllo della versione: è possibile modificare il codice e trasferire le modifiche al server, producendo una nuova versione dell'albero di origine. Nel frattempo puoi ancora eseguire il checkout di qualsiasi revisione precedente.

Per le raccolte non modificabili, si continua ad accedere a una versione precedente (essenzialmente un'istantanea immutabile) mantenendo un puntatore alla raccolta che non cambierà.

Si potrebbe sostenere che questo scenario è meno utile per uno stack perché probabilmente si utilizza uno stack per aggiungere e recuperare ogni elemento esattamente una volta, e anche preservando l'ordine. Di solito l'uso di uno stack è molto legato al codice in esecuzione su un singolo thread di esecuzione.

Ma ora che sto digitando, posso pensare a un caso d'uso specifico se hai un parser pigro che deve tracciare qualche stato in una pila. È quindi possibile salvare un puntatore nello stack immutabile nello stato in cui era durante l'analisi iniziale, senza copiarlo, e recuperarlo quando si analizza il lavoro posticipato.

Answer 2

Immaginate uno scenario in cui le richieste arrivano su una singola pipeline e sono archiviate in una pila poiché l'ultima richiesta deve essere considerata prioritaria. Poi ho una serie di consumatori di richieste filettate, ognuna delle quali tratta un tipo specifico di richiesta. Il codice di marshalling principale crea lo stack, quindi quando tutti i consumatori sono pronti, passa lo stack ai consumatori e inizia un nuovo stack.

Se lo stack fosse mutabile, ciascun utente sarebbe in esecuzione in parallelo e condividerebbe lo stesso stack che potrebbe cambiare in qualsiasi momento a causa degli altri utenti. Il blocco sarebbe necessario per controllare gli oggetti popping dallo stack per assicurarsi che fossero tutti sincronizzati. Se un utente impiega molto tempo per completare un'azione bloccata dallo stack, tutti gli altri vengono bloccati.

Con uno stack immutabile, ogni consumatore è libero di fare ciò che vuole nello stack senza preoccuparsi degli altri consumatori. L'inserimento di un elemento fuori dallo stack ne provoca uno nuovo e l'originale rimane invariato. Quindi non è richiesto alcun blocco e ogni thread è libero di funzionare senza la cura degli altri.

Answer 3

Amo le collezioni immutabili ma spesso si sentono come una soluzione che necessita di un problema. Possono essere unexpectedly slow a causa di how they are implemented: tentano molto duramente di utilizzare la memoria in modo efficiente al costo di rendere i loop e gli indicizzatori foreach molto più complessi dal punto di vista dell'algoritmo. Con quanta memoria è, può essere difficile giustificare questo costo. C'è una scarsità di informazioni che si possono trovare sul web in merito a usi di successo di collezioni immutabili (diverse da ImmutableArray<T>). Nel tentativo di rettificare ciò, ho pensato di aggiungere una risposta a questa domanda di più di 3 anni su un caso in cui ho trovato ImmutableStack<T> veramente utile.

considerare questo albero-come la struttura molto semplice:

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

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

ho creato le classi che seguono questo modello di base molte, molte volte, e in pratica, è sempre lavorato per me. Più di recente, ho iniziato a fare qualcosa di simile:

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

Per una serie di ragioni, sono venuto a preferire la memorizzazione di un ImmutableStack<T> di TreeNode istanze che posso attraversare alla radice, piuttosto che semplicemente un riferimento all'istanza Parent.

• L'implementazione di ImmutableStack<T>ImmutableStack<T> è fondamentalmente un elenco collegato. Ogni istanza di ImmutableStack<T> è in realtà un nodo in un elenco collegato. Ecco perché la proprietà ParentStack solo Pop è la NodeStack. ParentStack restituirà la stessa istanza di ImmutableStack<T> come Parent.NodeStack.
• Se si memorizza un riferimento allo ParentTreeNode, sarebbe facile creare un ciclo circolare che causerebbe operazioni come trovare il nodo radice non terminare mai e si otterrebbe un overflow dello stack o un ciclo infinito. Un ImmutableStack<T>, d'altra parte, può essere aumentato da Pop -ing, garantendo che terminerà.
  • Il fatto che si utilizza una raccolta (ImmutableStack<T>) significa che è possibile evitare i loop circolari accada, in primo luogo, semplicemente facendo attenzione che la parentTreeNode non si verifica due volte durante la costruzione della TreeNode.

Questo è solo per cominciare. Penso che lo ImmutableStack<T> renda le operazioni sugli alberi più semplici e sicure. Puoi (tranquillamente) usare LINQ su di esso. Vuoi sapere se uno TreeNode è un discendente di un altro? Si potrebbe semplicemente fare ParentStack.Any(node => node == otherNode)

Più in generale, la classe ImmutableStack<T> è per ogni caso in cui si desidera ricevere un Stack<T> che si può garantire non sarà mai modificato, o avete bisogno di un modo semplice per ottenere un ' "istantanea" di una Stack<T> ma non voglio creare creare un mucchio di copie di quella pila. Se si dispone di una serie di passaggi nidificati, è possibile utilizzare uno ImmutableStack<T> per tenere traccia dell'avanzamento e, pertanto, quando un passaggio è completato, può trasferire il lavoro al relativo passo principale. La sua natura immutabile è particolarmente utile quando stai cercando di lavorare in parallelo.