I riferimenti alla stessa allocazione dei dati e la memoria

Question

Si prega di considerare il seguente modello di dati:

data Artist = Artist Text 
data Song = Song Artist Text 
data Catalogue = Catalogue (Set Artist) (Set Song) 

Si può vedere che i Artist s sono indicati da entrambe le Song s e il Catalogue. Il Catalogue contiene un elenco di tutti gli artisti di cui da Song s, quindi gli stessi valori di Artist ottenere di cui da due posti.

Supponiamo di generare il valore Catalogue utilizzando più applicazioni del seguente funzione:

insertSong :: Song -> Catalogue -> Catalogue 
insertSong song@(Song artist title) (Catalogue artists songs) = 
    Catalogue (Set.insert artist artists) (Set.insert song songs) 

E 'evidente che la Catalogue otterrebbe riempito da riferimenti agli stessi valori del Artist come il Song s riferiscono, risparmiando così la memoria non memorizzando le copie di quei valori.

Il problema è che quando cerco di ricreare il catalogo da dati serializzati dalla deserializzazione separatamente una serie di artisti e una serie di canzoni, l'applicazione occupa modo più memoria rispetto a quando ha generato lo stesso valore di Catalogue con insertSong. Ho il sospetto che essa è causata dalla relazione tra la perduto stessi Artist s di cui da Song s e la Catalogue, che è il motivo per cui ho copie di valori di Artist che occupano memoria aggiuntiva.

L'unica soluzione che vedo è deserializzare prima l'insieme di artisti e quindi deserializzare il set di canzoni sostituendo con forza i valori di Artist con quelli del primo set.

Quindi le mie domande sono:

1. Ho ragione di mio sospetto?
2. disposta la soluzione che vedo lavorare?
3. Ci sono modi migliori per risolvere questo problema?

Answer 1

ho accidentalmente inciampato su un progetto, che si avvicina il problema. Vedi RefSerialize.

Answer 2

1. Sembra plausibile.
2. Si dovrebbe funzionare se fatto a destra. In particolare, è necessario assicurarsi che tutto sia valutato con attenzione, per evitare di fare riferimento ai vecchi valori di Testo da thunk.
3. È possibile scegliere un formato di serializzazione più intelligente. Ad esempio, quando serializzi i brani, memorizza l'indice dell'artista nella lista artisti anziché il nome completo dell'artista. Quindi cercalo durante la deserializzazione.

Nota che la condivisione sarà persa anche se si fa alcun tipo di calcolo sulle tue corde (vale a dire anche se artist1 e artist2 sono gli stessi e condivisa, f artist1 e f artist2 probabilmente non sono). Se questo diventa un problema, puoi fare anche cambiamenti simili alle tue strutture dati.

Answer 3

Una soluzione semplice sembra mettere in cache i dati utilizzando una mappa un po 'degenerata:

{-# LANGUAGE DeriveDataTypeable, RankNTypes #-} 
import Control.Monad 
import Control.Monad.State 
import Data.Map (Map) 
import qualified Data.Map as M 

type Cache a = Map a a 

Possiamo quindi interrogare questa cache se esiste già una voce uguale a questo, e sostituirlo con la cache uno:

cached :: (Ord a) => a -> State (Cache a) a 
cached x = state $ \m -> 
    case M.lookup x m of 
     Just x'  -> (x', m) 
     Nothing  -> (x, M.insert x x m) 

In questo modo, se cariciamo diversi elementi uguali di tipo a, li trasformiamo in un singolo. Questo può essere fatto durante la deserializzazione o una volta alla fine.

---

Forse sarebbe possibile generalizzare ulteriormente e utilizzare SYB per mappare tutti i valori di un dato tipo in una struttura di dati attraverso una cache:

import Data.Data (Data) 
import Data.Generics.Aliases (mkM) 
import Data.Generics.Schemes (everywhereM) 
import Data.Typeable (Typeable) 

replaceFromCache 
    :: (Ord a, Typeable a, Data b) 
    => b -> State (Cache a) b 
replaceFromCache = everywhereM (mkM cached) 

Poi possiamo sostituire tutti gli artisti in qualche struttura di dati come

data Artist = Artist String 
    deriving (Eq, Ord, Typeable) 

cacheAllArtists :: (Data b) => b -> b 
cacheAllArtists b = evalState (replaceFromCache b) (M.empty :: Cache Artist) 

Oppure possiamo usare Proxy tipo phantom per creare una versione generale:

cacheAll :: (Ord a, Typeable a, Data b) 
     => Proxy a -> b -> b 
cacheAll p = flip evalState (emptyOf p) . replaceFromCache 
    where 
    emptyOf p = asTypeOf2 M.empty p 
    asTypeOf2 :: f a -> Proxy a -> f a 
    asTypeOf2 = const 

cacheAllArtists :: (Data b) => b -> b 
cacheAllArtists = cacheAll (Proxy :: Proxy Artist) 

(Disclaimer:. Non ho provato nessuna delle codice di cui sopra)