Ogni volta che risolvo un problema con sottoproblemi sovrapposti, raggiungo la memoizzazione perché è così semplice da implementare. Tuttavia, memoizing in un linguaggio immutabile che non ha il supporto incorporato per la memoizzazione senza copiare la memoria su ogni inserto non è così efficiente.
Quali tecniche sono comuni nei linguaggi immutabili per risolvere il problema dei sottoproblemi sovrapposti nella programmazione dinamica?
Usi la memoizzazione. Inserimenti e ricerche su una tabella di hash persistente persistente sono effettivamente costante . Mentre tecnicamente quel valore costante è un po 'più lungo di una struttura dati mutevole, in pratica di solito non ti interessa. Ecco un esempio tratto da una delle mie precedenti risposte in cui ho memorizzato sequenze sovrapposte di collatz per ottenere un risultato che è tornato praticamente istantaneamente nella mia REPL.
La maggior parte dei cosiddetti linguaggi immutabili fornisce una backdoor che ti consente di sfuggire all'immutabilità e utilizzare strutture dati mutevoli. Ad esempio, Haskell fornisce la monade ST e la capacità di memorizzare dati mutabili con la monade IO. Ha anche una funzione "unsafePerformIO" che puoi usare per eseguire operazioni IO in un contesto che non è dichiarato di utilizzare la monade IO. È possibile utilizzare questi elementi costitutivi di base per eseguire la memoizzazione (e in quanto tale un'implementazione dovrebbe essere visibilmente trasparente in modo referenziale, non è pericoloso farlo (nonostante l'avviso di poppa nel nome della funzione)).
Posso quindi vedere le possibili firme per una funzione di memoize:
mwmoizeST :: (a -> b) -> a -> ST s b
memoizeIO :: (a -> b) -> a -> IO b
memoizeUmsafeIO :: (a -> b) -> a -> b
Tutto potrebbe essere utile in diverse circostanze.
Altre lingue simili offrono simili escape hatch - hanno devono , poiché a volte una struttura mutevole è l'unico modo per ottenere prestazioni soddisfacenti.
Leggi altre domande sui tag dynamic-programming