Fast memoization with tuples

debugcn 投稿 Dev

Radost

I want to use memoization to speed up code looking similar to (only a small number of possible values of arguments are ever called):

double MyFun(double a,double b,int c,char d)
{
    double a = cpu_intensive_pure_function_1(a,c,d);
    double b = cpu_intensive_pure_function_2(b,c,d);
    return a+b;
}

One possibility is to wrap args into a Tuple object and use Dictionary (new versions of Dotnet have hashing of tuples done for you)

Dictionary<Tuple<double,double,int,char>,double> MyFunCache = new Dictionary<Tuple<double,double,int,char>,double> ();
double MyFun(double a,double b,int c,char d)
{
    var tmp = Tuple<double,double,int,char>(a,b,c,d);
    if(MyFunCache.ContainsKey(tmp))
    {
         return MyFunCache[tmp];
    }

    double a = cpu_intensive_pure_function_1(a,c,d);
    double b = cpu_intensive_pure_function_2(b,c,d);
    return a+b;
}

But this requires creating an Tuple object every time function is called which seems wasteful, isn't there some better way? Something holding the arguments already?

Sean

You can use a ValueTuple instead. Also, remember to update the cache once you've got the computed value:

Dictionary<(double,double,int,char) ,double> MyFunCache = new Dictionary<(double,double,int,char) ,double> ();
double MyFun(double a,double b,int c,char d)
{
    var key = (a,b,c,d);
    if(MyFunCache.TryGetValue(key, out var cachedResult))
    {
         return cachedResult;
    }

    double a = cpu_intensive_pure_function_1(a,c,d);
    double b = cpu_intensive_pure_function_2(b,c,d);

    MyFunCache.Add(key, a+ b);
    return a+b;
}

この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。

侵害の場合は、連絡してください[email protected]

編集2021-06-12

コメントを追加

サインイン

分類Dev

What is the need or benefit to use an instance variable/function attribute to implement memoization vs passing down the memo in each call?

Related 関連記事

記事