Come vengono modificati i Set Immutabili

Per quanto posso dire, gli insiemi funzionali sono generalmente implementati come alberi, quindi la condivisione dei nodi tra versioni concorrenti ha senso. Alcuni linguaggi funzionali, in particolare F # e Clojure, aprono il loro codice su github, puoi guardare lì per dettagli concreti. F # usa alberi.

Qualche tempo fa, ho confrontato le prestazioni di F # immutable Set (Microsoft.FSharp.Collections) vs mutable .NET HashSet (System.Collections.Generic). Non ho i risultati disponibili da condividere ora, ma per quanto mi ricordo i tempi di ricerca / unione / intersezione erano simili per entrambi e quando si aggiungevano grandi numeri di voci il set immutabile veniva eseguito più lentamente da un fattore costante basso (qualcosa circa 3 o 4) .

Oltre al libro, è disponibile anche la tesi di Okasaki , che è stata la base per il libro - lo si intravede e sembra piuttosto difficile (beh, come dovrebbe essere una tesi vera e propria), anche se potresti trovarlo utile.

Condivisione - fare riferimento allo stesso blocco dati da diversi oggetti, in modo che diverse strutture dati finiscano con parte della loro memoria in comune - è uno dei punti principali delle strutture di dati immutabili. Strutture di dati immutabili condividono automaticamente i pezzi comuni da cui sono costruite. (Le strutture dati costruite in modo indipendente non condividono nulla: ci sono tecniche per questo, in particolare hash consing .)

In molti modi, la struttura fondamentale dei dati mutabili è l'array, e l'operazione fondamentale di mutazione è quella di modificare un elemento di un array. Una struttura dati mutabile è costituita da matrici che contengono puntatori a (o in) reciprocamente.

In una struttura di dati immutabile, devi decidere tutti gli elementi di un blocco di dati quando crei quel blocco. Questo tende a guidare verso piccoli blocchi di dati. Quando è necessario archiviare una grande quantità di dati, è necessario applicare una strategia di divisione e conquista: a meno che i dati non siano abbastanza piccoli da essere archiviati in un'unica soluzione, dividerli in più parti e memorizzare una serie di puntatori a quei pezzi - che possono essere di nuovo puntatori a pezzi più piccoli, e così via ricorsivamente. Ciò rende la struttura dei dati risultante una struttura . L'albero è la struttura dei dati immutabili di base.

Qualsiasi struttura di dati mutabile può essere rappresentata come una struttura di dati immutabile con una perdita di tempo logaritmica e un aumento lineare della memoria. Cioè, se si ha un algoritmo che opera nel tempo N e utilizza unità di memoria M, è possibile convertirlo per utilizzare solo strutture di dati immutabili con O (M) più memoria utilizzata e operante nel tempo O (N * log (N) ). Puoi farlo codificando ogni array come un albero binario dove le foglie sono gli elementi dell'albero. Per accedere o modificare un elemento costa O (1) tempo in un array e O (log (N)) in un albero con lo stesso numero di foglie. Questo è ovviamente un massimo: spesso c'è un approccio meno generale ma più efficiente.

Ciò significa che c'è un limite al build-up causato dal passaggio a strutture di dati immutabili. Non sperimenterai mai nulla di simile a un'esplosione quadratica.

