对递归函数使用记忆方法

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();

但编译器抱怨

The '.' operator cannot be applied to operand of type `method group'

和

The left-hand side of an assignment must be a variable, a property or an indexer

如何调用 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;
    }
}

很明显，这种类型的东西会受益于记忆。一开始我避免添加算法，因为它是无关紧要的，而且更有可能让人们给我建议，这是题外话。

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.

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

对递归函数使用记忆方法

Use Memoized Method for Recursive Function

c#

recursion

memoization