使用记忆方法进行递归函数

Question

我有一个记忆器函数，如下所示：

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.Memoize()TheRecursiveMeth包括递归调用？

编辑：我试图避免编辑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;
}
}

很明显，这种事情会从记忆中受益。 起初我避免添加算法，因为它无关紧要，更有可能让人们给我建议，这是无关紧要的。

Answer 1

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

忽略您尝试实例化记忆函数时遇到的问题，主要问题是由于早期绑定，您无法调用记忆函数，编译器将始终绑定到原始函数。 你需要给你的函数实现一个对记忆版本的引用，并让它使用它。 您可以使用一个工厂来实现这一点，该工厂同时接受与记忆函数具有相同签名的函数和 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;
}

然后，这将更改以下功能：

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一起使用。

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

然后，只需确保您的方法已声明为 virtual 并具有适当的属性即可。

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