的递归函数

Question

使用Memoized方法我有一个memoizer功能，像这样：

static Func<A, R> Memoize<A, R>(this Func<A, R> f) 
{ 
    var cache = new ConcurrentDictionary<A, R>(); 
    return argument => cache.GetOrAdd(argument, f); 
} 

而且我也有一些递归方法

long TheRecursiveMeth (string inString) { 
// recursive function that calls itself  
} 

现在，在我的主要功能，我尝试：

TheRecursiveMeth = TheRecursiveMeth.Memoize(); 

但编译器抱怨

'。'操作者可以不被施加到型方法组”的'操作数

和

赋值的左手侧必须是一个变量，属性或 索引器

我如何拨打TheRecursiveMeth实际上拨打TheRecursiveMeth.Memoize()，包括递归电话？

编辑：我试图避免编辑TheRecursiveMeth的定义。很明显，我可以只检查字典。

编辑2：既然你有兴趣，我有一个函数来计算给定字符串的某些回文数。这里有点复杂，但基本上是这样的，但基本上类似于：

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; 
    } 
} 

很明显，这种类型的东西会受益于memoization。我首先避免添加算法，因为它是无关紧要的，并且更有可能让人们给我提出建议，这是不言而喻的。

Answer 1

对于完全一般化的解决方案，您必须更改编写函数的方式才能使这一切工作。

忽略你试图实例化你的memoized函数的问题，主要问题是由于早期绑定，你不能调用你的memoized函数，编译器将始终绑定到原始函数。你需要给你的函数实现一个对memoized版本的引用，并让它使用它。你可以使用一个工厂来实现这个功能，这个工厂同时带有一个与memoized函数相同的签名的函数和参数。

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; 
} 

这就改变了功能，如：

public long Fib(long n) 
{ 
    if (n < 2L) 
     return 1L; 
    return Fib(n - 1) + Fib(n - 2); 
} 

这样：

private Func<long, long> _FibImpl = Memoized<long, long>((fib, n) => 
{ 
    if (n < 2L) 
     return 1L; 
    return fib(n - 1) + fib(n - 2); // using `fib`, the parameter passed in 
}); 
public long Fib(long n) => _FibImpl(n); 

---

踢，这里可能与Castle DynamicProxy使用的memoizer拦截器的实现。

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; 
    } 
} 

然后只要确保您的方法是声明为虚拟的并具有适当的属性。

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