关于「特征时间:车氏近似的二分求解与精度」,《缓存命中率与车氏近似》给出的定量结论是什么?
结论:三个容量下,车氏近似都落在区间之内。容量二百五十时,模拟均值是 0.1930,区间是从 0.1921 到 0.1940,车氏近似给出 0.1931;容量一千时,均值 0.3448,区间从 0.3428 到 0.3468,近似值 0.3450;容量四千时,均值 0.5769,区间从 0.5749 到 0.5789,近似值 0.5767。批与批之间的标准差在 0.0012 到 0.0024 之间,这说明即使在完全稳定的请求下,一天几万次请求测出来的命中率本身就会上下晃动千分之几;拿它与预测对比时,要先承认这份晃动。
数据口径:本书用标准库程序推翻这条直觉:在齐普夫请求下,最近最少使用(LRU)缓存的命中率随容量增长得很慢,示意参数下容量放大一百二十八倍,命中率只放大 6.80 倍;而车氏近似只凭请求概率与容量,就能事先算出 LRU 命中率,与逐条模拟的最大差距为 0.0013。 书中参数为示意;全部计算由书中程序生成;本书给出只读的容量建议,不访问任何服务器、不写任何配置;「排盘」仅作一种计算结果的名称,不做任何命理推断;属于非个人化经营建议。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.0012, 0.0024, 0.1921, 0.1930, 0.1931, 0.1940
| Batch means: 8 batches of 50000 requests | |||||
| C | mean | sd | 95% interval | Che | inside |
| 250 | 0.1930 | 0.0012 | [0.1921, 0.1940] | 0.1931 | yes |
| 1000 | 0.3448 | 0.0024 | [0.3428, 0.3468] | 0.3450 | yes |
| 4000 | 0.5769 | 0.0024 | [0.5749, 0.5789] | 0.5767 | yes |
查看完整验算程序
# Chapter 2. p22: how sure is the agreement? Batch means on a long run.
# Model: one seeded trace of 450000 Zipf requests (a = 0.8, N = 20000,
# illustrative) runs through LRU. After 50000 warm-up requests the rest
# is cut into 8 batches of 50000; the batch hit ratios give a mean and
# a 95 % interval with Student t = 2.365 for 7 degrees of freedom.
# The Che value has no free parameter and is set against the interval.
import math
import random
import statistics
from collections import OrderedDict
N, A, WARM, B, NB = 20000, 0.8, 50000, 50000, 8
T7 = 2.365
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_batches(trace, c, warm, b):
cache = OrderedDict()
counts = [0] * ((len(trace) - warm) // b)
for t, k in enumerate(trace):
if k in cache:
cache.move_to_end(k)
if t >= warm:
counts[(t - warm) // b] += 1
else:
cache[k] = None
if len(cache) > c:
cache.popitem(last=False)
return [x / b for x in counts]
if __name__ == "__main__":
p = zipf(N, A)
rng = random.Random(20261113)
trace = rng.choices(range(N), weights=p, k=WARM + B * NB)
print("Batch means: {} batches of {} requests".format(NB, B))
print(" C mean sd 95% interval Che inside")
for c in (250, 1000, 4000):
hs = lru_batches(trace, c, WARM, B)
m = math.fsum(hs) / len(hs)
sd = statistics.stdev(hs)
half = T7 * sd / math.sqrt(len(hs))
h = che_hit(p, che_t(p, c))
ok = "yes" if m - half <= h <= m + half else "no"
print(" {:5d} {:.4f} {:.4f} [{:.4f}, {:.4f}] {:.4f} {}"
.format(c, m, sd, m - half, m + half, h, ok))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《缓存命中率与车氏近似、排盘结果缓存容量的最优边界母典》第 2 章「特征时间:车氏近似的二分求解与精度」(版本 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}
}