关于「订单去重:过滤器只分流、不拒单,窗口分代与计数删除」,《布隆过滤器与基数估计》给出的定量结论是什么?
结论:第五章规定过滤器只分流、不拒单:查库量减少 0.987,而凭过滤器拒单三十天会拒错 4916 张真实订单;窗口用两代轮换,删除用计数过滤器,普通过滤器清零会让 0.3944 的有效订单读成没见过。
数据口径:示意网络中,各站独立访客相加是真实人数的 2.224 倍。 书中的站点、访客、订单与流量参数均为示意;全部计算由书中程序生成;本书是非个人化经营建议;访客统计只用匿名化、加密钥哈希的标识,不收集个人身份信息,须遵守所在地个人信息保护法规与站点隐私声明,法规只述大意,以上架前人工复核为准。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.987, 4916
| keys held n | 600000; exact set of 64-bit keys = 4687.5 KB |
| bits/key k filter KB FP rate store lookups/day saved | |
| 6 | 4 439.5 0.05606 1221.1 0.939 |
| 8 | 6 585.9 0.02158 531.5 0.974 |
| 10 | 7 732.4 0.00819 263.9 0.987 |
| 12 | 8 878.9 0.00314 162.8 0.992 |
| 16 11 | 1171.9 0.00046 109.2 0.995 |
| if the filter alone rejected orders, at 10 bits/key: | |
| genuine orders refused per day | 163.9 |
| chance of at least one refusal per day | 1.000000 |
| refused per 30-day window | 4916 |
查看完整验算程序
# Chapter 5. p51: a Bloom filter may route orders, never reject them.
# Illustrative network: 100 sites, 20,000 new orders a day plus 100
# resubmissions (double clicks, client retries); a 30-day dedup window,
# so n = 600,000 order keys are held. Gate: "definitely new" from the
# filter goes straight through; "maybe seen" goes to the exact order
# store. FP rate from the closed form at the best integer k; the exact
# rate is slightly higher (p43), negligible at this size.
import math
NEW, DUP, DAYS = 20000, 100, 30
N = NEW * DAYS
def fp(c):
k = min(range(1, 40), key=lambda j: (1 - math.exp(-j / c)) ** j)
return k, (1 - math.exp(-k / c)) ** k
print("keys held n = %d; exact set of 64-bit keys = %.1f KB"
% (N, N * 8 / 1024))
print("bits/key k filter KB FP rate store lookups/day saved")
for c in (6, 8, 10, 12, 16):
k, p = fp(c)
look = DUP + p * NEW
print("%8d %2d %10.1f %9.5f %18.1f %6.3f"
% (c, k, c * N / 8 / 1024, p, look, 1 - look / (NEW + DUP)))
k, p = fp(10)
print("if the filter alone rejected orders, at 10 bits/key:")
print(" genuine orders refused per day: %.1f" % (p * NEW))
print(" chance of at least one refusal per day: %.6f"
% (1 - (1 - p) ** NEW))
print(" refused per 30-day window: %.0f" % (p * NEW * DAYS))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《布隆过滤器与超对数对数基数估计、千字节内存统计百站独立访客与去重订单母典》第 5 章「订单去重:过滤器只分流、不拒单,窗口分代与计数删除」(版本 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}
}