记忆化

概念定义

纯函数的历史就是一张查找表。记忆化在函数运行时把这张表物化：首次调用计算，之后调用直读。递归密集的算法——斐波那契、解析、树编辑距离——从指数塌缩到线性。

工作机制

包装器从参数计算缓存键——身份、结构哈希或序列化——命中即返回缓存值。弱键映射让条目随参数一起蒸发，避免泄漏；语言级变体包括带容量上限的 lru_cache 与按结构键控的编译器记忆表。

使用场景

参数集合重复的纯昂贵计算：递归求解器、派生数据选择器、纯组件渲染输出。不纯或 I/O 密集的函数要先重构成“纯核心加副作用外壳”再谈记忆化。

常见误区

不纯函数（读时钟、读可变状态）记忆化后会拿昨天的答案。键语义决定一切：对象身份键在结构相等时 miss；序列化键顺序不稳定则永远 miss。有界缓存需要淘汰策略，miss 路径要计入收益评估。异常与错误要不要缓存必须有显式策略——缓存一次失败通常就是错的。

代码示例

export interface CacheLookup<V> {
  hit: boolean;
  value?: V;
}

interface CacheEntry<V> {
  value: V | null;
  expiresAt: number;
}

export class NegativeCache<K, V> {
  private readonly entries = new Map<K, CacheEntry<V>>();
  private readonly ttlMs: number;
  private readonly now: () => number;

  constructor(ttlMs: number, now: () => number = () => Date.now()) {
    if (!Number.isFinite(ttlMs) || ttlMs <= 0) {
      throw new RangeError("ttlMs must be a positive finite number");
    }
    if (typeof now !== "function") throw new TypeError("now must be a function");
    this.ttlMs = ttlMs;
    this.now = now;
  }

  get(key: K): CacheLookup<V> {
    const entry = this.entries.get(key);
    if (!entry) return { hit: false };
    if (this.now() >= entry.expiresAt) {
      this.entries.delete(key);
      return { hit: false };
    }
    if (entry.value === null) return { hit: true };
    return { hit: true, value: entry.value };
  }

  setMiss(key: K): void {
    this.entries.set(key, { value: null, expiresAt: this.now() + this.ttlMs });
  }

  setValue(key: K, value: V): void {
    if (value === null) throw new TypeError("value must not be null; use setMiss");
    this.entries.set(key, { value, expiresAt: this.now() + this.ttlMs });
  }

  delete(key: K): boolean {
    return this.entries.delete(key);
  }

  get size(): number {
    return this.entries.size;
  }
}

export async function withNegativeCache<K, V>(
  cache: NegativeCache<K, V>,
  key: K,
  loader: () => Promise<V | null>,
): Promise<V | null> {
  if (typeof loader !== "function") throw new TypeError("loader must be a function");
  const cached = cache.get(key);
  if (cached.hit) return cached.value ?? null;
  const value = await loader();
  if (value === null) cache.setMiss(key);
  else cache.setValue(key, value);
  return value;
}

export function memoize(fn, ttlMs = 60000) {
  const cache = new Map();
  return function memoized(key, ...rest) {
    const now = Date.now();
    const entry = cache.get(key);
    if (entry && now - entry.at < ttlMs) {
      return entry.value;
    }
    const value = fn(key, ...rest);
    cache.set(key, { value, at: now });
    return value;
  };
}