Python Memoization手动缓存

基础概念

Memoization（记忆化）是一种优化技术，主要用于通过将函数的计算结果缓存起来，避免重复计算，从而提高程序的运行效率。在Python中，Memoization可以通过手动实现缓存机制来完成。

类型

Python中的Memoization实现主要有以下几种类型：

基于字典的手动缓存：通过使用字典来存储函数的输入和输出，实现简单的缓存机制。
装饰器实现的自动缓存：使用Python的装饰器功能，可以更加优雅地实现Memoization。

应用场景

Memoization特别适用于以下场景：

递归函数：在递归调用中，很多子问题会被重复计算，使用Memoization可以避免这种重复计算。
复杂计算：对于一些计算量大且结果可重用的函数，使用Memoization可以显著提高效率。

示例代码（基于字典的手动缓存）

def memoize(func):
    cache = {}

    def wrapper(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]

    return wrapper

@memoize
def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(10))  # 输出 55

遇到的问题及解决方法

问题：缓存数据过多导致内存占用过高。

原因：随着缓存的不断增长，可能会消耗大量内存资源。

解决方法：

设置缓存大小限制：可以设定一个最大缓存大小，当缓存达到这个大小后，使用某种策略（如LRU，最近最少使用）来淘汰旧的缓存数据。
手动清理缓存：在适当的时候手动清理不再需要的缓存数据。

def memoize_with_limit(max_size):
    def decorator(func):
        cache = {}
        keys = []

        def wrapper(*args):
            if args not in cache:
                if len(keys) >= max_size:
                    oldest_key = keys.pop(0)
                    del cache[oldest_key]
                cache[args] = func(*args)
                keys.append(args)
            return cache[args]

        return wrapper
    return decorator

@memoize_with_limit(100)
def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(10))  # 输出 55