关于「超对数对数:首个 1 位、调和平均与 1.04/√m」,《布隆过滤器与基数估计》给出的定量结论是什么?
结论:第二章拆开 HyperLogLog,复算极限常数 1.03896,并说明 m = 16 时常数为 1.106、摘要里 1.5 千字节的例子对应标准误 0.0230。
数据口径:示意网络中,各站独立访客相加是真实人数的 2.224 倍。 书中的站点、访客、订单与流量参数均为示意;全部计算由书中程序生成;本书是非个人化经营建议;访客统计只用匿名化、加密钥哈希的标识,不收集个人身份信息,须遵守所在地个人信息保护法规与站点隐私声明,法规只述大意,以上架前人工复核为准。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 1.03896, 1.106, 16
| beta_inf = sqrt(3 ln 2 - 1) | 1.03896 |
| alpha_inf | 1 / (2 ln 2) = 0.72135 |
| m bias emp.SE SE*sqrt(m) paper in1s in2s in3s | |
| 16 -0.0030 | 0.2814 1.126 1.106 0.684 0.952 0.987 |
| 64 -0.0014 | 0.1304 1.043 1.054 0.686 0.955 0.994 |
| 256 -0.0002 | 0.0658 1.053 1.04 0.674 0.952 0.998 |
| 1024 -0.0002 | 0.0323 1.034 1.04 0.686 0.958 0.997 |
| 4096 -0.0001 | 0.0165 1.059 1.04 0.666 0.954 0.997 |
| paper: within 1, 2, 3 sigma in about 0.65, 0.95, 0.99 of cases |
查看完整验算程序
# Chapter 2. p22: the 1.04 / sqrt(m) law checked by 4,000 sketches per m.
# Poisson model (as in the analysis of Flajolet et al. 2007): with an
# ideal hash and Poisson(n) distinct items, the items of one register
# are Poisson(lam = n / m) and P(register <= r) = exp(-lam * 2^-r), so a
# register is drawn exactly by inverting that law. n = 1,000,000; the
# Poisson spread of n itself adds a relative 0.001, negligible here.
# Raw estimator E = alpha_m m^2 / sum 2^-M_j (no range correction is
# needed at n >> m). Paper constants: beta_16 = 1.106, beta_32 = 1.070,
# beta_64 = 1.054, beta_128 = 1.046, beta_inf = sqrt(3 ln 2 - 1);
# alpha_inf = 1 / (2 ln 2).
import math
import random
rng = random.Random(20261113)
N, T = 1000000, 4000
BETA = {16: 1.106, 64: 1.054}
def alpha(m):
table = {16: 0.673, 32: 0.697, 64: 0.709}
return table.get(m, 0.7213 / (1.0 + 1.079 / m))
def draw(lam):
u = rng.random()
while u == 0.0:
u = rng.random()
x = lam / -math.log(u)
return 0 if x <= 1.0 else math.ceil(math.log2(x))
def sketch_estimate(m):
lam = N / m
regs = [draw(lam) for _ in range(m)]
return alpha(m) * m * m / math.fsum(2.0 ** -r for r in regs)
print("beta_inf = sqrt(3 ln 2 - 1) = %.5f" % math.sqrt(3 * math.log(2) - 1))
print("alpha_inf = 1 / (2 ln 2) = %.5f" % (0.5 / math.log(2)))
print(" m bias emp.SE SE*sqrt(m) paper in1s in2s in3s")
for m in (16, 64, 256, 1024, 4096):
rel = [sketch_estimate(m) / N - 1.0 for _ in range(T)]
mu = math.fsum(rel) / T
sd = math.sqrt(math.fsum((r - mu) ** 2 for r in rel) / (T - 1))
s = 1.04 / math.sqrt(m)
cover = [len([r for r in rel if abs(r) <= k * s]) / T
for k in (1, 2, 3)]
paper = "%.3f" % BETA[m] if m in BETA else " 1.04"
print("%4d %7.4f %8.4f %11.3f %6s %5.3f %5.3f %5.3f"
% (m, mu, sd, sd * math.sqrt(m), paper,
cover[0], cover[1], cover[2]))
print("paper: within 1, 2, 3 sigma in about 0.65, 0.95, 0.99 of cases")唯一数据源与引用
范雅福(Fan, Y.). (2026). 《布隆过滤器与超对数对数基数估计、千字节内存统计百站独立访客与去重订单母典》第 2 章「超对数对数:首个 1 位、调和平均与 1.04/√m」(版本 1.0.0). 5D Library. DOI 待发布
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-294 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026294,
author = {Fan, Yafu},
title = {Bloom Filters and HyperLogLog Cardinality Estimation: Counting Unique Visitors and Deduplicating Orders across a Hundred Sites in Kilobytes},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}