关于「实证闭环:收费站与直答页只存寄存器的周报与预注册审计」,《布隆过滤器与基数估计》给出的定量结论是什么?
结论:第八章给出收费站与直答页只存寄存器的周报流程、基数估计器与预注册审计方案:示范周两页并集估计 35420 人、审计 35818 人,离散检验需要 70 个页日,订单闸门需要 3463 个已知新键。书中以标注框区分已发表的证据、可运行的 Python 计算(20 段程序)、原典与作者的假说。
数据口径:示意网络中,各站独立访客相加是真实人数的 2.224 倍。 书中的站点、访客、订单与流量参数均为示意;全部计算由书中程序生成;本书是非个人化经营建议;访客统计只用匿名化、加密钥哈希的标识,不收集个人身份信息,须遵守所在地个人信息保护法规与站点隐私声明,法规只述大意,以上架前人工复核为准。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 35420, 35818
| day T est T audit A est A audit | |
| 1 | 3267 3231 4150 4210 |
| 2 | 4583 4577 4071 4004 |
| 3 | 3822 3832 3123 3113 |
| 4 | 2785 2774 5875 5830 |
| 5 | 5607 5562 2873 2922 |
| 6 | 4736 4789 4574 4507 |
| 7 | 4115 4155 5759 5807 |
| week T 21137 (audit 21281), week A 18298 (audit 18563) | |
| week union 35420 (audit 35818) | |
| week overlap 4014 (audit 4026), share 0.113, FLAG: unreliable | |
| daily SE 0.0163; overlap shares below 0.2 are flagged | |
| stored | 14 sketches x 3072 bytes = 43008 bytes, no identifiers |
查看完整验算程序
# Chapter 8. p81: one week of unique visitors on two pages, registers
# only. Illustrative traffic: page T (a tollbooth page) draws from a pool
# of 40,000 people, page A (a direct-answer page) from 25,000, with
# 10,000 in both pools; 2,500 to 6,000 people a day per page, 1 to 3
# hits each. Identifiers are hashed with a key that lives for one
# weekly window only; each page keeps one m = 4096 sketch per day
# (3,072 bytes). Weekly figures are register-wise maxima. Exact sets
# exist here only as the audit column; the daily pipeline keeps none.
# Counts under 50 would be shown as "<50" (none occur here).
import hashlib
import math
import random
rng = random.Random(20261113)
M, B, DAYS = 4096, 12, 7
ALPHA = 0.7213 / (1.0 + 1.079 / M)
WINDOW_KEY = b"b294-demo-window-label"
POOLS = {"T": range(0, 40000), "A": range(30000, 55000)}
def h64(text):
d = hashlib.blake2b(text.encode(), digest_size=8, key=WINDOW_KEY)
return int.from_bytes(d.digest(), "big")
def add(regs, x):
j = x >> (64 - B)
rho = (64 - B) - (x & ((1 << (64 - B)) - 1)).bit_length() + 1
if rho > regs[j]:
regs[j] = rho
def estimate(regs):
e = ALPHA * M * M / math.fsum(2.0 ** -r for r in regs)
v = regs.count(0)
if e <= 2.5 * M and v > 0:
return M * math.log(M / v)
return e
def shown(x):
return "<50" if x < 50 else "%.0f" % x
daily = {p: [] for p in POOLS}
audit = {p: [] for p in POOLS}
print("day T est T audit A est A audit")
for day in range(1, DAYS + 1):
row = []
for page, pool in POOLS.items():
regs, seen = [0] * M, set()
for person in rng.sample(pool, rng.randint(2500, 6000)):
x = h64("visitor-%06d" % person)
for _ in range(rng.randint(1, 3)):
add(regs, x)
seen.add(person)
daily[page].append(regs)
audit[page].append(seen)
row += [shown(estimate(regs)), len(seen)]
print("%3d %7s %8d %7s %8d" % (day, row[0], row[1], row[2], row[3]))
week = {p: [max(c) for c in zip(*daily[p])] for p in POOLS}
exact = {p: set().union(*audit[p]) for p in POOLS}
both = [max(a, b) for a, b in zip(week["T"], week["A"])]
eu = estimate(both)
inter = estimate(week["T"]) + estimate(week["A"]) - eu
ex_i = len(exact["T"] & exact["A"])
print("week T %.0f (audit %d), week A %.0f (audit %d)"
% (estimate(week["T"]), len(exact["T"]), estimate(week["A"]),
len(exact["A"])))
print("week union %.0f (audit %d)" % (eu, len(exact["T"] | exact["A"])))
flag = "FLAG: unreliable" if inter / eu < 0.2 else "ok"
print("week overlap %.0f (audit %d), share %.3f, %s"
% (inter, ex_i, inter / eu, flag))
print("daily SE %.4f; overlap shares below 0.2 are flagged"
% (1.04 / math.sqrt(M)))
print("stored: %d sketches x %d bytes = %d bytes, no identifiers"
% (2 * DAYS, M * 6 // 8, 2 * DAYS * M * 6 // 8))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《布隆过滤器与超对数对数基数估计、千字节内存统计百站独立访客与去重订单母典》第 8 章「实证闭环:收费站与直答页只存寄存器的周报与预注册审计」(版本 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}
}