c# - Use Memoized Method for Recursive Function -


i have memoizer function so:

static func<a, r> memoize<a, r>(this func<a, r> f) {     var cache = new concurrentdictionary<a, r>();     return argument => cache.getoradd(argument, f); } 

and have recursive method

long therecursivemeth (string instring) { // recursive function calls     } 

now, in main function, try:

therecursivemeth = therecursivemeth.memoize(); 

but compiler complains

the '.' operator cannot applied operand of type `method group'

and

the left-hand side of assignment must variable, property or indexer

how make calls therecursivemeth call therecursivemeth.memoize(), including recursive calls?

edit: i'm trying avoid editing definition of therecursivemeth. have check dictionary.

edit 2: since you're interested, have function counts number of palindromes of given string. it's little complicated explain here, like:

long palcount(string instring) {     if (instring.length==1) return 1;     else {       count = 0;       foreach(substring of instring) {           // more complex logic here            count += palcount(substring);       }       return count;     } } 

so type of thing benefit memoization. avoided adding algorithm @ first because irrelevant , more people giving me suggestions on that, beside point.

for generalizable solution, you'll have change way write functions in order make work.

ignoring issues had trying instantiate memoized functions, main problem due binding, cannot call memoized function, compiler bind original function. need give function implementation reference memoized version , let use that. achieve using factory takes both function same signature memoized function, , args.

public static func<targs, tresult> memoized<targs, tresult>(func<func<targs, tresult>, targs, tresult> factory, iequalitycomparer<targs> comparer = null) {     var cache = new concurrentdictionary<targs, tresult>(comparer ?? equalitycomparer<targs>.default);     tresult functionimpl(targs args) => cache.getoradd(args, _ => factory(functionimpl, args));     return functionimpl; } 

this changes functions like:

public long fib(long n) {     if (n < 2l)         return 1l;     return fib(n - 1) + fib(n - 2); } 

to this:

private func<long, long> _fibimpl = memoized<long, long>((fib, n) => {     if (n < 2l)         return 1l;     return fib(n - 1) + fib(n - 2); // using `fib`, parameter passed in }); public long fib(long n) => _fibimpl(n); 

for kicks, here's implementation of memoizer interceptor used castle dynamicproxy.

class memoizedattribute : attribute { }  class memoizer<targ, tresult> : iinterceptor {     private readonly concurrentdictionary<targ, tresult> cache;     public memoizer(iequalitycomparer<targ> comparer = null)     {         cache = new concurrentdictionary<targ, tresult>(comparer ?? equalitycomparer<targ>.default);     }     public void intercept(iinvocation invocation)     {         if (!isapplicable(invocation))         {             invocation.proceed();         }         else         {             invocation.returnvalue = cache.getoradd((targ)invocation.getargumentvalue(0),                 _ =>                 {                     invocation.proceed();                     return (tresult)invocation.returnvalue;                 }             );         }     }     private bool isapplicable(iinvocation invocation)     {         var method = invocation.method;         var ismemoized = method.getcustomattribute<memoizedattribute>() != null;         var parameters = method.getparameters();         var hascompatibleargtype = parameters.length == 1 && typeof(targ).isassignablefrom(parameters[0].parametertype);         var hascompatiblereturntype = method.returntype.isassignablefrom(typeof(tresult));         return ismemoized && hascompatibleargtype && hascompatiblereturntype;     } } 

then make sure method declared virtual , has appropriate attribute.

public class fibcalculator {     [memoized]     public virtual long fib(long n)     {         if (n < 2l)             return 1l;         return fib(n - 1) + fib(n - 2);     } }  var calculator = new castle.dynamicproxy.proxygenerator().createclassproxy<fibcalculator>(new memoizer<long, long>()); calculator.fib(5); // 5 invocations calculator.fib(7); // 2 invocations 

Comments

Popular posts from this blog

android - InAppBilling registering BroadcastReceiver in AndroidManifest -

python Tkinter Capturing keyboard events save as one single string -

sql server - Why does Linq-to-SQL add unnecessary COUNT()? -