跳至主要內容

记忆化模式

SunnyFan大约 12 分钟约 3480 字

记忆化模式

简介

记忆化（Memoization）缓存函数的计算结果，相同输入直接返回缓存值而不重新计算。理解记忆化模式，有助于优化纯函数和计算密集型操作的性能。

记忆化的本质是一种"以空间换时间"的优化策略。它最早出现在函数式编程语言中，Haskell 的惰性求值天然支持记忆化。在现代编程中，记忆化被广泛应用于递归优化、动态规划、数据转换、API 缓存等场景。其核心思想非常简单：如果一个函数对于相同的输入总是返回相同的输出（即纯函数），那么就没有必要重复计算。

特点

结构分析

UML 类图

+-------------------+
|   Memoization     |
| (静态工具类)       |
+-------------------+
| +Memoize<T,R>()   |----> Func<T, R> (包装后的缓存函数)
| +Memoize<T1,T2,R>()|
| +MemoizeWithExpiry |
| +MemoizeWithLRU    |
+-------------------+
        |
        v
+-------------------+
| ConcurrentDict    |
| (缓存存储)         |
| +GetOrAdd()       |
+-------------------+

+-------------------+
| LRUCache<TKey,    |
|   TValue>         |
+-------------------+
| -_capacity: int   |
| -_cache: Dictionary|
| -_list: LinkedList|
| +TryGetValue()    |
| +Add()            |
+-------------------+

核心流程

调用方 ---> 记忆化函数 ---> 缓存命中?
                            |
               +------------+------------+
               |                         |
            是(命中)                  否(未命中)
               |                         |
          返回缓存值              执行原始函数
                                       |
                                  缓存结果
                                       |
                                  返回结果

实现

基础记忆化

public static class Memoization
{
    // 单参数记忆化
    public static Func<T, TResult> Memoize<T, TResult>(Func<T, TResult> func) where T : notnull
    {
        var cache = new ConcurrentDictionary<T, TResult>();
        return input => cache.GetOrAdd(input, func);
    }

    // 双参数记忆化
    public static Func<T1, T2, TResult> Memoize<T1, T2, TResult>(Func<T1, T2, TResult> func)
        where T1 : notnull where T2 : notnull
    {
        var cache = new ConcurrentDictionary<(T1, T2), TResult>();
        return (t1, t2) => cache.GetOrAdd((t1, t2), _ => func(t1, t2));
    }

    // 带过期时间的记忆化
    public static Func<T, TResult> MemoizeWithExpiry<T, TResult>(
        Func<T, TResult> func, TimeSpan expiry) where T : notnull
    {
        var cache = new ConcurrentDictionary<T, (TResult Result, DateTime ExpiresAt)>();
        return input =>
        {
            if (cache.TryGetValue(input, out var entry) && entry.ExpiresAt > DateTime.UtcNow)
                return entry.Result;

            var result = func(input);
            cache[input] = (result, DateTime.UtcNow.Add(expiry));
            return result;
        };
    }

    // 带 LRU 淘汰的记忆化
    public static Func<T, TResult> MemoizeWithLRU<T, TResult>(
        Func<T, TResult> func, int capacity) where T : notnull
    {
        var cache = new LRUCache<T, TResult>(capacity);
        return input =>
        {
            if (cache.TryGetValue(input, out var result)) return result;
            result = func(input);
            cache.Add(input, result);
            return result;
        };
    }
}

// LRU 缓存
public class LRUCache<TKey, TValue> where TKey : notnull
{
    private readonly int _capacity;
    private readonly Dictionary<TKey, LinkedListNode<(TKey Key, TValue Value)>> _cache = new();
    private readonly LinkedList<(TKey Key, TValue Value)> _list = new();

    public LRUCache(int capacity) => _capacity = capacity;

    public bool TryGetValue(TKey key, out TValue value)
    {
        if (_cache.TryGetValue(key, out var node))
        {
            _list.Remove(node);
            _list.AddFirst(node);
            value = node.Value.Value;
            return true;
        }
        value = default!;
        return false;
    }

    public void Add(TKey key, TValue value)
    {
        if (_cache.TryGetValue(key, out var node))
        {
            _list.Remove(node);
            _list.AddFirst((key, value));
            _cache[key] = _list.First!;
        }
        else
        {
            if (_cache.Count >= _capacity)
            {
                var last = _list.Last!;
                _cache.Remove(last.Value.Key);
                _list.RemoveLast();
            }
            _list.AddFirst((key, value));
            _cache[key] = _list.First!;
        }
    }
}

使用示例

// 斐波那契 — 未记忆化 O(2^n)
long FibNaive(int n) => n <= 1 ? n : FibNaive(n - 1) + FibNaive(n - 2);

