如何在Go中使用带有递归函数的缓存装饰器？

Question

我希望每个

fib

执行的结果存储在缓存变量中，但使

cached

装饰器和

fib

函数独立。

问题是，装饰过的

fib

在其内部执行未装饰过的

fib

。 我知道

fib

中的装饰

main

是一个局部变量，但我无法在全局范围内重新定义

fib

（或者我不知道如何）

这可能吗？

package main

import (
    "fmt"
)

func cached(f func(int) int) func(int) int {
    cache := make(map[int]int)
    return func(x int) int {
        if _, ok := cache[x]; !ok {
            cache[x] = f(x)
            fmt.Println(len(cache))
        }
        value, _ := cache[x]
        return value
    }
}

func fib(x int) int {
    if x < 0 {
        return -1
    }
    if x == 0 || x == 1 {
        return 1
    }
    return fib(x-1) + fib(x-2)
}

func main() {
    fib := cached(fib)
    fmt.Println(fib(40))
    fmt.Println(fib(41))
    fmt.Println(fib(42))
    fmt.Println(fib(43))
}

此代码输出：

1
165580141
2
267914296
3
433494437
4
701408733

但是这里的1、2、3、4应该是38、39、40、41

Answer 1

原因是调用的是内部fib而不是缓存的fib。您可以进行以下更改：

package main

import "fmt"

func cached(f func(int) int) func(int) int {
    cache := make(map[int]int)
    return func(x int) int {
        if _, ok := cache[x]; !ok {
            cache[x] = f(x)
        }
        value, _ := cache[x]
        return value
    }
}

var (
    fib func(int) int
    fibCached func(int) int
)
func main() {
    fib = func(x int) int {
        fmt.Printf("call arg:%d\n", x)
        if x <= 1 {
            return x
        } else {
            return fibCached(x-1) + fibCached(x-2)
        }
    }
    fibCached = cached(fib)
    fmt.Println(fibCached(40))
    fmt.Println(fibCached(41))
    fmt.Println(fibCached(42))
    fmt.Println(fibCached(43))
}

或者，您可以使用这个 gocache-decorator 包来实现它。

package main
import "github.com/ahuigo/gocache-decorator"
import "fmt"
func main() {
    var fib func(int) int
    var fibCached func(int) int
    fib = func(x int) int {
        fmt.Printf("call arg:%d\n", x)
        if x <= 1 {
            return x
        } else {
            return fibCached(x-1) + fibCached(x-2)
        }
    }

    fibCached = decorator.CacheFn1(fib, nil)    

    fmt.Println(fibCached(40))
    fmt.Println(fibCached(41))
}