Quali tipi di funzioni sono candidati per la memoizzazione?

Question

Ho deciso su PostSharp (indistinguibile dalla magia) di leggere gli attributi e funzioni di memoize . L'hash della chiamata di funzione sarà la chiave e la cache (in Velocity ) invece di richiamare nuovamente la funzione. Facile peasy, mac-and-cheesy.

Ho già dato su sulla capacità di rilevare effetti collaterali nelle funzioni decorate, che si è rivelato essere un "problema difficile", anche per gli esperti, cosa che certamente non lo sono. Successivamente, devo capire quali altre funzioni sono candidate alla memoizzazione.

• Che dire dei metodi che prendono tipi di riferimento complessi come parametri?
• Che dire dei metodi che dipendono dai dati all'interno delle istanze da cui vengono chiamati?

Gli oggetti dati di tipo ActiveRecord vengono in mente su quest'ultimo.

Devo rifattare il codice vecchio di una settimana per supportare la memoizzazione?

Answer 1

Puoi memorizzare una funzione solo se tutti i suoi input sono tipi di valore o tipi di riferimento immutabili, se restituisce un tipo di valore o una nuova istanza di un tipo di riferimento e se non ha effetti collaterali. Periodo.

La memoizzazione dipende da una mappatura deterministica tra ingressi e uscite. Ogni chiamata a F (a, b, c) in cui a, b e c contengono gli stessi valori deve restituire lo stesso risultato affinché sia ??possibile la memoizzazione.

Se un parametro è un tipo di riferimento, anche se il suo valore non cambia, più chiamate alla funzione che lo utilizza possono produrre un risultato diverso. Un esempio banale:

public int MyFunction(MyType t)
{
   return t.Value;
}

Console.WriteLine(MyFunction(t));
t.Value++;
Console.WriteLine(MyFunction(t));

Allo stesso modo, se una funzione dipende da un valore esterno ad essa, allora più chiamate a quella funzione con gli stessi parametri possono restituire risultati diversi:

int Value = 0;

public int MyFunction(int input)
{
   return Value;
}

Console.WriteLine(MyFunction(1));
Value++;
Console.WriteLine(MyFunction(1));

E heaven ti aiuta se la tua funzione memorizzata fa qualcosa di diverso da restituire un valore o un nuovo tipo di riferimento:

int Value = 0;

public int MyFunction(int input)
{
   Value++;
   return input;
}

Se si chiama quella funzione 10 volte, Value sarà 10. Se la si refactoring per utilizzare la memoization e quindi la si chiama 10 volte, Value sarà 1.

Puoi iniziare a capire come memorizzare lo stato, in modo da poter definire una funzione che memorizza un tipo di riferimento. Ma ciò che stai davvero memorizzando è l'insieme di valori su cui funziona la funzione. Allo stesso modo puoi hackerare una funzione memorizzata che ha effetti collaterali in modo che i suoi effetti collaterali si verifichino prima della memorizzazione dei ricordi. Ma tutto ciò sta implorando problemi.

Se si desidera implementare la memoizzazione in una funzione che accetta un tipo di riferimento, l'approccio corretto è quello di refactoring la parte della funzione che funziona solo su tipi di valore e memorizzare tale funzione, ad es .:

public int MyFunction(MyType t)
{
   return t.Value + 1;
}

a questo:

public int MyFunction(MyType t)
{
   return MyMemoizableFunction(t.Value);
}

private int MyMemoizableFunction(int value)
{
   return value + 1;
}

Qualunque altro approccio all'implementazione della memoizzazione che prendi a) fa la stessa cosa, attraverso mezzi più oscuri, oppure b) non funzionerà.

Answer 2

Bene, qualsiasi funzione, teoricamente, è un candidato per la memoizzazione. Tuttavia, ricorda che la memoizzazione riguarda lo spazio di trading per la velocità -

In generale, ciò significa che, più stato richiede o dipende da una funzione per calcolare una risposta, maggiore è il costo dello spazio, che riduce la desiderabilità di memorizzare il metodo.

Entrambi i tuoi esempi sono fondamentalmente casi in cui sarebbe necessario salvare più stati. Questo ha due effetti collaterali.

In primo luogo, ciò richiederà molto più spazio di memoria per memorizzare la funzione, poiché sarà necessario salvare più informazioni.

In secondo luogo, questo rallenterà potenzialmente la funzione memorizzata, poiché maggiore è lo spazio, maggiore è il costo della ricerca della risposta, nonché maggiore è il costo nel determinare se un risultato è stato precedentemente salvato.

In generale, tendo a considerare solo le funzioni che hanno pochi input possibili e bassi requisiti di archiviazione, a meno che non ci sia un costo molto elevato nel calcolo della risposta.

So che questo è vago, ma fa parte del "talento artistico". in architettura. Non c'è "giusto" rispondere senza implementare entrambe le opzioni (funzioni memorizzate e non memorizzate), creazione di profili e misurazione.

Answer 3

Hai già pensato a un modo per fornire una soluzione AOP per fornire una memoizzazione sulla funzione Foo , quindi cosa resta da capire?

Sì, puoi passare un oggetto di complessità arbitraria come parametro a una funzione memorizzata, purché sia ??immutabile, così come lo sono tutte le cose da cui dipende. Ancora una volta, questo non è affatto facile da scoprire staticamente al momento.

Sei ancora legato all'idea di poter esaminare staticamente il codice al fine di consigliare i tuoi utenti sulla domanda " È una buona idea applicare la memoization alla funzione Foo ? "

Se soddisfi questo requisito, ti unirai a uno sforzo di ricerca globale che dura da molti anni. Dipende da quanto sei ambizioso, immagino.