关于「精确去重的内存账:独立访客为什么不能相加」,《布隆过滤器与基数估计》给出的定量结论是什么?
结论:精确去重的内存与人数几乎成正比:一亿访客时信息论下限是 485.841 MB,是一个 3072 字节草图的 158151 倍。这不是工程不够好,而是有严格证明的结论:确定性算法连一成以内的近似都需要线性内存,随机算法要精确也需要线性内存;只有随机化与近似同时接受,内存才能与人数无关。各站独立访客直接相加,在示意网络中高估了 2.224 倍;一百个草图按寄存器取最大值合并,误差是 0.0221,存储是 307200 字节。下一章拆开 HyperLogLog 本身:首个 1 位的位置为什么能数人,调和平均为什么比几何平均好,1.04/√m 这个常数从哪里来、到底有多准?
数据口径:示意网络中,各站独立访客相加是真实人数的 2.224 倍。 书中的站点、访客、订单与流量参数均为示意;全部计算由书中程序生成;本书是非个人化经营建议;访客统计只用匿名化、加密钥哈希的标识,不收集个人身份信息,须遵守所在地个人信息保护法规与站点隐私声明,法规只述大意,以上架前人工复核为准。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.0221, 1.04, 2.224, 307200
| visits logged | 834564 |
| sum of site uniques | 333606 |
| true unique visitors | 150000 |
| overstatement factor | 2.224 |
| top site uniques | 36187 |
| HLL union estimate | 153319.2 |
| HLL relative error | 0.0221 |
| nominal 1.04/sqrt(m) | 0.0163 |
| 100 sketches, bytes | 307200 |
| exact union as hashes | 1200000 bytes |
查看完整验算程序
# Chapter 1. p12: adding up site uniques overstates the network's reach.
# Illustrative network: 100 sites whose popularity falls as 1/rank^0.8;
# 150,000 visitors; each visits 1 + Geometric(0.45) sites (capped at 12)
# and makes 1 to 4 visits per site. Exact per-site sets and the exact
# union are counted; the sum of site uniques is what a report gets when
# it adds per-site dashboards together. Then one HyperLogLog sketch per
# site (m = 4096, keyed BLAKE2b, 64-bit) is merged by register maximum.
import bisect
import hashlib
import math
import random
rng = random.Random(20261113)
SITES, PEOPLE, M, B = 100, 150000, 4096, 12
W = [1.0 / (r + 1) ** 0.8 for r in range(SITES)]
CUM = [math.fsum(W[:i + 1]) for i in range(SITES)]
KEY = b"b294-illustrative-window-key"
ALPHA = 0.7213 / (1.0 + 1.079 / M)
def h64(text):
d = hashlib.blake2b(text.encode(), digest_size=8, key=KEY).digest()
return int.from_bytes(d, "big")
def add(regs, x):
j = x >> (64 - B)
w = x & ((1 << (64 - B)) - 1)
rho = (64 - B) - w.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
site_sets = [set() for _ in range(SITES)]
sketches = [[0] * M for _ in range(SITES)]
visits = 0
for p in range(PEOPLE):
k = 1
while k < 12 and rng.random() > 0.45:
k += 1
chosen = set()
while len(chosen) < k:
u = rng.random() * CUM[-1]
chosen.add(min(SITES - 1, bisect.bisect_left(CUM, u)))
x = h64("visitor-%06d" % p)
for s in sorted(chosen):
for _ in range(rng.randint(1, 4)):
site_sets[s].add(p)
add(sketches[s], x)
visits += 1 # step
union = set()
for s in site_sets:
union |= s
added = int(math.fsum(len(s) for s in site_sets))
merged = [max(col) for col in zip(*sketches)]
est = estimate(merged)
print("visits logged %9d" % visits)
print("sum of site uniques %9d" % added)
print("true unique visitors %9d" % len(union))
print("overstatement factor %9.3f" % (added / len(union)))
print("top site uniques %9d" % len(site_sets[0]))
print("HLL union estimate %11.1f" % est)
print("HLL relative error %9.4f" % (est / len(union) - 1.0))
print("nominal 1.04/sqrt(m) %9.4f" % (1.04 / math.sqrt(M)))
print("100 sketches, bytes %9d" % (SITES * M * 6 // 8))
print("exact union as hashes %9d bytes" % (8 * len(union)))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《布隆过滤器与超对数对数基数估计、千字节内存统计百站独立访客与去重订单母典》第 1 章「精确去重的内存账:独立访客为什么不能相加」(版本 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}
}