Golang中的Memoization技术详解

在Golang中实现Memoization时，你遇到了两个典型问题：闭包变量作用域和整数溢出。以下是解决方案：

问题1：闭包中的缓存失效

你的第一个尝试中，每次递归调用都创建了新的缓存map。修正方案：

func memoize(f func(int) uint64) func(int) uint64 {
    cache := make(map[int]uint64)
    return func(n int) uint64 {
        if val, found := cache[n]; found {
            return val
        }
        val := f(n)
        cache[n] = val
        return val
    }
}

func fib(n int) uint64 {
    if n <= 1 {
        return uint64(n)
    }
    return fib(n-1) + fib(n-2)
}

func main() {
    memoizedFib := memoize(fib)
    
    // 关键：需要让fib函数内部也使用memoized版本
    fib = memoizedFib
    
    fmt.Println(fib(50)) // 快速计算
}

更简洁的实现方式：

var cache = make(map[int]uint64)

func fibMemoized(n int) uint64 {
    if n <= 1 {
        return uint64(n)
    }
    
    if val, ok := cache[n]; ok {
        return val
    }
    
    val := fibMemoized(n-1) + fibMemoized(n-2)
    cache[n] = val
    return val
}

问题2：大数溢出（超过93时错误）

当n>93时，斐波那契数超过64位整数范围。使用math/big包：

import "math/big"

var cacheBig = make(map[int]*big.Int)

func fibBigMemoized(n int) *big.Int {
    if n <= 1 {
        return big.NewInt(int64(n))
    }
    
    if val, ok := cacheBig[n]; ok {
        return val
    }
    
    val := new(big.Int)
    val.Add(fibBigMemoized(n-1), fibBigMemoized(n-2))
    cacheBig[n] = val
    return val
}

func main() {
    fmt.Println(fibBigMemoized(100))
    // 输出: 354224848179261915075
}

线程安全的Memoization实现

对于并发环境，需要添加锁：

import "sync"

type MemoizedFib struct {
    cache map[int]*big.Int
    mu    sync.RWMutex
}

func NewMemoizedFib() *MemoizedFib {
    return &MemoizedFib{
        cache: make(map[int]*big.Int),
    }
}

func (m *MemoizedFib) Calculate(n int) *big.Int {
    if n <= 1 {
        return big.NewInt(int64(n))
    }
    
    // 先尝试读锁
    m.mu.RLock()
    if val, ok := m.cache[n]; ok {
        m.mu.RUnlock()
        return val
    }
    m.mu.RUnlock()
    
    // 计算并写入
    m.mu.Lock()
    defer m.mu.Unlock()
    
    // 双重检查，防止其他goroutine已计算
    if val, ok := m.cache[n]; ok {
        return val
    }
    
    val := new(big.Int)
    val.Add(m.Calculate(n-1), m.Calculate(n-2))
    m.cache[n] = val
    return val
}

通用Memoization装饰器

创建可重用的Memoization包装器：

func Memoize[T comparable, R any](f func(T) R) func(T) R {
    cache := make(map[T]R)
    var mu sync.Mutex
    
    return func(input T) R {
        mu.Lock()
        defer mu.Unlock()
        
        if val, ok := cache[input]; ok {
            return val
        }
        
        val := f(input)
        cache[input] = val
        return val
    }
}

// 使用示例
func expensiveCalculation(n int) int {
    time.Sleep(100 * time.Millisecond)
    return n * n
}

func main() {
    memoizedCalc := Memoize(expensiveCalculation)
    
    // 第一次调用计算
    fmt.Println(memoizedCalc(5)) // 耗时100ms
    
    // 第二次调用从缓存读取
    fmt.Println(memoizedCalc(5)) // 立即返回
}

这些实现解决了你的两个问题：缓存生效问题和整数溢出问题。关键点是确保缓存变量在闭包外部声明，并且对于大数使用math/big.Int类型。