In pratica, ogni struttura di dati immutabile che troverai in qualsiasi libreria a metà strada sarà scritta attorno a tali linee di divisione e conquista, spesso con trucchi copiosi per compensare l'accumulo logaritmico. La condivisione è gratuita: la maggior parte delle volte ci vorrebbe del lavoro per evitarlo. Costruire strutture dati a breve termine che derivano da un'altra struttura dati, che differiscono solo in alcuni valori, è qualcosa che i programmatori fanno sempre; puoi essere certo che ciò comporterà la condivisione sotto il cofano. (Puoi testare controllando l'uguaglianza fisica delle parti non modificate della struttura dati, tenendo traccia del consumo di memoria del tuo programma, o osservando il programma che si sta eseguendo in un debugger).

Costruire una nuova struttura dati che differisce solo in alcuni punti da una vecchia e scartare quella vecchia è anche qualcosa che i programmatori fanno spesso, e spesso ci si può aspettare di trovare implementazioni di strutture di dati immutabili ottimizzate per quel caso. Guarda le indicazioni di complessità ammortizzata .

Il libro di Chris Okasaki Strutture dati puramente funzionali è un buon riferimento se è necessario scrivere la propria struttura di dati immutabile. Aspettatevi che gli implementatori di librerie di strutture dati immutabili abbiano letto questo libro.

Quando si tratta di insiemi e mappe, molto dipende dalla struttura specifica dei dati. Gli alberi sono abbastanza comuni per i contenitori associativi, compresi insiemi e mappe, quindi mi occuperò solo di questi.

Per gli alberi binari non bilanciati, un'operazione di inserimento funziona in due fasi: la parte in alto per trovare il punto di inserimento e la parte dal basso verso l'alto per modificare (o creare) il nuovo albero.

Il punto qui è che per ogni nodo, solo uno dei due sottoalberi contiene il punto di inserimento, e solo quella sola sottostruttura deve essere duplicata per un inserto dell'albero puramente funzionale. Quindi gli unici nuovi nodi necessari sono in una catena dal punto di inserimento indietro fino alla radice.

Questo significa che supponendo che l'albero sia (accidentalmente) bilanciato, hai O (log n) nuovi nodi per un singolo inserto - il numero di nuovi nodi dipende dalla profondità dell'albero, non dalla dimensione totale.

Un'ipotesi chiave qui è che i nodi memorizzano solo i puntatori ai propri figli. Nelle lingue imperative, è comune che i nodi memorizzino i puntatori ai loro genitori. Ciò significa che ci sono riferimenti ciclici, quindi la struttura dei dati deve essere copiata nel suo complesso. Ci sono problemi simili con alberi binari a thread . La regola generale è che quando si crea un nuovo stato, ogni componente strongmente connesso deve essere copiato nel suo complesso - in pratica, questi le strutture dati sono raramente utilizzate nella programmazione funzionale.

Ovviamente i link genitore possono essere memorizzati al di fuori della struttura dei dati dell'albero, e il modo funzionale per gestirli è usare un cerniera . Un problema (a volte vantaggioso, a volte lo svantaggio) è che le cerniere, come i collegamenti principali memorizzati esternamente, fanno riferimento allo stato particolare in cui sono state create per fare riferimento, non a uno stato più recente.

Con schemi ad albero binario bilanciati come alberi AVL e alberi rosso-nero, ci saranno cambiamenti più complessi dovuti al ribilanciamento, ma in genere si ottengono generalmente gli stessi nodi O (log n) copiati per singolo inserto - a meno che tu non abbia collegamenti principali ancora.

Alberi digitali o tentativi utilizzano una struttura dati ad albero, ma basano quella sul binario (o digitale, almeno) rappresentazione delle chiavi, non dell'ordine. Ad esempio, utilizzando le cifre di base 10, è possibile trovare l'elemento per la chiave 123 iniziando dal nodo radice, seguendo il collegamento figlio 1, quindi il collegamento figlio 2, quindi il collegamento figlio 3. La profondità di questi alberi è logaritmica nella dimensione massima possibile perché se si dispone di un numero di n cifre e di k cifre distinte, è possibile formare stringhe di cifre in modo che la dimensione massima possibile sia k ^ n. Ad esempio, con tre cifre decimali, puoi avere solo 1000 chiavi diverse, quindi la dimensione massima è 1000 - 3 è il logaritmo di base 10 di 1000.

La trama è simile agli alberi binari, ad eccezione del fatto che tendi ad avere costanti migliori (l'albero si dirama in più modi su ciascun nodo) e puoi spesso rivendicare O (1) perché le chiavi hanno tutti un numero fisso di bit. Questa struttura, con hash per le chiavi, può anche essere usata per dare una sorta di tabella hash - con vantaggi e svantaggi rispetto alle solite tabelle hash basate su array dalla programmazione imperativa.

C'è una struttura intermedia chiamata albero ternario - fondamentalmente un albero di alberi binari, quindi fai una ricerca binaria per il primo carattere della stringa, poi il prossimo e così via. Ancora una volta, è ancora un albero e, a patto che non ci siano indicatori genitore o altri riferimenti ciclici, ogni inserto deve solo copiare i nodi O (log n).