的遞歸函數

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