关于「贝拉迪下界:最优替换、静态上界与 LRU 的容量代价」,《缓存命中率与车氏近似》给出的定量结论是什么?
结论:第三章以贝拉迪最优替换为下界、静态前 C 名为上界,算出 LRU 为不知道流行度要多付 4.48 倍槽位。
数据口径:本书用标准库程序推翻这条直觉:在齐普夫请求下,最近最少使用(LRU)缓存的命中率随容量增长得很慢,示意参数下容量放大一百二十八倍,命中率只放大 6.80 倍;而车氏近似只凭请求概率与容量,就能事先算出 LRU 命中率,与逐条模拟的最大差距为 0.0013。 书中参数为示意;全部计算由书中程序生成;本书给出只读的容量建议,不访问任何服务器、不写任何配置;「排盘」仅作一种计算结果的名称,不做任何命理推断;属于非个人化经营建议。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 4.48
| LRU slots needed to match a static top-C cache, N = 20000 | ||||
| a | C | static hit | LRU slots | multiplier |
| 0.8 | 125 | 0.2737 | 559.5 | 4.48 |
| 0.8 | 500 | 0.4055 | 1527.2 | 3.05 |
| 0.8 | 2000 | 0.5795 | 4055.3 | 2.03 |
| 0.8 | 8000 | 0.8092 | 10490.9 | 1.31 |
| 1.0 | 125 | 0.5161 | 428.7 | 3.43 |
| 1.0 | 500 | 0.6481 | 1333.7 | 2.67 |
| 1.0 | 2000 | 0.7803 | 3898.1 | 1.95 |
| 1.0 | 8000 | 0.9126 | 10540.1 | 1.32 |
查看完整验算程序
# Chapter 3. p32: the capacity price LRU pays for not knowing popularity.
# Model: a static cache that knows p keeps the C most popular keys and
# hits with the head share H(C). For the same H, the Che approximation
# says how many LRU slots are needed: bisect on T until the Che hit
# ratio equals H, then read the slots as the occupancy at that T. The
# ratio of the two capacities is LRU's multiplier. N = 20000 keys and
# the Zipf exponents are illustrative.
import math
N = 20000
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_hit(p, t):
return math.fsum(x * -math.expm1(-x * t) for x in p)
def slots_for_hit(p, h, tol=1e-9):
lo, hi = 0.0, 1.0
while che_hit(p, hi) < h:
hi = 2.0 * hi
while hi - lo > tol * hi:
mid = 0.5 * (lo + hi)
if che_hit(p, mid) < h:
lo = mid
else:
hi = mid
return occupancy(p, 0.5 * (lo + hi))
if __name__ == "__main__":
print("LRU slots needed to match a static top-C cache, N = {}"
.format(N))
print(" a C static hit LRU slots multiplier")
for a in (0.8, 1.0):
p = zipf(N, a)
for c in (125, 500, 2000, 8000):
h = math.fsum(p[:c])
s = slots_for_hit(p, h)
print(" {:.1f} {:5d} {:.4f} {:8.1f} {:6.2f}"
.format(a, c, h, s, s / c))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《缓存命中率与车氏近似、排盘结果缓存容量的最优边界母典》第 3 章「贝拉迪下界:最优替换、静态上界与 LRU 的容量代价」(版本 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}
}