Quali sono gli algoritmi efficienti per dizionari / set immutabili? Per efficienza intendo che hanno un tempo migliore e comparabile e / o prestazioni di memoria rispetto alle loro versioni mutevoli. Non intendo necessariamente questo nel contesto della programmazione funzionale, dove ho visto l'immutabilità equiparata a strutture di dati persistenti.
Un esempio concreto è Guava , dove ho visto risparmi di memoria se usato con insiemi che non hanno bisogno da modificare.
Ci sono strutture dati che sono facili da leggere e (relativamente) lente da costruire, quindi tendono ad essere più adatte a strutture di dati immutabili.
Ad esempio, per un set mutabile, normalmente utilizzi una sorta di struttura ad albero (ad es. albero rosso-nero o albero AVL). Tale albero ha una ragionevole complessità sia per le ricerche che per le modifiche (tipicamente O (log N) per entrambi). Un albero, tuttavia, ha due (o tre) puntatori per elemento di dati. Ciò riduce la densità dei dati, quindi l'utilizzo della cache è relativamente scarso.
Se il tuo dizionario è immutabile, puoi utilizzare una matrice ordinata. Questo elimina i puntatori, aumentando la densità dei dati, in modo da ottenere (almeno in parte) un migliore utilizzo della cache.
In un caso tipico, l'uso di un array ordinato ti consente di andare oltre. Un albero supporta la ricerca binaria per trovare l'elemento di interesse. Se le tue chiavi hanno una distribuzione ragionevolmente prevedibile (il più delle volte approssimativamente uniforme, ma anche altre distribuzioni possono essere gestite), puoi utilizzare una ricerca interpolata.
Ad esempio, considera la ricerca di una parola in un dizionario (fisico). Se stai cercando "taxi", sai di voler guardare da qualche parte vicino all'inizio; se stai cercando "sì", sai che vuoi guardare vicino alla fine.
Una ricerca interpolata equivale approssimativamente - usa il tasto per calcolare un'approssimazione decente della posizione iniziale per la ricerca, piuttosto che iniziare sempre al centro (e lo stesso nelle ricerche successive).
Supponendo che la distribuzione delle chiavi sia almeno in qualche modo prevedibile, questo in genere migliorerà la complessità della ricerca fino a circa O (log log N), che viene spesso definita "pseudo-costante", perché è praticamente costante per quasi tutti dimensione della raccolta riscontrata nella realtà.
Ad esempio, assumiamo logaritmi comuni (base 10). Ogni dimensione da 10 0 a 10 9 ha log di log N = 1. Ogni dimensione da 10 10 a 10 99 ha log di registro N = 2.
Per qualsiasi scopo pratico, N = 2 è già ben oltre il massimo che possiamo mai aspettarci di affrontare - per arrivare a N = 3, avremmo bisogno di una collezione di almeno 10 100 articoli. Per metterlo in prospettiva, ci sono circa 10 57 atomi nel sistema solare, quindi se potessi immagazzinare ogni oggetto usando solo un singolo atomo, avresti ancora bisogno degli atomi da circa 10 43 sistemi solari per memorizzare una collezione di 10 100 elementi.
By efficient I mean they either have better or comparable time and/or memory performance compared to their mutable versions.
Strettamente parlando, non credo che possa esistere, perché puoi sempre mostrarmi una struttura dati immutabile e posso trovare il modo di rendere qualcosa di più economico se potesse essere reso mutevole. Ad esempio, potrei essere in grado di eliminare il requisito di garbage collection o reference-counting se fosse mutabile.
Esistono strutture dati che sono adatte a diventare immutabili anche se i costi sono relativamente economici. La maggior parte dei non banali sono in genere almeno in parte contigue. Ciò consente di banalizzare i costi di ref-counting o GC se i nodi vengono srotolati e memorizzare più elementi ciascuno, non un elemento per nodo.
Spesso c'è anche un atto di bilanciamento tra copiatura superficiale di più puntatori rispetto alla copia profonda di pochi elementi non univoci, perché qualsiasi struttura dati può essere resa immutabile se si copia l'intera cosa terribile ogni volta che si desidera modificare qualcosa, ma ciò potrebbe essere esplosivi nella memoria e requisiti di elaborazione. Il rovescio della medaglia, se riferimento superficiale ogni singolo elemento, che potrebbe essere esplosivo in memoria e requisiti di elaborazione con tutti i puntatori extra, tutta l'indiretta e la potenziale frammentazione della memoria, il costo di ref-counting o GC devono essere pagati per ogni singolo elemento, ecc.
Spesso penso che le strutture di dati immutabili più efficienti per insiemi e dizionari siano parzialmente contigue, come una tabella hash che utilizza l'indirizzamento aperto, ma invece di usare un array gigante per l'intera tabella, usa i blocchi srotolati che memorizzano, diciamo, 64 tasti ciascuno. Un altro esempio potrebbe essere un albero n-ary che memorizza molte chiavi in un nodo.
Ovviamente una tabella hash che utilizza il concatenamento separato è davvero semplice da rendere immutabile, dal momento che rendere le liste LIFO single-linked immutabili richiede semplicemente la memorizzazione di un diverso puntatore testa per lista immutabile. Tuttavia, è semplice ma non molto economico poiché ciò implica, ancora una volta, il conteggio dei riferimenti o il GC pagato a livello di singolo elemento.
È anche probabile che avrai bisogno di qualcosa come un "costruttore" o "transitorio" per esprimere ciò che vuoi fare con esso, dal momento che non vuoi pagare il costo di generare una nuova istanza immutabile ogni volta basta inserire o rimuovere una chiave.
A concrete example is Guava, where I have seen memory savings when used with sets that don't need to be modified.
Qui forse non si tratta tanto di immutabilità, ma solo di una struttura dati in grado di scartare il presupposto che gli elementi verranno semplicemente inseriti e conosciuti in anticipo e non avendo a che fare con la rimozione dinamica e l'inserimento di elementi dopo la sua costruzione .
In questo caso, ad esempio, è possibile utilizzare un allocatore di memoria sequenziale come ottimizzazione perché non è necessario gestire la memoria di liberazione per i singoli elementi poiché gli elementi non verranno mai rimossi singolarmente dalla struttura dei dati. Tutto ciò che devi essere in grado di fare è eliminare tutta la memoria per tutti gli elementi quando la struttura dei dati viene distrutta.
Anche se gli elementi sono tutti noti in anticipo, potresti essere in grado di evitare di dover effettuare riallocazioni per espandere la dimensione della struttura. Puoi renderlo perfettamente proporzionato poiché conosci tutti gli elementi che inserirai in anticipo in modo da non dover riservare memoria aggiuntiva per gli inserimenti futuri.
Le strutture dati che devono soddisfare solo questi tipi di requisiti "statici" e non "dinamici" offrono anche molto spazio per la post-elaborazione dopo la loro costruzione. Ad esempio, un albero binario potrebbe essere post-elaborato per riallocare i suoi nodi in un modello di accesso compatibile con la cache. Potete permettervelo con un tipo statico di struttura dati che non si occupa di inserimenti e rimozioni dinamiche poiché c'è una fase di costruzione chiara che lascia spazio per la post-elaborazione, dopodiché non dovrete più gestire le modifiche alla struttura dati.
Es: metodo "Cancella" mutevole
Qualunque struttura di dati che abbia meno requisiti funzionali da trattare avrà generalmente più spazio per l'ottimizzazione. Ma qui non si tratta di strutture di dati immutabili, quanto di strutture di dati che possono essere solo costruite in anticipo e non devono occuparsi di inserimenti e rimozioni dinamici. Tali strutture di dati potrebbero ancora essere rese mutevoli e rimanere a buon mercato. Ad esempio, una tale struttura dati potrebbe ancora fornire un metodo mutabile clear per cancellare l'intero contenuto dell'insieme / dizionario, e fornire un tale metodo mutabile non richiederebbe di perdere quelle potenziali ottimizzazioni descritte sopra. Quindi non c'è alcun caso per quanto vedo dove l'immutabilità rende tutto meno costoso, dal momento che l'immutabilità impone più requisiti funzionali su una struttura dati, per così dire, non meno.
Leggi altre domande sui tag data-structures algorithms