È possibile rappresentare la mutazione del grafico di un oggetto in modo efficiente con stati immutabili?

Question

È possibile rappresentare la mutazione del grafico di un oggetto in modo efficiente con stati immutabili?

#1 da (7 voti)
#2 da (3 voti)

8

Sto praticando l'uso di oggetti immutabili in C ++. Il mio obiettivo personale è rappresentare un oggetto grafico generico (in heap) con una sequenza di grafici immutabili.

Costruire il grafico multi-versione non è molto difficile. Il problema è la prestazione. Il controllo delle versioni a forza bruta richiede una copia completa del grafico e questo non era accettabile.

Ho provato a condividere nodi invariati. Ma in questo caso, ho avuto un nuovo problema; Riferimenti. Il riferimento ad altri oggetti deve essere aggiornato nel grafico intero. Questo richiede di visitare tutti i nodi ogni volta che ricavo una nuova versione del grafico. E questo muta i nodi con riferimenti, quindi dovrebbero anche essere derivati (copiando). Le prestazioni non saranno migliori rispetto alla copia a forza bruta.

Per quanto posso immaginare, non esiste un modo veramente efficace per rappresentare la mutazione del grafo degli oggetti con stati immutabili. Quindi ti sto chiedendo un'idea su questo.

È possibile rappresentare la mutazione del grafico dell'oggetto in modo efficiente con lo stato immutabile?

immutability graph

posta Eonil 12.08.2013 - 03:23

fonte

2 risposte

Leggi altre domande sui tag immutability graph

Cosa dovrebbe essere fatto con i nomi delle classi che hanno conflitti con i nomi delle strutture (comuni) Posso scrivere un'applicazione multipiattaforma (Mac e Windows) usando C #? [chiuso]

score 7 · Answer 1

Quello che stai cercando è chiamato una struttura dati persistente . La risorsa canonica per strutture dati persistenti è il libro Strutture dati puramente funzionali di Chris Okasaki . Le strutture di dati persistenti hanno raccolto interesse negli ultimi tempi a causa della loro popolarità in Clojure e Scala.

Tuttavia, per qualche strana ragione, i grafici persistenti sembrano essere per lo più ignorati. Abbiamo liste, dozzine di diversi tipi di alberi, matrici, code di priorità, mappe, ma nessun grafico.

Ho trovato solo un documento: Grafici completamente persistenti: quale scegliere?

score 3 · Answer 2

Se non si considerano le connessioni tra gli oggetti come parte della risorsa con versione (e si potrebbe - nel qual caso probabilmente non è di grande aiuto), si potrebbe considerare di suddividere gli oggetti in una parte che rappresenta la parte di connettività dell'oggetto e una parte che rappresenta lo stato immutabile.

Quindi potresti avere ciascuno degli oggetti secondari di connettività contenenti un vettore degli stati con versione. In questo modo è possibile operare con un numero di versione del grafico per accedere allo stato immutabile appropriato.

Per evitare di dover attraversare l'intero grafico ogni volta che vi è un aggiornamento a un nodo specifico, è possibile farlo in modo che se un nodo accede a un numero di versione che è maggiore del numero di versione corrente del nodo, l'attuale la versione è usata Se il nodo viene quindi aggiornato, si inseriscono tutte le versioni intermedie con la versione precedente, consentendo così di eseguire aggiornamenti lazy sul grafico degli oggetti.

Se la connettività tra gli oggetti fa parte dello stato della versione, il precedente non funziona. Ma forse puoi estenderlo come segue:

Per ogni oggetto nel grafico, crea un "oggetto maniglia". L'oggetto handle contiene l'elenco degli stati immutabili con versione. Anziché memorizzare riferimenti a oggetti in uno qualsiasi degli oggetti del grafico, si memorizzerebbe un riferimento all'oggetto handle. Quindi ogni riferimento agli oggetti verrebbe de-referenziato attraverso l'handle usando l'handle e il numero di versione della vista del grafico dell'oggetto che era in fase di elaborazione. Ciò restituirebbe lo stato immutabile corretto per l'oggetto. Gli stati immutabili utilizzano le maniglie per riferirsi ad altri oggetti nel grafico, in modo da ottenere sempre la data coerente per la versione del grafico che si desidera elaborare.

La stessa logica descritta sopra si applica all'aggiornamento delle versioni all'interno degli handle, che consente aggiornamenti pigri e localizzati.