关于「翻倍的错觉:齐普夫请求下的命中率曲线」,《缓存命中率与车氏近似》给出的定量结论是什么?
结论:四个容量下,模拟命中率分别是 0.1380、0.2624、0.4496 与 0.7374,车氏近似给出的是 0.1373、0.2613、0.4483 与 0.7367,差距分别是 -0.0007、-0.0010、-0.0013 与 -0.0007,最大的绝对差距只有 0.0013。车氏近似没有任何从模拟里拟合出来的参数,它只用了请求概率和容量两样输入。对一个容量规划问题来说,这样的误差已经远小于请求概率本身的估计误差:第八章会看到,单是齐普夫指数估得偏一点,带来的误差就比这里大一个数量级。
数据口径:本书用标准库程序推翻这条直觉:在齐普夫请求下,最近最少使用(LRU)缓存的命中率随容量增长得很慢,示意参数下容量放大一百二十八倍,命中率只放大 6.80 倍;而车氏近似只凭请求概率与容量,就能事先算出 LRU 命中率,与逐条模拟的最大差距为 0.0013。 书中参数为示意;全部计算由书中程序生成;本书给出只读的容量建议,不访问任何服务器、不写任何配置;「排盘」仅作一种计算结果的名称,不做任何命理推断;属于非个人化经营建议。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: -0.0007, -0.0010, -0.0013, 0.0013, 0.1373, 0.1380
| LRU simulation vs Che, 250000 scored requests | |||
| C | simulated | Che | Che - sim |
| 125 | 0.1380 | 0.1373 | -0.0007 |
| 500 | 0.2624 | 0.2613 | -0.0010 |
| 2000 | 0.4496 | 0.4483 | -0.0013 |
| 8000 | 0.7374 | 0.7367 | -0.0007 |
| largest absolute gap = 0.0013 |
查看完整验算程序
# Chapter 1. p13: a seeded LRU simulation against the Che prediction.
# Model: 300000 independent Zipf requests (a = 0.8, N = 20000 keys,
# illustrative) are replayed through a true LRU cache (OrderedDict);
# the first 50000 requests warm the cache and are not scored. The Che
# approximation is computed for the same p and C with no fitted
# parameter. Fixed seed 20261113, so every run prints the same table.
import math
import random
from collections import OrderedDict
N, A, L, WARM = 20000, 0.8, 300000, 50000
def zipf(n, a):
w = [1.0 / (i ** a) for i in range(1, n + 1)]
s = math.fsum(w)
return [x / s for x in w]
def occupancy(p, t):
return math.fsum(-math.expm1(-x * t) for x in p)
def che_t(p, c, tol=1e-9):
lo, hi = 0.0, 1.0
while occupancy(p, hi) < c:
hi = 2.0 * hi
while hi - lo > tol * hi:
mid = 0.5 * (lo + hi)
if occupancy(p, mid) < c:
lo = mid
else:
hi = mid
return 0.5 * (lo + hi)
def che_hit(p, t):
return math.fsum(x * -math.expm1(-x * t) for x in p)
def lru_hit(trace, c, warm):
cache = OrderedDict()
hits = 0
for t, k in enumerate(trace):
if k in cache:
cache.move_to_end(k)
if t >= warm:
hits += 1
else:
cache[k] = None
if len(cache) > c:
cache.popitem(last=False)
return hits / (len(trace) - warm)
if __name__ == "__main__":
p = zipf(N, A)
rng = random.Random(20261113)
trace = rng.choices(range(N), weights=p, k=L)
print("LRU simulation vs Che, {} scored requests".format(L - WARM))
print(" C simulated Che Che - sim")
worst = 0.0
for c in (125, 500, 2000, 8000):
s = lru_hit(trace, c, WARM)
h = che_hit(p, che_t(p, c))
worst = max(worst, abs(h - s))
print(" {:5d} {:.4f} {:.4f} {:+.4f}".format(c, s, h, h - s))
print("largest absolute gap = {:.4f}".format(worst))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《缓存命中率与车氏近似、排盘结果缓存容量的最优边界母典》第 1 章「翻倍的错觉:齐普夫请求下的命中率曲线」(版本 1.0.0). 5D Library. DOI 待发布
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-327 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026327,
author = {Fan, Yafu},
title = {Cache Hit Ratios and the Che Approximation: Optimal Capacity for Caching Computed Charts},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}