关于「贝拉迪下界:最优替换、静态上界与 LRU 的容量代价」,《缓存命中率与车氏近似》给出的定量结论是什么?

结论:第三章以贝拉迪最优替换为下界、静态前 C 名为上界,算出 LRU 为不知道流行度要多付 4.48 倍槽位。

数据口径:本书用标准库程序推翻这条直觉:在齐普夫请求下,最近最少使用(LRU)缓存的命中率随容量增长得很慢,示意参数下容量放大一百二十八倍,命中率只放大 6.80 倍;而车氏近似只凭请求概率与容量,就能事先算出 LRU 命中率,与逐条模拟的最大差距为 0.0013。 书中参数为示意;全部计算由书中程序生成;本书给出只读的容量建议,不访问任何服务器、不写任何配置;「排盘」仅作一种计算结果的名称,不做任何命理推断;属于非个人化经营建议。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 4.48

LRU slots needed to match a static top-C cache, N = 20000
aCstatic hitLRU slotsmultiplier
0.81250.2737559.54.48
0.85000.40551527.23.05
0.820000.57954055.32.03
0.880000.809210490.91.31
1.01250.5161428.73.43
1.05000.64811333.72.67
1.020000.78033898.11.95
1.080000.912610540.11.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}
}

本书其他章节结论