La memorizzazione delle funzioni è solo per le primitive?

4

Ci stavo pensando da un po 'di tempo. La funzione di memoizzazione è solo per le primitive?

Al momento ho questo codice:

Public Shared Function Mize(Of TArg1 As Structure, TResult)(ByVal input_f As System.Func(Of TArg1, TResult)) As System.Func(Of TArg1, TResult)
    Dim map = New System.Collections.Generic.Dictionary(Of TArg1, TResult)
    Return Function(arg1 As TArg1)
               If map.ContainsKey(arg1) Then Return map.Item(arg1)
               Dim result = input_f(arg1)
               map.Add(arg1, result)
               Return result
           End Function
End Function

E mi chiedo se dovrei aggiornare TArg1 in modo tale da poter accettare qualsiasi classe arbitraria?

    
posta Pacerier 18.05.2011 - 12:57
fonte

4 risposte

11

Is function memoization really only for primitives?

No. Chi te l'ha detto?

I'm wondering should i upgrade TArg1 such that it could accept any arbitrary class?

Assolutamente sì. Non c'è alcuna ragione per cui il tuo metodo di ordine superiore debba essere limitato a funzioni che assumono tipi di valore, fino a quando il valore che utilizzi come argomento non verrà modificato in modo tale da perdersi in una tabella hash . Non dovresti mettere gli oggetti in una tabella hash e poi mutarli.

Uso sempre la tua tecnica. Di solito qualcosa di simile in C #:

static Func<A, R> Memoize(this Func<A, R> f)
{
    var dict = new Dictionary<A, R>();
    return (A arg)=>
    {
        R result;
        if (!dict.TryGetValue(arg, out result))
        {
             result = f(arg);
             dict.Add(arg, result);
        }
        return result;
    };
}

E ora puoi dire:

Func<int, int> fib = null;
fib = x=> x < 2 ? 1 : fib(x-1) + fib(x-2);
fib = fib.Memoize();

E hey presto, hai una implementazione memoized di fib.

Ora ecco una sfida: fai lo stesso per le funzioni di due argomenti.

    
risposta data 19.05.2011 - 09:01
fonte
2

La tua domanda è un po 'vaga, ma la mia risposta è: no.

La Memoizzazione è solo una tecnica per la memorizzazione nella cache invisibile / incapsulata nell'ambito della funzione, e puoi renderla complessa come desideri. Qualsiasi oggetto che, in qualunque lingua / ambiente specifico stai usando, può essere usato come chiave per la cache, e qualsiasi oggetto può essere memorizzato come valore memorizzato nella cache per evitare costosi ricalcoli.

Non riconosco la lingua nell'esempio, ma in Java, ad esempio, qualsiasi oggetto può essere una chiave in una mappa / tabella hash, quindi non è limitato ai tipi primitivi.

    
risposta data 18.05.2011 - 17:53
fonte
1

Memoization è una tecnica di ottimizzazione generale utilizzata per evitare il calcolo ripetuto dei risultati per gli input precedentemente elaborati. Può certamente essere usato su qualsiasi tipo di dati, non solo per le primitive. La cache HTTP, ad esempio, può essere vista come una forma di memoizzazione (di livello superiore).

Non capisco appieno la tua domanda, ma sembra che tu stia cercando di fornire una funzione di memoizzazione generica, "Mize"? Questo non è proprio il modo in cui viene utilizzata la memoizzazione. Viene utilizzato caso per caso. O è una specie di esempio?

    
risposta data 18.05.2011 - 18:16
fonte
1

Perché la memoizzazione sia efficace, hai davvero bisogno della tua funzione per puro, il risultato dipende solo dalle sue argomentazioni e non causa effetti collaterali. Se i tuoi argomenti hanno una semantica dell'oggetto di valore (in .net questo significa renderli immutabili e sovrascrivono gli operatori gethashcode e di uguaglianza), quindi non è un problema usarli come chiavi per la cache lookaside.

Sembra che tu stia cercando di creare una sorta di funzione di utilità di memoizzazione generica - potresti invece voler utilizzare una programmazione orientata all'aspetto per farlo (es. usando qualcosa come PostSharp , che ha già un aspetto memoisation che puoi usare).

    
risposta data 18.05.2011 - 23:16
fonte

Leggi altre domande sui tag