S03-X13 · 轻量算法与数据加工：GCD、斐波那契、Map-Reduce 与脱敏
面试题里的算法和线上代码里的算法不是一回事。线上要的是能在约束里跑完、能解释为什么这么写、出问题时知道往哪看。四个看起来"太基础"的东西——最大公约数、斐波那契数列、Map-Reduce 的聚合模型、PII 脱敏正则——恰好都是这种：写起来几行，写错了要几个月才发现。
这篇把它们放在同一条链上：数论 → 递推 → 聚合 → 脱敏，每一步都给出边界与代价。
1. Euclidean_algorithm：为什么取模版比减法版快得多
欧几里得算法求最大公约数有两个版本：减法版（gcd(a,b) = gcd(a-b,b)）和取模版（gcd(a,b) = gcd(b, a mod b)）。两者数学等价，复杂度差一个量级。
// 取模版：迭代实现，无递归栈风险
static long gcd(long a, long b) {
a = Math.abs(a); b = Math.abs(b);
while (b != 0) {
long t = a % b;
a = b;
b = t;
}
return a;
}
// 最小公倍数：必须先除后乘，否则 long 溢出
static long lcm(long a, long b) {
return a / gcd(a, b) * b; // 不是 a * b / gcd
}
| 版本 | 单步代价 | 步数 | 最坏情况 |
|---|---|---|---|
| 减法版 | 一次减法 | 与 a/b 的比值成正比 |
a 极大、b = 1 时退化成 O(a) |
| 取模版 | 一次除法 | O(log min(a,b)) 步 | 斐波那契相邻项是经典最坏输入 |
| 二进制 GCD | 移位与减法 | 与取模版同级，但避免除法 | 除法昂贵的嵌入式环境 |
取模版的最坏输入是相邻斐波那契数——这正好接上下一节。工程上的用法其实很具体：
| 用途 | 怎么用 | 注意 |
|---|---|---|
| 比例缩减 | 把 (宽, 高) 除以 gcd 得到最简比 |
宽高为 0 时 gcd 返回 0，要单独判 |
| 分片对齐 | 用 lcm 求多个周期的最小公倍数 |
先除后乘防溢出 |
| 配额取整 | 用 gcd 把一组配额缩放到整数 | 缩放后要校验和不超总量 |
| 时间对齐 | 把不同间隔的定时任务对齐到公共周期 | 周期过大会导致任务稀疏 |
gcd 的溢出陷阱在 lcm 上最明显：a * b 先乘，两个接近 Long.MAX_VALUE 的数会直接回绕成负数，得到一个"看起来正常"的错误结果。这类 bug 不会抛异常，只会在对账时差几条。
2. Fibonacci_number：从 O(2^n) 到 O(log n) 的三次跳跃
斐波那契数列是"同一个问题三种复杂度"的最佳教具，也是线上最容易写错的一类递归。
// 版本一：朴素递归，O(2^n)，只用于教学
static long fibNaive(int n) {
return n < 2 ? n : fibNaive(n - 1) + fibNaive(n - 2);
}
// 版本二：迭代，O(n) 时间 / O(1) 空间，工程默认选它
static long fibIter(int n) {
long a = 0, b = 1;
for (int i = 0; i < n; i++) {
long t = a + b;
a = b;
b = t;
}
return a;
}
// 版本三：矩阵快速幂，O(log n)，n 很大时才划算
static long fibFast(long n) {
long[][] r = {{1, 0}, {0, 1}}; // 单位阵
long[][] m = {{1, 1}, {1, 0}};
while (n > 0) {
if ((n & 1) == 1) r = mul(r, m);
m = mul(m, m);
n >>= 1;
}
return r[0][1];
}
| 版本 | 时间复杂度 | 空间 | n 的实际上限（long） |
适用 |
|---|---|---|---|---|
| 朴素递归 | O(2^n) | O(n) 栈深 | n≈40 就明显卡 | 教学、验证小规模 |
| 迭代 | O(n) | O(1) | n≈92 后溢出 long |
默认选择 |
| 矩阵快速幂 | O(log n) | O(1) | 同上，溢出先于超时 | n 极大但只需取模 |
| 记忆化递归 | O(n) | O(n) | 同上 | 需要中间结果的场景 |
三个坑：
- 溢出先于超时。
long在 n≈92 溢出，矩阵快速幂算得快但结果已经是错的；需要大数时用BigInteger，或全程取模。 - 递归深度。记忆化递归在 n 很大时会爆栈，迭代不会。
- 矩阵乘法的直觉。矩阵快速幂之所以成立，是因为递推可以写成矩阵乘法的幂；这条"线性变换反复作用"的直觉，3Blue1Brown 的线性代数系列讲得比大多数教材直观，值得先建立直觉再看代码。
斐波那契还常被借用来做容量估算的类比：指数增长的排队在早期看不出问题，等看出问题时已经越过拐点。它的价值不在数列本身，而在"增长曲线的形状"。
3. Map-Reduce：四段结构，不只是 Hadoop
Map-Reduce 常被当成一个框架名，其实它是一个数据流的四段结构：map（拆分并转换）→ shuffle（按 key 分组）→ combine（可选，局部预聚合）→ reduce（按 key 汇总）。单机写 groupingBy 也是同一套结构。
// 单机版的 map-reduce：四段结构完全对应
Map<String, Long> bytesByHost = logs.stream()
.map(line -> line.split("\\s+")) // map：拆字段
.filter(f -> f.length >= 7) // 过滤脏行
.collect(Collectors.groupingBy( // shuffle：按 key 分组
f -> f[0], // host
Collectors.summingLong(f -> Long.parseLong(f[6])))); // reduce
| 阶段 | 输入 → 输出 | 能否省略 | 出问题的典型表现 |
|---|---|---|---|
| map | 一条记录 → 若干键值对 | 不可省 | 字段切错，后续全部错位 |
| shuffle | 按键分组，跨网络传输 | 不可省，代价最高 | 数据倾斜：某个 key 占八成数据 |
| combine | 局部预聚合，输入输出同型 | 可省，但强烈建议 | 省了之后 shuffle 数据量翻数倍 |
| reduce | 按键汇总成最终结果 | 不可省 | 汇总逻辑非结合律，结果依赖顺序 |
combiner 的前置条件是"聚合函数满足结合律与交换律"。求和、取最大值可以；求平均值、求中位数不行——avg(avg(a,b),c) ≠ avg(a,b,c)。这是面试与线上事故的双重高频点。
// 反例：把平均值当可 combine
map 阶段输出 (host, 100ms), (host, 300ms)
combiner 若输出 (host, avg=200) 且丢掉了条数
reduce 阶段拿到 (host,200) 与 (host,400) 再平均 → 300，真值是 266.7
结论：平均值必须用 (sum, count) 二元组穿过整个流程，在最后一步才做除法。
数据倾斜的处理手段同样落在这四段里：给热点 key 加随机后缀打散（改 shuffle 的键）、把小表广播（省掉 shuffle）、两阶段聚合（先局部 combine 再全局 reduce）。
4. PIIPattern：脱敏不是"把中间几位换成星号"
PII（个人可识别信息）脱敏最容易做成"看起来脱敏了"：手机号中间四位打码，但同一份数据里还有身份证、邮箱、地址、设备号可以关联回本人。工程上要做的是模式识别 + 一致性处理 + 可验证。
// 识别用模式，替换用策略，两者分开配置
static final Map<String, Pattern> PII = Map.of(
"phone", Pattern.compile("(?<!\\d)1[3-9]\\d{9}(?!\\d)"),
"idcard", Pattern.compile("(?<!\\d)\\d{17}[\\dXx](?!\\d)"),
"email", Pattern.compile("[\\w.+-]+@[\\w-]+\\.[\\w.]{2,}"),
"bankcard", Pattern.compile("(?<!\\d)\\d{16,19}(?!\\d)")
);
// 同一主体在同一批次内必须映射到同一个假值，否则关联分析失效
String token = "PII-" + hmacSha256(salt, rawValue).substring(0, 12);
| 字段 | 识别手段 | 误伤来源 | 处理策略 |
|---|---|---|---|
| 手机号 | 前缀 + 11 位 + 前后边界 | 订单号、时间戳恰好 11 位 | 加 (?<!\d) 边界 + 长度校验 |
| 身份证 | 18 位 + 末位校验码 | 随机串撞上格式 | 先算校验位，再判定 |
| 银行卡 | 16–19 位 + Luhn 校验 | 长数字 ID | Luhn 过滤掉绝大多数误报 |
| 邮箱 | 正则 + 域名白名单 | 内部系统标识含 @ |
排除内部域名 |
| 地址 | 词典/模型，非正则 | 分词粒度 | 分级脱敏（省市区保留，门牌去掉） |
三条实践约束：
- 正则会漏，也会误伤。宁可多一道校验（Luhn、身份证校验位），也不要靠一条正则包打天下。
- 假值必须稳定。同一个人在不同批次的假值不一致，等于把"可关联"变成了"不可关联但也不可追溯"，下游对账会崩。用
HMAC(salt, 值)派生假值是常见做法。 - 脱敏日志与明文日志不能共存于同一条链路。日志框架的
MDC、异常堆栈里的参数回显、SQL 打印，都会绕过你的脱敏层。
$ grep -rEo "1[3-9][0-9]{9}" /var/log/app/*.log | sort | uniq -c | head
上线前用这条命令自查一遍，比写十页脱敏规范有效。
5. 排错：五个"算出来了但不对"的现象
| 现象 | 原因 | 处理 |
|---|---|---|
lcm 返回负数 |
先乘后除导致 long 回绕 |
改成 a / gcd * b |
| 斐波那契结果突然变小 | long 溢出后回绕 |
改 BigInteger 或全程取模 |
递归版本偶发 StackOverflowError |
n 超过默认栈深能承载的层数 | 改迭代 |
| 聚合结果与明细对不上 | combiner 用了非结合律函数 | 换 (sum,count) 二元组 |
| 脱敏后仍能定位到人 | 关联字段未同步处理 | 对主体做统一假值映射，覆盖全字段 |
6. 边界：什么时候这些"基础"不够用
| 场景 | 为什么不够 | 该用什么 |
|---|---|---|
| 亿级数据聚合 | 单机内存装不下 shuffle 结果 | 分布式计算框架或预聚合表 |
| 强隐私合规要求 | 正则识别不了自由文本里的姓名与地址 | NER 模型 + 人工抽检 |
| 需要可逆脱敏 | 哈希不可逆，业务要回查 | 加密（保留格式加密或密钥托管） |
| 极端性能要求 | 除法与取模在热点路径上仍然昂贵 | 位运算、预计算表、SIMD |
| 浮点聚合 | 求和顺序影响结果 | Kahan 求和或定点数 |
一句话：算法的选择标准不是"最优复杂度"，而是"在数据规模与约束下最不容易错的复杂度"。
8. 自测
lcm为什么必须先除后乘？- 斐波那契的矩阵快速幂在
n很大时，先出问题的是时间还是数值？ - combiner 能被使用的前提是什么，为什么平均值不满足？
- 数据倾斜应该在哪一段处理，三种手段分别改了什么？
- 脱敏假值为什么必须跨批次稳定？
- 身份证这类字段，正则之外还要补哪一步校验？