// 斐波那契 — 记忆化 O(n)
var fib = Memoization.Memoize<int, long>(n => n <= 1 ? n : fib(n - 1) + fib(n - 2));
Console.WriteLine(fib(50)); // 瞬间完成

// 阶乘
var factorial = Memoization.Memoize<int, long>(n => n <= 1 ? 1 : n * factorial(n - 1));

// 字符串哈希 — 带过期
var expensiveHash = Memoization.MemoizeWithExpiry<string, string>(
    input => Convert.ToBase64String(System.Security.Cryptography.SHA256.HashData(System.Text.Encoding.UTF8.GetBytes(input))),
    TimeSpan.FromMinutes(5)
);

// 配置查找 — 带 LRU
var configLookup = Memoization.MemoizeWithLRU<string, string?>(key =>
{
    Console.WriteLine($"查找配置: {key}");
    return $"value_of_{key}";
}, capacity: 100);

异步记忆化

public static class AsyncMemoization
{
    public static Func<T, Task<TResult>> Memoize<T, TResult>(Func<T, Task<TResult>> func) where T : notnull
    {
        var cache = new ConcurrentDictionary<T, Lazy<Task<TResult>>>();
        return input => cache.GetOrAdd(input, _ => new Lazy<Task<TResult>>(() => func(input))).Value;
    }
}

// 使用 — 缓存 HTTP 请求
var cachedApi = AsyncMemoization.Memoize<string, string>(async url =>
{
    using var client = new HttpClient();
    Console.WriteLine($"请求: {url}");
    return await client.GetStringAsync(url);
});

var result1 = await cachedApi("https://api.example.com/config");
var result2 = await cachedApi("https://api.example.com/config"); // 缓存命中

实战：权限树缓存

在业务系统中，权限树往往需要递归计算每个节点及其子节点的权限集合，且权限数据在用户会话期间基本不变，非常适合记忆化。

// 权限节点
public class PermissionNode
{
    public string Name { get; init; } = "";
    public List<string> DirectPermissions { get; init; } = new();
    public List<PermissionNode> Children { get; init; } = new();
}

// 权限服务
public class PermissionService
{
    private readonly Func<string, HashSet<string>> _getEffectivePermissions;

    public PermissionService()
    {
        // 使用记忆化缓存权限计算结果
        _getEffectivePermissions = Memoization.Memoize<string, HashSet<string>>(CalculatePermissions);
    }

    // 计算某个角色的有效权限（递归 + 记忆化）
    private HashSet<string> CalculatePermissions(string roleName)
    {
        var node = LoadPermissionTree(roleName);
        var permissions = new HashSet<string>(node.DirectPermissions);

        foreach (var child in node.Children)
        {
            var childPerms = _getEffectivePermissions(child.Name);
            permissions.UnionWith(childPerms);
        }

        return permissions;
    }

    // 对外接口
    public HashSet<string> GetPermissions(string roleName) => _getEffectivePermissions(roleName);

    private PermissionNode LoadPermissionTree(string role) => new(); // 模拟加载
}

// 使用
var service = new PermissionService();
var perms = service.GetPermissions("admin"); // 首次计算并缓存
var permsAgain = service.GetPermissions("admin"); // 缓存命中，瞬间返回

实战：汇率转换记忆化

汇率数据在短时间内不会频繁变化，可以结合过期策略进行记忆化缓存。

public class CurrencyConverter
{
    private readonly Func<string, decimal> _getRate;

    public CurrencyConverter()
    {
        // 每 10 分钟过期一次
        _getRate = Memoization.MemoizeWithExpiry<string, decimal>(
            FetchRateFromApi,
            TimeSpan.FromMinutes(10)
        );
    }

    private decimal FetchRateFromApi(string currencyPair)
    {
        Console.WriteLine($"[API 调用] 获取汇率: {currencyPair}");
        // 模拟 API 调用
        return currencyPair switch
        {
            "USD_CNY" => 7.25m,
            "EUR_CNY" => 7.85m,
            "GBP_CNY" => 9.15m,
            _ => throw new ArgumentException($"不支持的货币对: {currencyPair}")
        };
    }

    public decimal Convert(decimal amount, string from, string to)
    {
        if (from == to) return amount;

        var fromToUsd = _getRate($"{from}_USD");
        var usdToTo = _getRate($"USD_{to}");
        return amount * fromToUsd * usdToTo;
    }
}

// 使用
var converter = new CurrencyConverter();
Console.WriteLine(converter.Convert(100, "USD", "CNY")); // API 调用
Console.WriteLine(converter.Convert(200, "USD", "CNY")); // 缓存命中
Console.WriteLine(converter.Convert(50, "EUR", "CNY"));  // API 调用（新货币对）

实战：表达式编译缓存

在规则引擎中，将字符串表达式编译为委托是一个昂贵的操作，适合记忆化。

