magic-algorithm · 十四个开关

十四个开关

所有算法可视化站都在演示算法怎么工作。这十四份演示的是没有它世界会怎么样——每一个都配一个能真按下去的开关,关掉之后屏幕上必须有东西当场塌掉。选它们的判据只有一条反事实:如果 1950 年有人证明它不可能存在,今天少的不是一点速度,是一整个行业。

十四份 · 全部建成 闸门 250 条断言 零后端 · 纯静态 被打回的二十七处 → 设计文档 · 路线图

十四个开关

01

傅里叶开关

Cooley & Tukey · 1965

关掉它,移动互联网不会被设计成今天这个样子。一个真的 5G OFDM 符号,和 71.4 微秒那道截止线。

次数比 372 倍秒表比 109×DFT 需 58.7 G/s 的芯片
02

纠错码开关

Shannon 1948 → Reed–Solomon 1960

关掉它,数字存储和数字通信全都变得不可信。真的 GF(256) Reed–Solomon,可以用鼠标砸坏字节。

16 个错 100%17 个错 0%冗余只要 12.5%
03

公钥开关

Diffie–Hellman 1976 · RSA 1977

关掉它,互联网只能是个公告板,不可能是市场。Eve 真的在跑大步小步算法。

40 位半秒破44 位内存先撑不住2¹²⁸ = 1.12 倍宇宙年龄
04

压缩开关

Huffman 1952 · DCT 1974

关掉它,流媒体在物理上不能存在。一个真的编解码器在浏览器里现编现解。

压缩比 33.7 倍熵编码值 19.6 倍运动补偿只值 1.02 倍
05

卡尔曼开关

Rudolf Kálmán · 1960 · 阿波罗

关掉它,人类到不了月球,你的手机也不知道自己在哪条车道

惯导 120 秒漂 538 米零偏归零只漂 68 米RMSE ÷ σ = 1.01
06

维数灾难开关

Ulam 1946 · Metropolis 1953

关掉它,高维空间里的一切都算不动。外带 Metropolis 接受准则的开关。

交叉点恰好 d=4= 2 × 求积阶数d=10 差 130 万倍
07

梯度开关

Linnainmaa 1970 · Rumelhart 1986

关掉它,你现在正在用的这个东西不存在。同样的前向预算,两个决策边界并排。

差 205 倍梯度误差 7.6×10⁻¹⁰最优 ε = ∛εm
08

拥塞崩溃开关

Van Jacobson · 1988

关掉它,互联网扩展不到几十台机器以上。两个开关管的是两件不同的事。

RTO 管吞吐 100%→6.2%AIMD 管公平 0.997→0.461作弊流 →0.184
09

单纯形开关

George Dantzig · 1947

关掉它,整个物理经济的调度层退回到拍脑袋。外带 Klee–Minty 那族反例。

实测 0.38m ~ 0.57mKlee–Minty 恰好 2ⁿ−1Bland 规则降到 177 步
10

一致性哈希开关

Karger et al. 1997 · Akamai 1998

关掉它,每加一台缓存机器,整个互联网都要回源一次。一行取模换成环上取后继。

取模搬 89.0%环只搬 11.8%其中白搬 77.8%
11

拍卖与匹配开关

Vickrey 1961 · Gale–Shapley 1962

关掉它,市场不是变慢,是所有人开始撒谎。前十份关的是「机器算得动」,这一份关的是「人肯说真话」。

收入一分没少 0.6667照实出价收益 0.0000阻塞对 0.0
12

分布式一致性开关

Lamport 1998 · Raft 2014

关掉它,不是变慢,是两个人同时以为自己是对的。提交前要不要等多数派确认。

分叉条目 15970代价:可用率 88.1%枚举 55 对全相交
13

FM-index 开关

BWT 1994 · Ferragina–Manzini 2000

关掉它,「千元基因组」里便宜下来的那一半根本没发生——测序仪读得再快,也没人比对得完。

后向 200 步逐位置 159 962 步错 1 个碱基就 0.0%
14

PageRank 开关

Page & Brin 1998

关掉它,搜索结果的前十名可以被造出来——链接是免费的,造一批垃圾页互指就行。

数入链要 36 个垃圾页PageRank 要 340 个⚠ 它不免疫,只是贵 9 倍