Che tipo di struttura dati viene utilizzata per le mappe immutabili?

So come funzionano le normali mappe mutabili (usando le hashtables) e so come funzionano le liste immutabili (liste ricorsive collegate) e il loro vantaggio rispetto alle liste mutabili (l'aggiunta costante di tempo senza incasinare l'originale) ma come fare mappe immutabili (es.) lavoro?Che tipo di struttura dati viene utilizzata per le mappe immutabili?

Conosco il vantaggio di non incasinare con la mappa originale quando si generano nuove mappe, ma come funziona la struttura dati sottostante e quale tipo di caratteristiche delle prestazioni hanno, ad esempio rispetto alle tabelle hash mutabili? C'è qualche struttura dati standard che le persone usano per implementarle, che potrei andare a cercare in CLRS/wikipedia?

fonte

2012-01-29 Li Haoyi

CLRS, e praticamente ogni altro libro di testo struttura dati/algoritmo sono * * fortemente sbilanciata verso mutevolezza e l'impurità. Chris Okasaki * ha letteralmente * scritto il libro su Funcastructure Datastructures, che è basato su e un'estensione del suo precedente lavoro di tesi. Altri lavori che dovresti guardare sono di Phil Bagwell e Rich Hickey. –

persistente Hash mappe sono realizzati tramite una struttura chiamata Hash trie. Era originally proposed by Phil Bagwell (che è un membro del gruppo Scala all'EPFL), ma in realtà implementato da Clojure prima. Ha colpito scala quando 2,8 è uscito nel 2010.

C'è un great talk on functional data structures da Dan Spiewak in cui la meccanica del trie hash sono spiegati molto lucidamente (insieme ad altre cose, come le code del banchiere)! Spiega anche molto bene la performance big-O asintotica.

Lo scorso ottobre Phil ha tenuto un altro discorso allo London scala Lift Off, questa volta su strutture di dati persistenti parallele.

mappe ordinati persistenti vengono implementati tramite un Red-Black tree

fonte

2012-01-29 16:22:21

In generale, le strutture dati persistenti si basano su * condivisione strutturale * (ad esempio liste di consenti persistenti condividono le loro code). In genere, si usano alberi per questo. Se capisci come funzionano le liste di controllo persistenti, sei a metà strada: dopo tutto, una lista è solo un albero degenerato con un solo ramo dappertutto. (Oppure, un albero è una generalizzazione di un elenco, in cui ogni cella può avere più di un successore.) –

Penso che l'informazione interessante sia come connettere tale comprensione con il modo in cui riguarda l'accesso basato su hash –

Potrebbe essere un albero (rosso-nero) o una mappa hash. Le loro caratteristiche di accesso dipendono dall'implementazione sottostante. Un albero è O (log n) per l'accesso in lettura; una mappa hash è O (1).

fonte

2012-01-29 16:13:31 duffymo

Che tipo di struttura dati viene utilizzata per le mappe immutabili?

risposta

Problemi correlati