public class ExpressionCompiler
{
    // 缓存编译后的委托，避免重复编译
    private static readonly ConcurrentDictionary<string, Func<decimal, decimal, bool>>
        _compiledExpressions = new();

    public static Func<decimal, decimal, bool> Compile(string expression)
    {
        return _compiledExpressions.GetOrAdd(expression, expr =>
        {
            Console.WriteLine($"[编译] 表达式: {expr}");
            // 模拟编译过程
            return expr switch
            {
                "amount > threshold" => (amount, threshold) => amount > threshold,
                "amount >= threshold" => (amount, threshold) => amount >= threshold,
                "amount == threshold" => (amount, threshold) => amount == threshold,
                _ => throw new NotSupportedException($"不支持的表达式: {expr}")
            };
        });
    }
}

// 使用
var rule1 = ExpressionCompiler.Compile("amount > threshold");
var rule2 = ExpressionCompiler.Compile("amount > threshold"); // 缓存命中，不重复编译
Console.WriteLine(rule1(150, 100)); // true

缓存策略对比

策略实现方式适用场景内存占用数据新鲜度
无限缓存ConcurrentDictionary数据量小、永不变化持续增长永不过期
固定过期过期时间戳数据周期性变化可控过期后刷新
LRU 淘汰LinkedList + Dictionary数据量大、热点集中固定上限冷数据淘汰
LFU 淘汰频率计数 + 堆访问模式稳定固定上限低频数据淘汰
分层缓存L1(内存) + L2(分布式)高并发大流量多层分层过期

与其他模式的对比

记忆化 vs 缓存（Cache）

记忆化                              缓存
+------------------+              +------------------+
| 自动绑定到函数    |              | 独立存储结构      |
| 透明调用          |              | 显式读写          |
| 纯函数专用        |              | 通用场景          |
| 无失效通知        |              | 支持失效策略      |
| 键 = 函数参数     |              | 键 = 任意字符串    |
+------------------+              +------------------+

记忆化可以看作是缓存的一种特殊形式 —— 它直接绑定到函数调用，对调用方完全透明。而传统缓存（如 IMemoryCache、Redis）是独立的数据存储，需要显式地读写。

记忆化 vs 代理模式

代理模式也可以实现缓存功能（缓存代理），但两者的关注点不同：

  • 记忆化关注的是函数级别的缓存，通过包装函数实现
  • 代理模式关注的是对象级别的控制，通过代理类实现

性能考量

缓存命中率的衡量

public class MemoizationMetrics
{
    private long _hits;
    private long _misses;

    public void RecordHit() => Interlocked.Increment(ref _hits);
    public void RecordMiss() => Interlocked.Increment(ref _misses);

    public double HitRate => _hits + _misses == 0 ? 0 : (double)_hits / (_hits + _misses);
    public override string ToString() => $"命中: {_hits}, 未命中: {_misses}, 命中率: {HitRate:P1}";
}

// 带指标的记忆化
public static Func<T, TResult> MemoizeWithMetrics<T, TResult>(
    Func<T, TResult> func,
    MemoizationMetrics metrics) where T : notnull
{
    var cache = new ConcurrentDictionary<T, TResult>();
    return input =>
    {
        if (cache.TryGetValue(input, out var result))
        {
            metrics.RecordHit();
            return result;
        }

        metrics.RecordMiss();
        return cache.GetOrAdd(input, func);
    };
}

内存监控

public class MonitoredMemoization<T, TResult> where T : notnull
{
    private readonly ConcurrentDictionary<T, TResult> _cache = new();
    private readonly int _maxSize;
    private readonly Action<string> _onEvict;

    public MonitoredMemoization(int maxSize, Action<string>? onEvict = null)
    {
        _maxSize = maxSize;
        _onEvict = onEvict ?? (_ => { });
    }

    public TResult GetOrAdd(T key, Func<T, TResult> factory)
    {
        if (_cache.Count >= _maxSize && !_cache.ContainsKey(key))
        {
            _onEvict($"缓存已满 ({_cache.Count}/{_maxSize})，考虑清理");
        }

        return _cache.GetOrAdd(key, factory);
    }

    public int Count => _cache.Count;
    public void Clear() => _cache.Clear();
}

最佳实践

  1. 仅用于纯函数：确保函数没有副作用（不修改外部状态、不依赖外部可变状态），否则缓存结果可能与实际行为不一致。

  2. 设置合理的容量上限：无限制的缓存会导致内存泄漏，特别是输入空间无限大的场景。

  3. 考虑线程安全：ConcurrentDictionary 是线程安全的，但如果缓存值本身是可变对象，仍需注意。

  4. 注意参数类型：参数必须正确实现 GetHashCode() 和 Equals()，否则缓存无法正确匹配。

  5. 监控缓存效果：记录命中率、缓存大小等指标，验证记忆化是否真正带来性能提升。

  6. 避免缓存大对象：缓存大对象会快速消耗内存，必要时只缓存计算结果的摘要或引用。

常见陷阱

陷阱 1：缓存了有副作用的函数

// 错误示范 — 函数有副作用，不应记忆化
var counter = 0;
var badMemo = Memoization.Memoize<int, int>(n =>
{
    counter++; // 副作用：递增计数器
    Console.WriteLine($"计算: {n}");
    return n * 2;
});

badMemo(5); // 输出 "计算: 5"，counter = 1
badMemo(5); // 缓存命中，counter 仍然是 1（预期可能是 2）

陷阱 2：引用类型参数的问题

// 错误示范 — 数组作为参数，每次 new 都是不同的引用
var memo = Memoization.Memoize<int[], int>(arr => arr.Sum());

memo(new[] { 1, 2, 3 }); // 未命中，计算结果 6
memo(new[] { 1, 2, 3 }); // 未命中！因为数组引用不同

// 正确做法 — 使用值类型或自定义 key
var memo2 = Memoization.Memoize<string, int>(key =>
{
    var arr = key.Split(',').Select(int.Parse).ToArray();
    return arr.Sum();
});

memo2("1,2,3"); // 命中
memo2("1,2,3"); // 命中

陷阱 3：忘记清理缓存导致内存泄漏

// 危险 — 无限缓存，输入空间无限大
var leakMemo = Memoization.Memoize<Guid, string>(guid =>
{
    // 如果 Guid 每次都不同，缓存会无限增长
    return $"result_{guid}";
});

// 安全做法 — 使用 LRU 或过期策略
var safeMemo = Memoization.MemoizeWithLRU<Guid, string>(
    guid => $"result_{guid}",
    capacity: 1000
);

.NET 生态中的记忆化

  • ASP.NET Core 响应缓存：ResponseCache 属性和 IMemoryCache 可以缓存 HTTP 响应
  • EF Core 查询缓存：通过二级缓存插件实现查询结果缓存
  • 分布式缓存：IDistributedCache（Redis、SQL Server）实现跨进程缓存

优点

缺点

总结

记忆化模式用 ConcurrentDictionary 缓存函数结果，相同输入直接返回缓存。可配合过期时间、LRU 淘汰、容量限制等策略控制缓存大小。异步版本使用 Lazy<Task<T>> 避免重复执行。仅适用于纯函数（无副作用）。建议在递归计算（斐波那契、阶乘）、配置查找、数据转换等重复计算场景使用记忆化。

记忆化的核心价值在于：当你确认一个函数的输入空间有限、计算成本高、且调用频繁时，用少量内存换取大量计算时间的节省。这是一种"算一次、用多次"的朴素智慧。

关键知识点

  • 模式不是目标，降低耦合和控制变化才是目标。
  • 先找变化点、稳定点和协作边界，再决定是否引入模式。
  • 同一个模式在不同规模下的收益和代价差异很大。

项目落地视角

  • 优先画出参与对象、依赖方向和调用链，再落到代码。
  • 把模式放到一个真实场景里，比如支付、规则引擎、工作流或插件扩展。
  • 配合单元测试或契约测试，保证重构后的行为没有漂移。

常见误区

  • 为了看起来"高级"而套模式。
  • 把简单问题拆成过多抽象层，导致阅读和排障都变难。
  • 只会背 UML，不会解释为什么这里需要这个模式。

进阶路线

  • 继续关注模式之间的组合用法，而不是孤立记忆。
  • 从业务建模、演进策略和团队协作角度看模式的适用性。
  • 把模式结论沉淀为项目模板、基类或约束文档。

适用场景

  • 当你准备把《记忆化模式》真正落到项目里时，最适合先在一个独立模块或最小样例里验证关键路径。
  • 适合在业务规则频繁变化、分支增多或对象协作复杂时引入。
  • 当你希望提高扩展性，但又不想把系统拆得过度抽象时，这类主题很有参考价值。

落地建议

  • 先识别变化点，再决定是否引入模式，而不是反过来套模板。
  • 优先为模式的边界、依赖和调用路径画出简单结构图。
  • 把模式落到一个明确场景，例如支付、规则计算、插件扩展或工作流。

排错清单

  • 检查抽象层是否过多，导致调用路径和责任不清晰。
  • 确认引入模式后是否真的减少了条件分支和重复代码。
  • 警惕"为了模式而模式"，尤其是在简单业务里。

复盘问题

  • 如果把《记忆化模式》放进你的当前项目，最先要验证的输入、输出和失败路径分别是什么？
  • 《记忆化模式》最容易在什么规模、什么边界条件下暴露问题？你会用什么指标或日志去确认？
  • 相比默认实现或替代方案，采用《记忆化模式》最大的收益和代价分别是什么？

延伸阅读

Copyright © 2026 SunnyFan